前言:上一篇我们介绍了顺序表和链表
(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文章来源:https://www.toymoban.com/news/detail-697224.html
文章来源地址https://www.toymoban.com/news/detail-697224.html
到了这里,关于【数据结构篇】线性表2 —— 栈和队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!