【数据结构篇】线性表2 —— 栈和队列

前言：上一篇我们介绍了顺序表和链表

（https://blog.csdn.net/iiiiiihuang/article/details/132615465?spm=1001.2014.3001.5501），

这一篇我们将介绍栈和队列，栈和队列都是基于顺序表和链表来实现的

目录

栈（Stack）

什么是栈 ？

栈的方法 和 使用

栈的模拟实现 

先初始化一下栈 

往栈里插入元素 （push)

栈是否为空(empty)

弹出栈顶元素（删除）(pop)

获取栈顶元素 (peek)

模拟实现完整代码 

栈的应用场景

 1. 改变元素的序列

2. 将递归转化为循环

补充 ：

队列（Queue） 

什么是队列 ？

队列的方法 

队列模拟实现 

初始化 

offer 

poll

peek

完整代码（链式队列） 

循环队列 

认识循环队列 

如何把数组看作是一个循环呢？（rear 从 7 --> 0) 

设计一个循环队列 （https://leetcode.cn/problems/design-circular-queue/）

初始化 

判断队列是否是空的，和是否是满的 

入队 

 出队

得到队头元素

得到队尾元素

完整代码： （循环队列）

双端队列 (Deque)

（面试题） 1. 用队列实现栈   2. 用栈实现队列

 1. 用队列实现栈

代码实现：

入栈

出栈 

获取栈顶元素 

 判断栈空

完整代码 

 2. 用栈实现队列 

我直接上代码了： 

 

---

 

栈（Stack）

什么是栈 ？

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

后进先出原则：先进的后出，后进的先出  。我们举一个生活中的例子

比如这有个圆筒，一端封闭，一端开口，然后往圆筒里放乒乓球：

    

你想拿乒乓球，先拿到的肯定是后放的，那如果你想要拿到最底下的，你肯定得把上面的都拿走才行。也就是 栈的后进先出原则 （先进的后出，后进的先出）

栈的方法 和 使用

 栈的方法很少，只有这些： 

使用 （没什么好说的😁😁）

栈的模拟实现 

 栈这种数据结构可以用数组来实现，也可以用链表来实现，这里我们用数组实现。

先初始化一下栈 

往栈里插入元素 （push)

和顺序表异曲同工，先看看满没满，满了要扩容，再入栈 

栈是否为空(empty)

弹出栈顶元素（删除）(pop)

就很简单 （顺序表那搞懂，这些方法很简单的）

 

获取栈顶元素 (peek)

 

模拟实现完整代码 

import java.util.ArrayList;
import java.util.Arrays;/*** @Author: iiiiiihuang*/
public class MyStack {private int[] elem;private int usedSize;private static final int DEFAULT_CAPACITY = 10;//默认容积public MyStack() {this.elem = new int[DEFAULT_CAPACITY];}/*** 往栈里插入元素* @param val*/public void push(int val) {isFull();this.elem[usedSize] = val;usedSize++;}private void isFull() {if(usedSize == this.elem.length) {this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);}}/*** 弹出栈顶元素* @return*/public int pop() {if(empty()) {throw new EmptyException("栈为空");}int pop = this.elem[usedSize - 1];usedSize--;return pop;}/*** 获取栈顶元素* @return*/public int peek() {if(empty()) {System.out.println("栈为空");return 0;}int peek = this.elem[usedSize - 1];return peek;}/*** 栈是否为空* @return*/public boolean empty() {return usedSize == 0;}
}

栈的应用场景

 1. 改变元素的序列

我们去牛客上找两道题做做 

根据我们上面介绍，栈 遵循 先进后出原则， 我们可以得出答案，不可能的出栈顺序是 D 选项

因为F，E出来了，下一个出来的必须是 D，这种情况下C不可能比D先出。 

2. 将递归转化为循环
 

比如逆序打印链表： 

  1.递归方法 

 

 2.循环方法 

 

运行结果 

 

 

补充 ：

用数组实现栈，出栈，入栈，都是O(1),

那用链表如何实现栈呢？

1.假设用单链表（单向）实现栈： 

  尾插： 

      入栈：尾插法 入栈是 O(n)

      出栈：因为栈后进的先出，这就相当于删除链表的尾巴节点，时间复杂度还是O(n);

 头插： 

      入栈：头插法 O(1)

      出栈：相等于删除头节点，时间复杂度O(1)

2.假设用双向链表实现栈：  （前后都能找到）

尾插： 

      入栈：尾插法 入栈是 O(1)

      出栈：时间复杂度还是O(1)，

 头插： 

      入栈：头插法 O(1)

      出栈：时间复杂度O(1)

上述我们可知，用链表实现栈时，双向链表实现栈是最好的，不管从那边入栈，出栈 时间复杂度都是O(1)。

那使用链式栈时就可以这样使用：如果这是个栈，那peek的内容就是 4. 

 

是 4. 

 

那为啥会这样，你看LinkedList,里本来就有栈里的一些方法，push..... 

 

push 用的是头插法 

 

 

所以如果是顺序栈，你可以用Stack, 如果是链式栈，你就用LinkedList 

 

 

队列（Queue） 

什么是队列 ？

 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头

举例说明： 

假如有一条单行隧道，车辆必须从入口进 （入队列），从出口出（出队列）。那先驶出隧道的车辆肯定是先进去的，后驶出的肯定是后进去的，这就是 队列的先进先出原则

通过上述介绍，我们发现我们可以把 双向链表当成是一个 队列 ，(单链表也行，双链表更简单)

队尾进，队头出，时间复杂度O(1)

 

 ps:Queue 普通队列，Deque 双端队列（两边都可以进出），LinkedList 可以当作普通队列，双端队列，链表，栈（究极打工人😭😭😭）

队列的方法 

在Java中，Queue是个接口，底层是通过链表实现的。 

队列方法少的嘞 

 

offer (入队列) 

 

peek 

 

poll 

 

......... 

add，remove ，element (和peek一个意思）是一组 

offer,  poll,  peek 是一组

 

 

队列模拟实现 

队列的实现使用 顺序结构 和 链式结构 都行，但链式结构更简单一点。

我们这里拿双链表去写 (前面的链表学会了，这里很简单的，信手拈来）

初始化 

 

 

offer 

 

调试一看 插进去了 

 

poll

 

 

 

 

peek

 

 

 

完整代码（链式队列） 

 

/*** @Author: iiiiiihuang*/
public class MyQueue {static class ListNode {private int val;private ListNode prev;private ListNode next;public ListNode(int val) {this.val = val;}}private ListNode front;//头private ListNode rear;//尾private int usedSize;//计数/*** 插入--- 头插法* @param val*/public void offer(int val) {ListNode node = new ListNode(val);if(front == null) {front = node;rear = node;} else {node.next = front;front.prev = node;node = front;}usedSize++;}/*** 删除 -- 尾删* @return*/public int poll() {if(front == null) {throw new EmptyException("队列为空");}if(front == rear) {int poll = front.val;front = null;rear = null;usedSize--;return poll;}int poll = rear.val;rear = rear.prev;rear.next = null;usedSize--;return poll;}/*** 获取队头* @return*/public int peek() {if(front == null) {throw new EmptyException("队列为空");}return rear.val;}
}

 

循环队列
 

实际中我们有时还会使用一种队列叫循环队列。
环形队列通常使用数组实现。 

认识循环队列 

 

 

。。。。。 

 

这就有意思了 ，

front 和 rear 第一次在一起的时候 队列 是空的，第二次 在一起的时候是队列是满的

那这怎么判断呢，其实有很多方法去判断

 1.计数  usedSize == len

 2.标记，flag

 3.浪费一个空间来区分（常用） 

 浪费一个空间，就类似下面这样

 

 

如何把数组看作是一个循环呢？（rear 从 7 --> 0) 

就是把 rear ++  换成 （rear + 1 ）% len  （余数肯定都是小于 len的（len 数组长度）），rear++ 会越界的 (看不懂自己带数据算算)

 

设计一个循环队列 （https://leetcode.cn/problems/design-circular-queue/）

根据这个来 

 

 

初始化 

 

判断队列是否是空的，和是否是满的 

 

 

入队 

 

 

 出队

 

 

得到队头元素

 

得到队尾元素

 

不能直接rear - 1哦

 那现在我们放到力扣里运行一下（链接在上边）

 错了 ！！！ 为什么，我们看看我什么

 

数组容量是 3 ，预期结果成功 插入了 3个，而我们的程序，只能插入两个，因为我们的浪费掉了一个空间 。

 

所以我们应该多给一个空间： 

 

在运行一下 ，通过了，当然你要是觉得这样奇怪，你也可以用 usedSize,很多方法啦😎😎

 

完整代码： （循环队列）

class MyCircularQueue {private int[] elem;private int front;//头private int rear;//尾public MyCircularQueue(int k) {this.elem = new int[k + 1];}public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] = value;rear = (rear + 1) % elem.length;return true;}public boolean deQueue() {if(isEmpty()) {return false;}front = (front + 1) % elem.length;return true;}public int Front() {if(isEmpty()) {return -1;}int ret = elem[front];return ret;}public int Rear() {if(isEmpty()) {return -1;}int index = (rear == 0) ? elem.length - 1 : rear - 1;//不能直接rear - 1哦return elem[index];}public boolean isEmpty() {return front == rear;}public boolean isFull() {if((rear + 1) % this.elem.length == front) {return true;}return false;}
}

 

双端队列 (Deque)
 

 双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double   ended queue” 的简称。
那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

Deque是一个接口，使用时必须创建LinkedList的对象 。

 在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口

1. Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现（数组）
2. Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现 

 

（面试题） 1. 用队列实现栈   2. 用栈实现队列

 1. 用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode） 

1.首先一个栈是不够用的，它俩的出栈原则不一样，栈先进后出，队列先进先出，一个队列实现不了呀 ，对不上。

2.所以我们需要两个队列，当 2 个队列都为空的时候，说明模拟栈为空。

 

3.当要出栈的时候，（出 45 ），我们要把 12，23，34，入到第二个队列里去，然后再把第一个队列里的 45 出队列 ，

结论就是，”出栈“的时候出不为空的 队列，出队列size - 1 个（俩队列轮流），最后那一个就是我们要 ”出栈“的元素

 

 4.“入栈” 的时候入到不为空的队列

 思路有了，我们开始写代码：

代码实现：

入栈

 

出栈 

 用for 循环的时候注意一下，不要写成 i < queue.size() - 1,因为queue.size()一直在变。你先记录一下

 

获取栈顶元素 

 我们可以定义一个临时量，来存放栈顶元素

 

里面的元素一直被覆盖，那最后出队列的元素，就覆盖了之前的全部元素，就是栈顶元素。 

 

 注意：这里可别写成 queue1.offer(queue2.poll), 跳两回啦。

 判断栈空

完美通过 

 

完整代码 

 

import java.util.LinkedList;
import java.util.Queue;/*** @Author: iiiiiihuang*/
public class MyStack {private Queue<Integer> queue1;private Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}/*** 入栈操作* @param x*/public void push(int x) {if(!queue1.isEmpty()){queue1.offer(x);} else if(!queue2.isEmpty()) {queue2.offer(x);}else {queue1.offer(x);}}/*** 出栈* @return*/public int pop() {//先判断栈空不空if(empty()) {return -1;}if(!queue1.isEmpty()) {int len = queue1.size() - 1;while (len > 0) {int tmp = queue1.poll();queue2.offer(tmp);len--;}return queue1.poll();} else {int len = queue2.size() - 1;while (len > 0) {int tmp = queue2.poll();queue1.offer(tmp);len--;}return queue2.poll();}}/*** 获取栈顶元素* @return*/public int top() {int tmp = -1;if(empty()) {return -1;}if(!queue1.isEmpty()) {int len = queue1.size();while (len > 0) {tmp = queue1.poll();queue2.offer(tmp);len--;}return tmp;} else {int len = queue2.size();while (len > 0) {tmp = queue2.poll();queue1.offer(tmp);len--;}return tmp;}}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}
}

 

 2. 用栈实现队列 

232. 用栈实现队列 - 力扣（LeetCode）

思路差不多 

1.两个栈实现，同理 

2.入队的时候 把所有元素 全部放到第一个栈当中

3.出队的时候 把所有的元素 全部倒到第二个栈当中，然后出第二个栈顶元素就行了.（记得判空）

我直接上代码了： 

import java.util.Stack;/*** @Author: iiiiiihuang*/
public class MyQueue {private Stack<Integer> stack1;private Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if(empty()) {return -1;}if(stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(empty()) {return -1;}if(stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}

 

 

先别急着走，点个关注先，👀👀👀

点赞，评论，收藏，支持一下ヾ(≧▽≦*)oヾ(≧▽≦*)o