数据结构之栈

た入场券 2022-10-14 10:49 172阅读 0赞

**一.什么是栈？**  
本文将介绍一个重要的数据结构—栈，和之前讲到的链表、数组一样也是一种数据呈线性排列的数据结构，不过在这种结构中，我们只能访问最新添加的数据。栈就像是一摞书，拿到新书时我们会把它放在书堆的最上面，取书时也只能从最上面的新书开始取。

**栈**  
![在这里插入图片描述][20210521093834131.png]  
如上就是栈的概念图，现在存储在栈中的只有数据 Blue。往栈中添加数据的时候，新数据被放在最上面。  
![在这里插入图片描述][2021052109390075.png]  
然后，我们往栈中添加了数据 Green。往栈中添加数据的操作叫作入栈。  
![在这里插入图片描述][20210521093919869.png]  
接下来，数据 Red 入栈。  
![在这里插入图片描述][20210521093935175.png]  
从栈中取出数据时，是从最上面，也就是最新的数据开始取出的，即 Red。从栈中取出数据的操作叫作出栈。  
![在这里插入图片描述][20210521093955403.png]  
如果再进行一次出栈操作，取出的就是 Green 了。  
像栈这种最后添加的数据最先被取出，即后进先出的结构，我们称为 Last In First Out，简称 LIFO。

与链表和数组一样，栈的数据也是线性排列，但在栈中，添加和删除数据的操作只能在一端进行，访问数据也只能访问到顶端的数据，想要访问中间的数据时，就必须通过出栈操作将目标数据移到栈顶才行。

介绍完栈的基本知识后，接下来举一个例子，比如大家正在看公众号文章，那我就拿微信的订阅号为例。

**二.如何理解栈？**

首先你打开订阅号，是一个公众号列表，之后你点击了一个公众号,进入了相应的文章列表界面。点击了某某文章。  
好了，现在你想返回订阅号怎么办呢？向右滑两次吧，第一次回到文章列表界面，第二次回到订阅号界面。  
这时候你就发现了，这些界面的储存结构可以说是一个栈结构，你打开文章详情页面，必须经过两次入栈才能达到，你想回到订阅号界面（位于栈底），必须经历两次出栈把前面两个界面移除。

**三.栈的实现**

看到这里，相信你已经对栈有了初步的理解，栈主要包含两个操作，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据。光理解还不够，我们还要动手去实现栈，接下来让我们来看一看如何用代码实现一个栈。

栈有两种存储结构，即顺序存储和链式存储，也就是说栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

首先来看下用数组实现的栈是怎么样的，其实现如下图所示：  
![在这里插入图片描述][20210521094321714.png]  
那么我先用 Java 语言来实现下顺序栈，代码如下：

/** * 基于数组实现的顺序栈 * * @author wupx * @date 2020/02/11 */
    public class ArrayStack { 
        /** * 数组 */
        private String[] items;
        /** * 栈中元素个数 */
        private int count;
        /** * 栈的大小 */
        private int n;
    
        /** * 初始化数组，申请一个大小为 n 的数组空间 * * @param n */
        public ArrayStack(int n) { 
            this.items = new String[n];
            this.n = n;
            this.count = 0;
        }
    
        /** * 入栈 * * @param item * @return */
        public boolean push(String item) { 
            // 数组空间不够了，直接返回 false，入栈失败。
            if (count == n) { 
                return false;
            }
            // 将 item 放到下标为 count 的位置，并且 count 加一
            items[count] = item;
            ++count;
            return true;
        }
    
        /** * 出栈 * * @return */
        public String pop() { 
            // 栈为空，则直接返回 null
            if (count == 0) { 
                return null;
            }
            // 返回下标为 count-1 的数组元素，并且栈中元素个数 count 减一
            String tmp = items[count - 1];
            --count;
            return tmp;
        }
    }

另外一种就是链式栈，它的实现如下图所示：  
![在这里插入图片描述][20210521094355860.png]  
再用链表去实现栈，代码如下：

/** * 基于链表实现的链式栈 * * @author wupx * @date 2020/02/11 */
    public class LinkedListStack { 
        private Node top = null;
    
        /** * 入栈 * * @param value */
        public void push(int value) { 
            Node newNode = new Node(value, null);
            // 判断是否栈空
            if (top != null) { 
                newNode.next = top;
            }
            top = newNode;
        }
    
        /** * 出栈 * * @return */
        public int pop() { 
            if (top == null) { 
                // -1 表示栈中没有数据
                return -1;
            }
            int value = top.data;
            top = top.next;
            return value;
        }
    
        public void printAll() { 
            Node p = top;
            while (p != null) { 
                System.out.print(p.data + " ");
                p = p.next;
            }
            System.out.println();
        }
    
        private static class Node { 
            private int data;
            private Node next;
    
            public Node(int data, Node next) { 
                this.data = data;
                this.next = next;
            }
    
            public int getData() { 
                return data;
            }
        }
    }

在对栈有了更深一步的理解和实践后，让我们来看下它的空间、时间复杂度各是多少呢？

不管是顺序栈还是链式栈，我们存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。

入栈和出栈只会影响到最后一个元素，不涉及其他元素的整体移动，所以无论是以数组还是以链表实现，入栈、出栈的时间复杂度都是 O(1)。

**总结**  
看完之后，相信大家都对栈有了一定的了解，让我们总结下这篇文章的内容，栈是一种线性逻辑结构，只支持入栈和出栈操作，遵循后进先出的原则（FILO）。栈既可以通过数组实现，也可以通过链表来实现，不管基于数组还是链表，入栈、出栈的时间复杂度都为 O(1)。

[20210521093834131.png]: /images/20221014/3e6a22d02ff74d1da812aa3e21670d5e.png
[2021052109390075.png]: /images/20221014/345375d02703444388539ce82e9cdb9a.png
[20210521093919869.png]: /images/20221014/a4b2c4feab61436aa4cd11c00a13be8e.png
[20210521093935175.png]: /images/20221014/d3316d690e7049299b03466bc97df78f.png
[20210521093955403.png]: /images/20221014/2d289c4b9469420ba4800274582cb806.png
[20210521094321714.png]: /images/20221014/21655e0b927a42619850303a81224f14.png
[20210521094355860.png]: /images/20221014/4440347ff8b64ac398a51e056dd71d5f.png