一、什么是栈
栈(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
博客中若有不恰当的地方,请您一定要告诉我。前路崎岖,望我们可以互相帮助,并肩前行!