数据结构与算法 —— 02 栈

2.栈(stack) ——————本质为:"线性表"
栈是限定仅在表尾进行'插入'和'删除'的线性表。允许插入和删除的一端称为栈顶(top),另一端则称为栈底(bottom),不含任何元素的栈称为'空栈'。

主要基本操作:

    ① 初始化
    ② 入栈(进栈、压栈、插入)
    ③ 出栈(弹栈、删除)
    ④ 获取 —— 取栈顶数据元素。注意:不删除栈中的数据,这是和'出栈'的区别
    ⑤ 判空
    ⑥ 求长度
    ⑦ 正序遍历
    ⑧ 清空(只是把栈的top指针归回原位,并非把栈中的内容销毁,即原内容还是存在的)

表示形式:
㈠'逻辑结构':
S = (a1, a2, ... , an), a1为栈底元素,an为栈顶元素

            进栈   出栈
              ↓     ↑
 栈顶————> ┌───────────┐
           ├───────────┤(n)
           ├───────────┤
           ├───────────┤ .
           ├───────────┤ .
           ├───────────┤ .
           ├───────────┤(2)
           ├───────────┤(1)
 栈底————> └───────────┘(0)
                        (-1)

特点:'后进先出(LIFO, last in first out)',因此又被称之为后进先出的线性表

㈡'物理存储结构'
(1) 顺序存储结构:顺序栈
利用一组地址连续的存储单元(由数组实现)依次存放自'栈底'到'栈顶'的数据元素,把数组中下标为0的一端作为栈底,为了指示栈中元素的位置,需要定义栈顶指针(top,为整型)来指示栈顶元素在顺序栈中的位置

顺序栈为"空"的条件:top == -1;

代码描述:

public class SequenceStack<T> {

    private final int maxSize = 10; //栈的默认存储容量
    private T[] stackArray; //模拟栈的数组
    private int top; //栈顶指针
    /**
    *   顺序栈的初始化
    *   注意:顺序栈的长度是固定的,因此,初始化时有两种方式:
    *   1.不指定长度(即采用默认的长度)
    *   2.指定长度
    */
    //采用默认容量初始化
    public SequenceStack() {
        top = -1; //初始化栈顶指针,之所以从-1开始,是因为数组是从0开始的
        stackArray = (T[])new Object[maxSize];
    }
    //采用指定的容量初始化
    public SequenceStack(int n) {
        //对传入的参数进行合法性检查
        if (n <= 0) {
            System.out.println("error!");
            System.exit(1);
        }

        top = -1;
        stackArray = (T[])new Object[n];
    }       
    /**
    *   入栈操作
    */
    public void push(T obj) {
        
        /*
        * 由于,顺序栈是基于数组实现的,因此,插入数据时要考虑栈满的情况(但是链栈则不存在栈满的情况)
        * 插入数据时,需要检查一下当前栈是否满了,需要扩容
        */
        if (top == stackArray.length - 1) {
            T[] p = (T[])new Object[top*2 + 2]; //容量扩展为原来的2倍
            //将原来的数据复制到新的数组中
            for (int i = 0; i <= top; i++) {
                p[i] = stackArray[i];
            }
            stackArray = p;
        }
        //插入数据
        top ++;
        stackArray[top] = obj;
    }
    //  出栈操作, 时间复杂度:O(1)
    public T pop() {
        //需要检查栈是否为空
        if (isEmpty()) {
            System.out.println("栈为空,不可进行出栈操作!");
            return null;
        }
        //删除元素: 应该先返回元素再将top--,但在程序中return不能先执行,否则top--执行不到了
        top --;
        return stackArray[top + 1];

    }
    // 获取
    public T getHead() {
        if (isEmpty()) {
            System.out.println("栈为空,不可进行获取栈顶元素的操作!");
            return null;
        }
        //注意:只是返回栈顶的元素,不删除它,因此不修改栈顶指针
        return stackArray[top];
    }
    // 判空
    public boolean isEmpty() {
        return top == -1;
    }
    // 求长度
    public int size() {
        return top + 1;
    }
    // 正序遍历
    public void nextOrder() {
        System.out.print("[");
        //注意:遍历栈,也就类似于将栈元素依次出栈的顺序打印出来
        for (int i = top; i >= 0; i--) {
            if (i == 0) {
                System.out.print(stackArray[i]);
            } else {
                System.out.print(stackArray[i] + ", ");
            }
            
        }
        System.out.println("]");

    }
    // 销毁栈
    public void clear() {
        top = -1; //将栈顶指针调整为-1即可。
    }

}

★ 两栈共享空间
当两个栈的'入栈'和'出栈'在同一时段是"彼此相反"的,则可以考虑让它们共享同一个数组,一个栈的栈底在数组的0处,另一个栈的栈底在数组的末端,彼此相中间入栈
top1 ↓ top2 ↓
┌──┬──┬──┬──┬──┬──┬ ... ─┬──┬──┬──┬──┬──┬──┐
└──┴──┴──┴──┴──┴──┴ ... ─┴──┴──┴──┴──┴──┴──┘
(栈1的底)0 1 n-1 n (栈2的底)

public class SharStack<T> {
    private int top1; //1号栈的栈顶指针
    private int top2; //2号栈的栈顶指针
    private T[] data; //共享的数组
    
    //初始化
    public init() {
        ...
    }
    /**
    *   入栈:插入元素
    */
    public void push(T obj, int stackNumber) {
        //判断是否栈满
        // 当两个栈指针“碰头”时,表示栈满了,此时两个指针相差1
        if (top1 + 1 == top2) {
            //或者扩容、或者返回null
            System.out.println("栈已满,不能进行入栈操作");
            return null;
        }
        //入栈操作
        if (stackNumber == 1) {
            //表示对栈1入栈
            top1 ++;
            data[top1] = obj;
        }
        if (stackNumber == 2) {
            //表示对栈2入栈
            top2 --;
            data[top2] = obj;
        }
    }

    //出栈:删除元素
    public T pop(int stackNumber) {
        //判断是哪个栈的出栈
        //对栈1的操作
        if (stackNumber == 1) {
            //判断是否出现栈空
            if (top1 == -1) {
                System.out.println("栈1已空,不能进行出栈操作");
                return null;
            }
            //正常出栈
            top1 --;
            return data[top1+1];
        }

        //对栈2的操作
        if (stackNumber == 2) {
            //判断是否出现栈空
            if (top2 == data.length) {
                System.out.println("栈2已空,不能进行出栈操作");
                return null;
            }
            //正常出栈
            top2 ++;
            return data[top1-1];
        }
    }
}

(2) 链式存储结构:链栈
利用链表实现的,其中的每个数据元素(即Node结点)由两部分组成:数据域,指针域

由于,只在链栈的'头部'进行操作(进出栈),因此,没必要像单链表那样附加头结点,并且
'头指针与栈顶指针'合二为一。
┌───────┬───────────┐
top ————> │ an │ next(n-1) │ :实质为链表的表头
(链表头指针) └───────┴───────────┘
.
.
.
┌───────┬───────────┐
│ a2 │ next(1) │
└───────┴───────────┘
┌───────┬───────────┐
栈底 ————> │ a1 │ null │ :实质为链表的表尾
└───────┴───────────┘

链栈为"空"的条件:top == null

注意:尽管从存储结构上看,链栈是链表的形式,但是在操作上依然是栈的定义。

代码描述:
// 1.链栈的结点描述

public class Node<T> {
    T data;
    Node<T> next;
    //构造没有数据的结点
    public Node(Node<T> n) {
        next = n;
    }
    //构造有数据的结点
    public Node(T obj, Node<T> n) {
        data = obj;
        next = n;
    }

    public T getData() {
        return data;
    }
    public Node<T> getNext() {
        return next;
    }
}

// 2.链栈的描述

public class LinkStack<T> {
    private Node<T> top; //栈顶指针,具备头指针的作用
    private int length; //存储栈的长度(即数据元素的个数)
    /**
    *   初始化链栈:构造一个空的链栈
    */
    public LinkStack() {
        length = 0; //元素个数为0
        top = null; //top指向空
    }

    //入栈, 时间复杂度:O(1)
    public void push(T obj) {
        //将top指针由null状态指向一个新的Node结点处
        top = new Node<T>(obj, top); //该元素就是链表的尾部,因此,指针域为null
        length ++; //元素个数加1 
    }
    
    //出栈, 时间复杂度:O(1)
    public T pop() {
        //判空
        if (isEmpty()) {
            System.out.println("链栈为空,不能进行出栈操作!");
            return null;
        }

        //出栈过程
        T x = top.data;
        top = top.next;
        length --; //栈的元素长度减1
        return x;
    }

    //获取栈顶元素
    public T getHead() {
        //进行判空
        if (isEmpty()) {
            System.out.println("链栈为空,不能进行获取栈顶元素!");
            return null;
        }
        return top.data;
    }

    //判空
    public boolean isEmpty() {
        return top == null;
    }

    //求长度
    public int size() {
        return length;
    }

    //正向遍历
    public void nextOrder() {

        System.out.print("[");
        Node<T> p = top; //注意,不能将原链表进行输出,不然在进行其他操作将引起错误
        while (p != null) {
            if (p.next == null) {
                System.out.print(p.data);
            } else {
                System.out.print(p.data + ", ");    
            }
            p = p.next;
        }
        System.out.println("]");                    
    }

    //销毁链栈
    public void clear() {
        length = 0;
        top = null;
    }
}
顺序栈和链栈的优缺点:

顺序栈和链栈在时间复杂度上是一样的,均为O(1)
在空间性能上:
• 顺序栈需要事先确定一个固定的长度,这样可能会造成空间的浪费。但其出入栈时的定位很方便。适用于元素数量变化可测的情况。
• 链栈则需要每个元素附件一个指针域,这在空间上增加了一定的内存开销,但它的长度灵活可变,不会造成空间上的浪费。适用于元素数量变化不可测的情况。

基于栈的一些应用:
进制转换
语法检查(如括号匹配问题)
回朔算法
递归算法
表达式求值

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 202,406评论 5 475
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,976评论 2 379
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 149,302评论 0 335
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,366评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,372评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,457评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,872评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,521评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,717评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,523评论 2 319
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,590评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,299评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,859评论 3 306
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,883评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,127评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,760评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,290评论 2 342

推荐阅读更多精彩内容