一、什么是栈

  栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
  栈是一个元素先进后出的数据结构,我们可以把栈结构理解成手枪的弹夹。入栈就是就是将子弹压入弹夹中,后压的子弹总是在先压的子弹上面;而出栈就是开枪,先打出的子弹总是弹夹最上放的子弹,即后压入的子弹;所以先压进的子弹总是最后打出。

二、定义栈接口

  栈是一种特殊的线性表,所以栈的接口也继承我们之前定义的 MyList 接口,IStack 接口包含一些栈的基本操作。

 1public interface IStack<T> extends MyList<T> {
 2    /**
 3     * 元素入栈
 4     */
 5    void push(T e);
 6
 7    /**
 8     * 弹出栈顶
 9     */
10    T pop();
11
12    /**
13     * 是否空栈
14     */
15    boolean empty();
16
17    /**
18     * 栈内元素个数
19     */
20    @Override
21    int getSize();
22
23    /**
24     * 查看栈顶元素,不弹出
25     */
26    T peek();
27}

三、栈的实现

  数据的存储结构有两种:顺序存储结构和链式存储结构。堆栈只能对栈首进行操作(入栈/出栈),所以底层的存储结构用链表比数组更好些。为了方便获取元素的前驱,我们使用双链表来实现栈。我们只需要将栈的实现类继承 DoubleLinkedList 类就可以使用双链表进行存储栈的数据了。(DoubleLinkedList 类是我们上一篇双链表的实现类)

1public class MyStack<T> extends DoubleLinkedList<T> implements IStack<T> {
2}
1、入栈

  入栈就是向栈的最上方添加元素,等同于向链表末尾添加元素,所以我们只需要调用双链表的 add 方法即可。

1    @Override
2    public void push(T e) {
3        super.add(e);
4    }
2、出栈

  出栈包含两个操作:获取栈顶元素并将其删除;也就是获取链尾结点并将其删除。

 1    @Override
 2    public T pop() {
 3        if (size <= 0) {
 4            // 如果没有元素直接抛异常
 5            throw new EmptyStackException();
 6        }
 7        // 获取链表尾部结点即栈顶元素
 8        ListNode<T> the = last.pre;
 9        T res = the.data;
10        // 将链表尾部结点的前面结点作为尾部结点
11        the.pre.next = last;
12        // 重新设置尾部哑元的指针
13        last.pre = the.pre;
14        the.next = null;
15        the.pre = null;
16        size--;
17        return res;
18    }
3、其他方法

  MyStack 类完整的代码如下:

 1public class MyStack<T> extends DoubleLinkedList<T> implements IStack<T> {
 2    @Override
 3    public void push(T e) {
 4        super.add(e);
 5    }
 6
 7    @Override
 8    public T pop() {
 9        if (size <= 0) {
10            // 如果没有元素直接抛异常
11            throw new EmptyStackException();
12        }
13        // 获取链表尾部结点即栈顶元素
14        ListNode<T> the = last.pre;
15        T res = the.data;
16        // 将链表尾部结点的前面结点作为尾部结点
17        the.pre.next = last;
18        // 重新设置尾部哑元的指针
19        last.pre = the.pre;
20        the.next = null;
21        the.pre = null;
22        size--;
23        return res;
24    }
25
26    @Override
27    public boolean empty() {
28        return getSize() == 0;
29    }
30
31    @Override
32    public T peek() {
33        if (size <= 0) {
34            throw new EmptyStackException();
35        }
36        return last.pre.data;
37    }
38}

四、关于栈的练习题

1、判断链表是不是回文链表

  所谓回文链表就是顺序读和逆序读的结果一样,如果链表中的结点没有指向前驱,我们可以用栈结构来实现。

  定义两个指针,慢指针一次移动一个节点,快指针一次移动两个节点。当快指针指向结尾时,慢指针指向链表的中间,循环也就结束了。在移动的过程中,将慢指针指向的元素全部入栈,然后继续移动慢指针和栈中的元素进行比较即可。注意:对链表长度的奇偶性进行处理。

 1public static boolean isPalindrome(ListNode<Integer> head) {
 2        if (head == null) {
 3            return false;
 4        }
 5        // 如果只有一个元素直接返回 true
 6        if (head.next == null) {
 7            return true;
 8        }
 9        // 定义两个指针,慢指针一次移动一个节点,快指针一次移动两个节点
10        // 当快指针指向结尾时,慢指针指向链表的中间
11        ListNode<Integer> slower = head;
12        ListNode<Integer> faster = head;
13        // 创建一个栈用于存储链表的前半部分
14        Stack<Integer> stack = new Stack<>();
15        // 判断链表的长度的奇偶数 true 为奇数
16        boolean isOdd = true;
17        while (faster != null && faster.next != null) {
18            // 每次将慢指针的元素压入栈底
19            stack.push(slower.data);
20            slower = slower.next;
21            faster = faster.next.next;
22            if (faster == null) {
23                isOdd = false;
24            }
25        }
26        // 奇数个节点,slower 还要 next 一下
27        if (isOdd) {
28            slower = slower.next;
29        }
30        while (!stack.empty() && slower!=null) {
31            // 每次将栈顶元素弹出与慢指针指向的后半链表的节点比较,不相等则不是回文
32            if (!stack.pop().equals(slower.data)) {
33                return false;
34            } else {
35                slower = slower.next;
36            }
37        }
38        return true;
39    }
2、O(1)获取栈的最小值

  请设计一个栈,支持 min 方法,可返回栈元素中的最小值。时间复杂度必须为 O(1)。再用一个栈存储最小值。

 1/**
 2     * 这个栈用于存储最小值
 3     */
 4    private MyQueue<T> min=new MyQueue<T>();
 5
 6    public T min(){
 7        // 每次获得栈顶元素
 8        return min.peek();
 9        // 每次添加元素时,和这个栈顶元素做比较,小于等于则存储
10        // 每次弹出元素时,和这个栈顶元素做比较,等于则也将该栈中的元素弹出
11    }
3、栈排序

  请编写一个程序,按升序多栈进行排序(即最大元素位于栈顶),要求最多只能使用一个额外的栈存放临时数据,但不得将元素复制到别的数据结构中。给定一个 int[] numbers,其中第一个元素为栈顶,请返回排序后的栈,请注意这是一个栈,意味着排序过程你只能访问第一个元素。

例子:

  • 输入:[1, 2, 3, 4, 5]
  • 输出:[5, 4, 3, 2, 1]
 1    public static ArrayList<Integer> twoStackSort(int[] numbers) {
 2        Stack<Integer> source = new Stack<>();
 3        // 第一个元素作为栈顶进行初始化栈
 4        for (int i = numbers.length - 1; i >= 0; i--) {
 5            source.push(numbers[i]);
 6        }
 7        // 对栈进行排序
 8        Stack<Integer> target = sortToTarget(source);
 9        ArrayList<Integer> list = new ArrayList<>();
10        // 第一个元素作为栈顶
11        while (!target.empty()) {
12            list.add(target.pop());
13        }
14        return list;
15    }
16
17
18    private static Stack<Integer> sortToTarget(Stack<Integer> source) {
19        // 创建一个临时栈
20        Stack<Integer> target = new Stack<>();
21        // 遍历原栈进行排序
22        while (!source.empty()) {
23            // 揭开盖子 即弹出栈顶元素
24            int v1 = source.pop();
25            // 如果临时栈为空则直接压入
26            if (!target.empty()) {
27                // 取出临时栈的栈顶元素
28                int v2 = target.peek();
29                if (v1 < v2) {
30                    // 如果盖子小,把大的先回收
31                    source.push(target.pop());
32                    // 直到有盖子的容身之所
33                    while (!target.empty() && v1 < target.peek()) {
34                        source.push(target.pop());
35                    }
36                }
37            }
38            // 把盖子放入临时栈中
39            target.push(v1);
40        }
41        return target;
42    }

标题:栈(先进后出表)
作者:Yi-Xing
地址:http://zyxwmj.top/articles/2020/03/02/1583160485980.html
博客中若有不恰当的地方,请您一定要告诉我。前路崎岖,望我们可以互相帮助,并肩前行!