数据结构-线性结构：栈（Stack）【底层依托“动态数组”/“链表”】【“栈”的操作是“动态数组”操作的子集；“栈”只能同一端（称为“栈顶”）添加元素、取出元素；“后进先出”】

深碍√TFBOYSˉ_ 2023-10-04 12:19 7阅读 0赞

> 栈（stack） ：只能允许在一端进行加入数据和输出数据的**线性表**（可由顺序表(动态数组)或链表通过特定操作来实现栈规定的特性）

> 栈（stack）：有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。

> 由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]

## 一、 “栈”的操作 ##

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>作用</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Stack()</td> 
   <td>创建一个新的空栈</td> 
  </tr> 
  <tr> 
   <td>push(item)</td> 
   <td>添加一个新的元素item到栈顶</td> 
  </tr> 
  <tr> 
   <td>pop()</td> 
   <td>弹出栈顶元素</td> 
  </tr> 
  <tr> 
   <td>peek()</td> 
   <td>返回栈顶元素</td> 
  </tr> 
  <tr> 
   <td>is_empty()</td> 
   <td>判断栈是否为空</td> 
  </tr> 
  <tr> 
   <td>size()</td> 
   <td>返回栈的元素个数</td> 
  </tr> 
 </tbody> 
</table>

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 1]

## 二、 “栈”的应用 ##

*  undo操作-编辑器
 *  系统调用栈-操作系统
 *  括号匹配-编译器（LeetCode20）

## 三、 “栈”结构的代码实现 ##

栈可以用顺序表(动态数组)（python中的list数据结构是一种顺序表(**动态数组**)）实现，也可以用**链表**实现。

基于“动态数组”的栈、基于“链表”的栈整体上时间复杂度基本一致；最多2~3倍的差异；绝不会出现几百倍的差异；

### 1、基于“动态数组”的栈 ###

java代码：

MyStack.java

public interface MyStack<T> {
        
        int getCapacity();  // 获取栈的容量
    
        int getSize();  // 获取栈的大小
    
        boolean isEmpty();  // 判断栈是否为空
    
        void push(T element);   // 压栈
    
        T pop();    // 出栈
    
        T peek();   // 获取栈顶元素
    }

MyArray.java

public class MyArray<T> {
        
        private T[] data;
        private int size;
    
        public MyArray(int capacity){
        
            data = (T[])new Object[capacity];
            size = 0;
        }
    
        //默认构造方法，初始化最大容量为10
        public MyArray(){
        
            this(10);
        }
    
        //获取数组的大小
        public int getSize(){
        
            return size;
        }
    
        //获取数组最大容量
        public int getCapacity(){
        
            return data.length;
        }
    
        public boolean isEmpty(){
        
            return size == 0;
        }
    
        //向数组末尾添加元素
        public void add(T element){
        
            add(size, element);
        }
    
        //向数组中指定位置添加元素
        public void add(int index, T element){
        
            if (index < 0 || index > size){
        
                throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
            }
            if (size == data.length){
        
                resize(data.length * 2);
            }
            for (int i = size - 1; i >= index; i--){
        
                data[i + 1] = data[i];
            }
            data[index] = element;
            size++;
        }
    
        //获取指定位置的元素
        public T get(int index){
        
            if (index < 0 || index >= size){
        
                throw new IllegalArgumentException("Get faild. Index is illegal.");
            }
            return data[index];
        }
    
        //修改指定位置的元素
        public void set(int index, T element){
        
            if (index < 0 || index >= size){
        
                throw new IllegalArgumentException("Set faild. Index is illegal.");
            }
            data[index] = element;
        }
    
        //查找数组中是否包含该元素
        public boolean contains(T element){
        
            for (int i = 0; i < size; i++){
        
                if (data[i].equals(element)){
        
                    return true;
                }
            }
            return false;
        }
    
        //查找该元素的下标
        public int indexOf(T element){
        
            for (int i = 0; i < size; i++){
        
                if (data[i].equals(element)){
        
                    return i;
                }
            }
            return -1;
        }
    
        //删除数组末尾的元素
        public T remove(){
        
            return remove(size - 1);
        }
    
        //删除数组中指定位置的元素
        public T remove(int index){
        
            if (index < 0 || index >= size){
        
                throw new IllegalArgumentException("Remove faild. Index is illegal.");
            }
    
            T element = data[index];
            for (int i = index + 1; i < size; i++){
        
                data[i - 1] = data[i];
            }
            size--;
            data[size] = null;
    
            if (size == data.length / 4 && data.length / 2 != 0){
        
                resize(data.length / 2);
            }
            return element;
        }
    
        //删除数组中指定的元素
        public boolean remove(T element){
        
            int index = indexOf(element);
            if (index != -1){
        
                remove(index);
                return true;
            }
            return false;
        }
    
        //对数组进行扩容或缩容
        private void resize(int capacity){
        
            T[] newData = (T[])new Object[capacity];
            for (int i = 0; i < size; i++){
        
                newData[i] = data[i];
            }
            data = newData;
        }
    
        @Override
        public String toString() {
        
            StringBuilder string = new StringBuilder();
            string.append("[");
            for (int i = 0; i < size; i++){
        
                string.append(data[i]);
                if (i != size - 1){
        
                    string.append(", ");
                }
            }
            string.append("]");
            return string.toString();
        }
    }

MyArrayStack.java

//基于动态数组的栈
    public class MyArrayStack<T> implements MyStack<T> {
        
    
        MyArray<T> array;
    
        public MyArrayStack(int capacity) {
        
            array = new MyArray<>(capacity);
        }
    
        public MyArrayStack() {
        
            array = new MyArray<>();
        }
    
        @Override
        public int getSize() {
        
            return array.getSize();
        }
    
        @Override
        public boolean isEmpty() {
        
            return array.isEmpty();
        }
    
    
        @Override
        public void push(T element) {
        
            array.add(element);
        }
    
        @Override
        public T pop() {
        
            return array.remove();
        }
    
        @Override
        public T peek() {
        
            return array.get(array.getSize() - 1);
        }
    
        @Override
        public int getCapacity() {
        
            return array.getCapacity();
        }
    
    
        @Override
        public String toString() {
        
            StringBuilder string = new StringBuilder();
            string.append("Stack: ");
            string.append("bottom [");
            for (int i = 0; i < array.getSize(); i++){
        
                string.append(array.get(i));
                if (i != array.getSize() - 1){
        
                    string.append(", ");
                }
            }
            string.append("] top");
            return string.toString();
        }
    
    }

Main.java

public class Main {
        
        public static void main(String[] args){
        
            MyStack<String> stack = new MyArrayStack<>();
            System.out.println("stack.getCapacity() = " + stack.getCapacity());
            System.out.println("stack.getSize() = " + stack.getSize());
            System.out.println("stack.isEmpty() = " + stack.isEmpty());
            System.out.println("stack = " + stack);
            System.out.println("========================================================================================");
    
            stack.push("a");
            stack.push("b");
            stack.push("c");
            System.out.println("stack.getCapacity() = " + stack.getCapacity());
            System.out.println("stack.getSize() = " + stack.getSize());
            System.out.println("stack.isEmpty() = " + stack.isEmpty());
            System.out.println("stack = " + stack);
            System.out.println("========================================================================================");
    
            System.out.println("返回栈顶元素：stack.peek() = " + stack.peek());
            System.out.println("stack.getCapacity() = " + stack.getCapacity());
            System.out.println("stack.getSize() = " + stack.getSize());
            System.out.println("stack.isEmpty() = " + stack.isEmpty());
            System.out.println("stack = " + stack);
            System.out.println("========================================================================================");
    
            System.out.println("弹出栈顶元素：stack.pop() = " + stack.pop());
            System.out.println("stack.getCapacity() = " + stack.getCapacity());
            System.out.println("stack.getSize() = " + stack.getSize());
            System.out.println("stack.isEmpty() = " + stack.isEmpty());
            System.out.println("stack = " + stack);
            System.out.println("========================================================================================");
            
            MyArrayStack stack02 = new MyArrayStack();
            for(int i = 0; i< 5; i++){
        
                stack02.push(i);
                System.out.println(stack02);
            }
            System.out.println("========================================================================================");
            stack02.pop();
            System.out.println(stack02);
            System.out.println("========================================================================================");
        }
    }

输出结果：

stack.getCapacity() = 10
    stack.getSize() = 0
    stack.isEmpty() = true
    stack = Stack: bottom [] top
    ========================================================================================
    stack.getCapacity() = 10
    stack.getSize() = 3
    stack.isEmpty() = false
    stack = Stack: bottom [a, b, c] top
    ========================================================================================
    返回栈顶元素：stack.peek() = c
    stack.getCapacity() = 10
    stack.getSize() = 3
    stack.isEmpty() = false
    stack = Stack: bottom [a, b, c] top
    ========================================================================================
    弹出栈顶元素：stack.pop() = c
    stack.getCapacity() = 5
    stack.getSize() = 2
    stack.isEmpty() = false
    stack = Stack: bottom [a, b] top
    ========================================================================================
    Stack: bottom [0] top
    Stack: bottom [0, 1] top
    Stack: bottom [0, 1, 2] top
    Stack: bottom [0, 1, 2, 3] top
    Stack: bottom [0, 1, 2, 3, 4] top
    ========================================================================================
    Stack: bottom [0, 1, 2, 3] top
    ========================================================================================
    
    Process finished with exit code 0

### 2、基于“链表”的栈 ###

MyStack.java

MyLinkedList.java

/**
     * Title: 带虚拟头结点的链表
     * Description:
     * 链表结构包含两个要素： 头结点head + 链表大小size，
     * 操作包括：
     * 链表的增删
     * 链表是否为空
     * 链表的大小
     * 链表的打印输出
     * 删除链表重复节点
     * 链表倒数第K个元素
     * 链表的反转
     * 链表的倒序输出
     * 链表的中间节点
     * 链表是否有环
     * 链表节点的删除(不知道头结点的情况下)
     * 链表是否相交
     * 链表的交点
     */
    public class MyLinkedList<E> {
        
        // 节点
        private class Node {
        
            private E elem;
            private Node next;
    
            private Node(E elem, Node next) {
        
                this.elem = elem;
                this.next = next;
            }
    
            private Node(E elem) {
        
                this(elem, null);
            }
    
            private Node() {
        
                this(null, null);
            }
    
            @Override
            public String toString() {
        
                return elem.toString();
            }
        }
    
        private Node dummyHead; // 链表虚拟头节点
        private int size; // 链表大小
    
        // 初始化链表
        public MyLinkedList() {
        
            dummyHead = new Node();
            size = 0;
        }
    
        // 获取链表的头结点
        public Node getHead() {
        
            return dummyHead;
        }
    
        // 获取链表中的元素个数
        public int getSize() {
        
            return size;
        }
    
        // 链表是否为空
        public boolean isEmpty() {
        
            return size == 0;
        }
    
    
        // 在链表的index(0-based)位置添加新的元素elem【此操作在链表中不是一个常用的操作，仅仅练习使用】
        public void add(int index, E elem) {
        
            if (index < 0 || index > size) {
        
                throw new IllegalArgumentException("超出范围...");
            }
            Node prev = dummyHead;
            for (int i = 0; i < index; i++) {
           // 查找插入处(index处)的前一个节点
                prev = prev.next;   // 最后一个 prev.next 表示 index节点
            }
    /*            Node node = new Node(elem); // 将新元素链入链表
                node.next = prev.next;
                prev.next = node;*/
            prev.next = new Node(elem, prev.next);  // 新建一个Node节点，让该节点的next指针指向head，然后让head指向该节点【完成插入头结点的操作，和上面三行代码结果相同】
            size++;
        }
    
        // 重载添加方法，如果不写添加元素的下标，则默认添加头节点
        public void add(E elem) {
        
            addFirst(elem);
        }
    
        // 链表头添加新的元素elem
        public void addFirst(E elem) {
        
            add(0, elem);
        }
    
        // 在链表末尾添加新的元素elem
        public void addLast(E elem) throws Exception {
        
            add(size, elem);
        }
    
        // 获得链表的第index(0-based)个位置的元素【此操作在链表中不是一个常用操作，仅仅练习使用】
        public E get(int index) {
        
            if (index < 0 || index > size) {
        
                throw new IllegalArgumentException("超出范围...");
            }
            Node cur = dummyHead.next;
            for (int i = 0; i < index; i++) {
        
                cur = cur.next;
            }
            return cur.elem;
        }
    
        // 获得链表的第一个元素
        public E getFirst() {
        
            return get(0);
        }
    
        // 获得链表的最后一个元素
        public E getLast() {
        
            return get(size - 1);
        }
    
        // 修改链表的第index(0-based)个位置的元素为elem【此操作在链表中不是一个常用操作，仅仅练习使用】
        public void set(int index, E elem) {
        
            if (index < 0 || index > size) {
        
                throw new IllegalArgumentException("超出范围...");
            }
            Node cur = dummyHead.next;
            for (int i = 0; i < index; i++) {
        
                cur = cur.next;
            }
            cur.elem = elem;
        }
    
        // 查找链表中是否有元素elem
        public boolean contains(E elem) {
        
            Node cur = dummyHead.next;
            while (cur != null) {
        
                if (cur.elem.equals(elem)) {
        
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
    
        // 从链表汇总删除第index(0-based)个位置的元素【此操作在链表中不是一个常用操作，仅仅练习使用】
        public E remove(int index) {
        
            if (index < 0 || index > size) {
        
                throw new IllegalArgumentException("超出范围...");
            }
            Node prev = dummyHead;
            for (int i = 0; i < index; i++) {
        
                prev = prev.next;
            }
            Node retNode = prev.next;   // retNode代表待删除节点
            prev.next = retNode.next;   // 将待删除节点的前一个节点的next指向待删除节点的下一个节点
            retNode.next = null;   // 将待删除节点的next指向null
            size--;
    
            return retNode.elem;
        }
    
        // 删除链表中该元素的节点
        public void remove(E elem) {
        
            if (elem == null) {
        
                return;
            }
            Node prev = dummyHead;
            Node node = dummyHead.next;
            while (node != null) {
        
                if (elem.equals(node.elem)) {
        
                    prev.next = node.next;
                    node.next = null;
                    size--;
                    break;
                }
                prev = prev.next;
                node = node.next;
            }
        }
    
        // 从链表中删除第一个元素，返回删除的元素
        public E removeFirst() {
        
            return remove(0);
        }
    
        // 从链表中删除最后一个元素，返回删除的元素
        public E removeLast() {
        
            return remove(size - 1);
        }
    
    
        @Override
        public String toString() {
        
            StringBuilder string = new StringBuilder();
    //        for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
        
    //            string.append(cur + "->");
    //        }
            Node cur = dummyHead.next;
            while (cur != null) {
        
                string.append(cur + "->");
                cur = cur.next;
            }
            string.append("NULL");
    
            return string.toString();
        }
    
    
    }

MyLinkedListStack.java

/**
     * @name MyLinkedListStack
     * @description 基于链表的栈
     */
    public class MyLinkedListStack<T> implements MyStack<T> {
        
    
        private MyLinkedList<T> list;
    
        public MyLinkedListStack(){
        
            list = new MyLinkedList<>();
        }
    
        @Override
        public int getCapacity() {
        
            return 0;
        }
    
        @Override
        public int getSize() {
        
            return list.getSize();
        }
    
        @Override
        public void push(T element) {
        
            list.addFirst(element);
        }
    
        @Override
        public T pop() {
        
            return list.removeFirst();
        }
    
        @Override
        public T peek() {
        
            return list.getFirst();
        }
    
        @Override
        public boolean isEmpty() {
        
            return list.isEmpty();
        }
    
        @Override
        public String toString() {
        
            StringBuilder string = new StringBuilder();
            string.append("Stack: top ");
            string.append(list);
            return string.toString();
        }
    }

Main.java

public class Main {
        
        public static void main(String[] args){
        
            MyStack<String> stack = new MyLinkedListStack<>();
            System.out.println("stack.getCapacity() = " + stack.getCapacity());
            System.out.println("stack.getSize() = " + stack.getSize());
            System.out.println("stack.isEmpty() = " + stack.isEmpty());
            System.out.println("stack = " + stack);
            System.out.println("========================================================================================");
    
            stack.push("a");
            stack.push("b");
            stack.push("c");
            System.out.println("stack.getCapacity() = " + stack.getCapacity());
            System.out.println("stack.getSize() = " + stack.getSize());
            System.out.println("stack.isEmpty() = " + stack.isEmpty());
            System.out.println("stack = " + stack);
            System.out.println("========================================================================================");
    
            System.out.println("返回栈顶元素：stack.peek() = " + stack.peek());
            System.out.println("stack.getCapacity() = " + stack.getCapacity());
            System.out.println("stack.getSize() = " + stack.getSize());
            System.out.println("stack.isEmpty() = " + stack.isEmpty());
            System.out.println("stack = " + stack);
            System.out.println("========================================================================================");
    
            System.out.println("弹出栈顶元素：stack.pop() = " + stack.pop());
            System.out.println("stack.getCapacity() = " + stack.getCapacity());
            System.out.println("stack.getSize() = " + stack.getSize());
            System.out.println("stack.isEmpty() = " + stack.isEmpty());
            System.out.println("stack = " + stack);
            System.out.println("========================================================================================");
    
            MyLinkedListStack stack02 = new MyLinkedListStack();
            for(int i = 0; i< 5; i++){
        
                stack02.push(i);
                System.out.println(stack02);
            }
            System.out.println("========================================================================================");
            stack02.pop();
            System.out.println(stack02);
            System.out.println("========================================================================================");
        }
    }

输出结果：

stack.getCapacity() = 0
    stack.getSize() = 0
    stack.isEmpty() = true
    stack = Stack: top null
    ========================================================================================
    stack.getCapacity() = 0
    stack.getSize() = 3
    stack.isEmpty() = false
    stack = Stack: top c->b->a->null
    ========================================================================================
    返回栈顶元素：stack.peek() = c
    stack.getCapacity() = 0
    stack.getSize() = 3
    stack.isEmpty() = false
    stack = Stack: top c->b->a->null
    ========================================================================================
    弹出栈顶元素：stack.pop() = c
    stack.getCapacity() = 0
    stack.getSize() = 2
    stack.isEmpty() = false
    stack = Stack: top b->a->null
    ========================================================================================
    Stack: top 0->null
    Stack: top 1->0->null
    Stack: top 2->1->0->null
    Stack: top 3->2->1->0->null
    Stack: top 4->3->2->1->0->null
    ========================================================================================
    Stack: top 3->2->1->0->null
    ========================================================================================
    
    Process finished with exit code 0

python代码：

class Stack(object):
        """栈"""
    
        def __init__(self):
            self.__items = []
    
        def is_empty(self):
            """判断栈是否为空"""
            return self.__items == []
    
        def push(self, item):
            """加入一个新的元素item到栈顶"""
            # self.__items .insert(0,item)  # 往items这个list的头部添加新元素（时间复杂度为O(n)）
            self.__items.append(item)  # 往items这个list的尾部添加新元素（时间复杂度为O(1)）
    
        def pop(self):
            """弹出栈顶元素"""
            return self.__items.pop()  # 从items这个list的尾部取出一个元素（时间复杂度为O(1)）
    
        def peek(self):
            """返回栈顶元素"""
            if self.__items:
                return self.__items[- 1]  # 展示items这个list的尾部元素
            else:
                return None
    
        def size(self):
            """返回栈的大小"""
            return len(self.__items)  # 展示items这个list的长度
    
    
    if __name__ == "__main__":
        stack = Stack()
        stack.push(1)
        stack.push(2)
        stack.push(3)
        print('栈的大小', stack.size())
        print('返回栈顶元素', stack.peek())
        print('弹出栈顶元素', stack.pop())
        print('弹出栈顶元素', stack.pop())
        print('弹出栈顶元素', stack.pop())

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/2020102621573222.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210501152957742.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center