数据结构基础：使用数组和链表实现栈

Bertha 。 2023-10-03 16:03 34阅读 0赞

### 前传 ###

推荐一个数据可视化网站：  
[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html][https_www.cs.usfca.edu_galles_visualization_Algorithms.html]

### 一、栈概述 ###

在开始具体的编码之前，我们先聊一下栈。

栈的特点是先进后出（FILO）；举个例子：以子弹装入弹夹来看，先入弹夹的子弹总是最后射出。  
![在这里插入图片描述][e0a136eb66bb486380fa34c7e95e1e0e.png]  
**软件中的应用：**

无处不在的Undo撤销操作（编辑器）；程序调用的系统栈（例如方法里面套方法）；  
括号匹配（编译器）：左括号先进去，然后接下来的括号和栈顶括号去配对，种类和方向相反的栈顶括号被取出。

### 二、基于数组和链表实现栈 ###

#### 0、栈通用接口 ####

出于通用性的考量，我们抽象一个Stack接口，其中包括入栈、出栈、获取栈size操作；并对栈内数据进行泛型化处理。

package com.saint.base.datastructure.stack;
    
    /**
     * 栈通用接口
     *
     * @author Saint
     * @version 1.0
     * @createTime 2021-09-05 9:47
     */
    public interface Stack<E> {
        
    
        /**
         * 栈顶入栈
         * @param e
         */
        void push(E e);
    
        /**
         * 弹出栈顶元素
         * @return
         */
        E pop();
    
        /**
         * 看一眼栈顶元素
         * @return
         */
        E peek();
    
        /**
         * 获取栈的元素个数
         * @return
         */
        int getSize();
    }

#### 1、基于数组实现栈 ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qKm5Zue546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16]

package com.saint.base.datastructure.stack;
    
    /**
     * 基于数组实现的栈
     *
     * @author Saint
     * @version 1.0
     * @createTime 2021-09-05 9:54
     */
    public class ArrayStack<E extends Comparable<E>> implements Stack<E> {
        
    
        /**
         * 存储栈数据元素的容器
         */
        Object[] items;
    
        /**
         * 栈内数据元素个数
         */
        int size;
    
        public ArrayStack() {
        
            this(8);
        }
    
        public ArrayStack(int capacity) {
        
            items = new Object[capacity];
            size = 0;
        }
    
    
        @Override
        public void push(E e) {
        
            // 扩容判断
            if (size == items.length) {
        
                resize(2 * items.length);
            }
            items[size] = e;
            size++;
        }
    
        @Override
        public E pop() {
        
            E e = (E) items[size - 1];
            items[size - 1] = null;
            size--;
            if (size == items.length / 4 && size > 1) {
        
                resize(items.length / 2);
            }
            return e;
        }
    
        @Override
        public E peek() {
        
            if (size < 1) {
        
                throw new RuntimeException("Stack is empty!");
            }
            return (E) items[size - 1];
        }
    
        /**
         * 扩容/缩容操作
         *
         * @param newCapacity 数组新容量
         */
        public void resize(int newCapacity) {
        
            Object[] newItems = new Object[newCapacity];
            for (int i = 0; i < size; i++) {
        
                newItems[i] = items[i];
            }
            items = newItems;
        }
    
        @Override
        public int getSize() {
        
            return size;
        }
    
        @Override
        public String toString() {
        
            StringBuilder res = new StringBuilder();
            res.append(String.format("ArrayStack: capacity: %d, size: %d.", items.length, size));
            res.append("[");
            for (int i = 0; i < size; i++) {
        
                res.append(items[i]);
                if (i != size - 1) {
        
                    res.append(",");
                }
            }
            res.append("] top");
            return res.toString();
        }
    }

#### 2、基于链表实现 ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qKm5Zue546W5p-S_size_17_color_FFFFFF_t_70_g_se_x_16]

package com.saint.base.datastructure.stack;
    
    import com.saint.base.datastructure.Node;
    
    /**
     * @author Saint
     * @version 1.0
     * @createTime 2021-09-05 9:54
     */
    public class LinkedStack<E extends Comparable<E>> implements Stack<E>{
        
    
        /**
         * 栈顶
         */
        Node<E> head;
    
        /**
         * 栈中元素个数
         */
        int size;
    
        public LinkedStack() {
        
            head = null;
            size = 0;
        }
    
        @Override
        public void push(E e) {
        
            if (head == null) {
        
                head = new Node<>(e);
            } else {
        
                Node<E> curNode = new Node<>(e);
                curNode.next = head;
                head = curNode;
            }
            size ++;
        }
    
        @Override
        public E pop() {
        
            if (head == null) {
        
                throw new RuntimeException("Stack is empty");
            }
            Node<E> curNode = head;
            head = head.next;
            curNode.next = null;
            size --;
            return curNode.value;
        }
    
        @Override
        public E peek() {
        
            return head.value;
        }
    
        @Override
        public int getSize() {
        
            return 0;
        }
    
        @Override
        public String toString() {
        
            StringBuilder res = new StringBuilder();
            res.append(String.format("LinkedStack: size: %d. top: ", size));
            Node<E> cur = head;
            res.append("null");
            while (cur != null) {
        
                res.append(" <-- " + cur.value);
                cur = cur.next;
            }
            return res.toString();
        }
    }

#### 3、测试 ####

package com.saint.base.datastructure.stack;
    
    /**
     * @author Saint
     * @version 1.0
     * @createTime 2021-09-05 9:54
     */
    public class StackTest {
        
        public static void main(String[] args) {
        
    
            System.out.println("--------------ArrayStack-----------------");
            ArrayStack<Integer> arrayStack = new ArrayStack<>();
            for (int i = 0; i < 10; i++) {
        
                arrayStack.push(i);
                System.out.println(arrayStack);
                if (i % 3 == 0) {
        
                    arrayStack.pop();
                    System.out.println("出栈：" + arrayStack);
                }
            }
            System.out.println("-------------------------------");
    
            System.out.println("--------------LinkedStack-----------------");
            LinkedStack<Integer> linkedStack = new LinkedStack<>();
            for (int i = 0; i < 10; i++) {
        
                linkedStack.push(i);
                System.out.println(linkedStack);
                if (i % 3 == 0) {
        
                    linkedStack.pop();
                    System.out.println("出栈：" + linkedStack);
                }
            }
    
        }
    }

控制台输出：

--------------ArrayStack-----------------
    ArrayStack: capacity: 8, size: 1.[0] top
    出栈：ArrayStack: capacity: 8, size: 0.[] top
    ArrayStack: capacity: 8, size: 1.[1] top
    ArrayStack: capacity: 8, size: 2.[1,2] top
    ArrayStack: capacity: 8, size: 3.[1,2,3] top
    出栈：ArrayStack: capacity: 4, size: 2.[1,2] top
    ArrayStack: capacity: 4, size: 3.[1,2,4] top
    ArrayStack: capacity: 4, size: 4.[1,2,4,5] top
    ArrayStack: capacity: 8, size: 5.[1,2,4,5,6] top
    出栈：ArrayStack: capacity: 8, size: 4.[1,2,4,5] top
    ArrayStack: capacity: 8, size: 5.[1,2,4,5,7] top
    ArrayStack: capacity: 8, size: 6.[1,2,4,5,7,8] top
    ArrayStack: capacity: 8, size: 7.[1,2,4,5,7,8,9] top
    出栈：ArrayStack: capacity: 8, size: 6.[1,2,4,5,7,8] top
    -------------------------------
    --------------LinkedStack-----------------
    LinkedStack: size: 1. top: null <-- 0
    出栈：LinkedStack: size: 0. top: null
    LinkedStack: size: 1. top: null <-- 1
    LinkedStack: size: 2. top: null <-- 2 <-- 1
    LinkedStack: size: 3. top: null <-- 3 <-- 2 <-- 1
    出栈：LinkedStack: size: 2. top: null <-- 2 <-- 1
    LinkedStack: size: 3. top: null <-- 4 <-- 2 <-- 1
    LinkedStack: size: 4. top: null <-- 5 <-- 4 <-- 2 <-- 1
    LinkedStack: size: 5. top: null <-- 6 <-- 5 <-- 4 <-- 2 <-- 1
    出栈：LinkedStack: size: 4. top: null <-- 5 <-- 4 <-- 2 <-- 1
    LinkedStack: size: 5. top: null <-- 7 <-- 5 <-- 4 <-- 2 <-- 1
    LinkedStack: size: 6. top: null <-- 8 <-- 7 <-- 5 <-- 4 <-- 2 <-- 1
    LinkedStack: size: 7. top: null <-- 9 <-- 8 <-- 7 <-- 5 <-- 4 <-- 2 <-- 1
    出栈：LinkedStack: size: 6. top: null <-- 8 <-- 7 <-- 5 <-- 4 <-- 2 <-- 1

[https_www.cs.usfca.edu_galles_visualization_Algorithms.html]: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
[e0a136eb66bb486380fa34c7e95e1e0e.png]: https://img-blog.csdnimg.cn/e0a136eb66bb486380fa34c7e95e1e0e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qKm5Zue546W5p-S_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/0a7532265d864fe5971d16a33b5907cb.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qKm5Zue546W5p-S,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qKm5Zue546W5p-S_size_17_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/89f6d475594445ef82f0bf5108433137.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5qKm5Zue546W5p-S,size_17,color_FFFFFF,t_70,g_se,x_16