栈:后进先出
队列:先进先出
1. 栈(Stack)
1.1 概念
栈:是一种特殊的线性表,只允许在固定的一端插入或者删除元素,一个栈包含了栈顶和栈底。只能在栈顶插入或者删除元素。栈的底层是由数组实现的。
栈遵循先入后出原则,也就是先插入的元素得到后面才能删除,后面插入的元素比先插入的元素要更早的删除。可以理解成:后进先出
入栈:在栈顶插入元素。
出栈:在栈顶删除元素。
1.2 栈的使用
如下图,栈的常用方法有:
检查栈是否为空的意思是,看看栈里面是不是一个元素都没有。
栈的方法都挺简单,我就不一个个演示了,刷题的时候直接用即可
import java.util.Stack;
public class Main {
public static void main(String[] args) {
//创建一个栈
Stack<Integer> stack = new Stack<>();
//入栈
stack.push(1);
//看看栈顶元素但不删除
int top = stack.peek();
System.out.println(top);
//删除栈顶元素
stack.pop();
//如果栈不为空,就看看栈里有几个元素
if (!stack.empty()) {
int size = stack.size();
System.out.println(size);
}
}
}
1.3 栈的模拟实现
既然要实现一个栈,那我们可以先定义一个 MyStack 类,接下来只需要思考怎么完成 MyStack 类即可。
之前也说过,栈的底层是由一个数组实现的,所以我们可以定义一个数组,对栈进行操作就是对数组进行操作。
为了以后方便操作数组,我们还可以再定义一个 usedSize ,用来表示数组当前存放的元素个数。
因为我们待会还要提供 MyStack 的构造方法,就相当于给数组分配内存,所以我们可以定义一个默认容量,用来表示数组一开始的容量大小。
有了默认容量,我们就可以把 MyStack 的构造方法给写出来了。
栈要实现以下方法:
//入栈
public void push(int val) {
}
//出栈
public int pop() {
return -1;
}
//返回栈顶元素
public int peek() {
return -1;
}
//判空
public boolean empty() {
return false;
}
//返回栈的元素个数
public int size() {
return 0;
}
我们可以先挑最简单的实现,比如 empty 和 size。
我们先实现 empty 方法,很简单,就是看数组有没有元素咯,元素个数不为 0 ,说明栈不空。
再来实现 size 方法,这个也简单,直接返回数组元素个数就好啦。
再来实现 pop 方法,出栈,就是出栈顶元素,也就是把数组的最后一个元素给删掉,那就得先判断数组里有没有元素,根据这个再来进行删除。
usedSize-- ,之后入栈的时候会把原来的元素给覆盖掉,相当于是变相删除了这个元素
再来实现 peek 方法,这个和 pop 方法同理,只是瞄一眼栈顶元素,但是不用删除栈顶元素。
最后再来实现 push 方法,首先,你得看看数组满没满,满了就要扩容,然后再来放元素。
import java.util.Arrays;
public class MyStack {
private int[] elem;
private int usedSize;//表示当前数组存放元素个数
private static final int DEFAULT_CAPACITY = 10;//数组的默认容量
public MyStack() {
this.elem = new int[DEFAULT_CAPACITY];
}
//判空
public boolean empty() {
return this.usedSize == 0;
}
//返回栈的元素个数
public int size() {
return this.usedSize;
}
//出栈
public int pop() {
//栈为空,删不了
if (empty()) {
return -1;
}
//栈不为空,删除
int top = this.elem[this.usedSize - 1];
usedSize--;
return top;
}
//返回栈顶元素
public int peek() {
//栈为空
if (empty()) {
return -1;
}
return elem[usedSize - 1];
}
//入栈
public void push(int val) {
//数组满了,得扩容
if (this.usedSize == this.elem.length) {
//扩容
this.elem = Arrays.copyOf(this.elem, this.elem.length * 2);
}
this.elem[usedSize] = val;
usedSize++;
}
}
1.4 栈的应用场景
1. 改变元素的序列
1. 若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是()
A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1
选C
2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈,然后再依次出栈,则元素出栈的顺序是( )。
A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA
选B。
20. 有效的括号
思路:直接遍历 s ,因为是看看括号是否匹配,可以利用栈来完成,所以直接让右括号来跟左括号匹配即可
分两种情况,如果是左括号,那就直接入栈
如果是右括号,那就匹配,匹配之前得看看栈是不是为空,如果为空,说明就不匹配
如果匹配了,那就出栈。
最后遍历完 s ,如果栈为空,说明全部匹配成功,返回 true。
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
//左括号
if (ch == '(' || ch == '[' || ch == '{') {
stack.push(ch);
} else {
//右括号
if (!stack.empty()) {
char top = stack.peek();
if (top == '(' && ch == ')'
|| top == '{' && ch == '}'
|| top == '[' && ch == ']') {
stack.pop();
} else {
return false;
}
} else {
//栈为空,没有左括号
return false;
}
}
}
if (!stack.empty()) {
return false;
}
return true;
}
}
150. 逆波兰表达式求值
思路:利用栈来完成,遍历数组,如果遇到数字,那就放进栈里,如果遇到运算符,就弹出栈的两个元素,
第一个弹出的元素作为运算符的右操作数,第二个作为左操作数,将计算完的值放入栈中
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
//运算符
if (tokens[i].equals("+")
|| tokens[i].equals("-")
|| tokens[i].equals("*")
|| tokens[i].equals("/")) {
int b = stack.pop();
int a = stack.pop();
switch (tokens[i]) {
case "+":
stack.push(a + b);
break;
case "-":
stack.push(a - b);
break;
case "*":
stack.push(a * b);
break;
case "/":
stack.push(a / b);
break;
}
} else {
//数字
int tmp = Integer.parseInt(tokens[i]);
stack.push(tmp);
}
}
return stack.pop();
}
}
JZ31 栈的压入、弹出序列
你平常怎么判断出栈顺序的,现在就怎么写这个方法,思路是差不多的。
思路:这题利用栈来完成,遍历 push 数组,用 j 遍历 pop 数组,先把元素放入栈里,然后如果栈不为空并且栈顶元素和 pop[ j ] 相同的话,那就出栈,然后 j 往后走。
最后看看栈是否为空,如果为空,说明全都匹配成功,就返回 true ,否则返回 false
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pushV int整型一维数组
* @param popV int整型一维数组
* @return bool布尔型
*/
public boolean IsPopOrder(int[] push, int[] pop) {
int j = 0;
Stack<Integer> stack = new Stack<>();
//用i遍历push数组,j遍历pop数组,
//将push数组的所有数字都放入栈中,然后再peek栈
//如果peek栈的元素和pop数组的j下标元素相同
//就将该元素出栈
//遍历完i后,如果栈不是空的就返回false
for (int i = 0; i < push.length; i++) {
//入栈
stack.push(push[i]);
//匹配
while (!stack.empty() && j < pop.length && stack.peek() == pop[j]) {
stack.pop();
j++;
}
}
if (stack.empty()) {
return true;
}
return false;
}
}
155. 最小栈
思路:定义两个栈,一个就是普通的栈,一个用来存放有可能是最小值的元素的栈(简称最小栈)
构造方法就是初始化这两个栈,
push 方法,那就得判断是不是第一次入栈,如果是第一次入栈,那就两个栈都要入,如果不是第一次,那就普通栈正常入栈,而最小栈就需要判断一下,如果要入的 val 小于等于 最小栈的栈顶元素,那就入栈。
pop 方法,得看看是不是空栈,空栈出不了。如果栈不为空,那普通栈就正常出栈,但是得看看普通栈出的元素在最小栈中是否存在,如果存在,那最小栈也得出。
top 方法,看看是不是空栈,不是就正常返回栈顶元素
getMin 方法也同理。
class MinStack {
private Stack<Integer> stack;//一个是普通栈
private Stack<Integer> minStack;//一个存有可能是最小值的栈
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if (minStack.empty()) {
//如果是第一次入栈,那么两个栈都得入
minStack.push(val);
} else {
int tmp = minStack.peek();
//如果val小于等于minStack栈顶元素,那就入栈
if (val <= tmp) {
minStack.push(val);
}
}
}
public void pop() {
if (stack.empty()) {
return;
}
int top = stack.pop();
int tmp = minStack.peek();
if (tmp == top) {
//如果普通栈和最小栈元素相等,那就都得出栈
//不是的话就普通栈出栈
minStack.pop();
}
}
//获取普通栈的栈顶元素
public int top() {
if (stack.empty()) {
return -1;
}
return stack.peek();
}
//获取普通栈的栈顶元素
public int getMin() {
if (minStack.empty()) {
return -1;
}
return minStack.peek();
}
}
1.5 概念区分
2. 队列(Queue)
![数据结构之栈和队列 - 超详细的教程,手把手教你认识并运用栈和队列,数据结构,数据结构,java,开发语言,算法](https://imgs.yssmx.com/Uploads/2023/10/733040-26.png)
2.1 概念
队列:如上图,只能在队尾插入元素,队头删除元素,是一种特殊的线性表,遵循先进先出原则。
2.2 队列的使用
在Java中,Queue是个接口,底层是通过链表实现的,所以在创建对象的时候,必须实例化 LinkedList 对象。
Queue 的常见方法有:
跟栈的使用方式差不多,我就不演示啦
2.3 队列模拟实现
队列可以使用顺序结构或者链式结构实现,更推荐使用链式结构实现,因为简单
和栈同理,既然要实现队列,那就先定义一个 MyQueue 类。
同时,既然是使用链表实现,那肯定得定义一个静态内部类 ListNode。
而一个队列还有队头和队尾,所以也要定义队头和队尾。
因为要实现的方法里包含 isEmpty 方法,所以可以额外定义一个 usedSize 来记录队列的元素个数
队列要实现的方法有这些:
public void offer(int val) {
}
//出队列 相当于删除队尾结点
public int poll() {
return -1;
}
//获取队头
public int peek() {
return -1;
}
public int getUsedSize() {
return 0;
}
public boolean isEmpty() {
return false;
}
同样的,我们先选择简单的方法来实现,比如 getUsedSize 方法和 isEmpty 方法。
我们先实现 getUsedSize 方法,这个简单,直接返回 usedSize 就行。
再来实现 isEmpty 方法,判断队列是否为空,就是判断队列里usedSize是否为零。
再来实现 offer 方法,分两种情况,
一种是队列为空,说明链表里面还没有元素,也就是说新增的元素是第一个元素,所以就让 front 和 rear 都指向新增的元素即可。
第二种是队列不为空,相当于链表的头插法。
再来实现 poll 方法,
分两种情况,第一种,如果队列为空,删不了
第二种,队列不为空,就得判断,队列里面是否只有一个节点,如果只有一个节点,那删了队列就空了,如果不是只有一个节点,那就相当于删除尾巴节点。
最后实现 peek 方法,与 poll 方法类似,先看看空不空,不为空,就直接返回 top,为空,就返回 -1。
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;
public void offer(int val) {
ListNode node = new ListNode(val);
if (front == null) {
front = node;
rear = node;
} else {
//采用头插法
front.prev = node;
node.next = front;
front = node;
}
usedSize++;
}
//出队列 相当于删除队尾结点
public int poll() {
//头插尾删
if (rear == null) {
return -1;
} else if (front == rear) {
//只有一个结点
int ret = rear.val;
front = null;
rear = null;
usedSize--;
return ret;
} else {
int ret = rear.val;
rear = rear.prev;
rear.next = null;
usedSize--;
return ret;
}
}
//获取队头
public int peek() {
if (rear == null) {
return -1;
}
//因为是头插尾删,所以返回的是队尾元素
return rear.val;
}
public int getUsedSize() {
return usedSize;
}
public boolean isEmpty() {
if (usedSize == 0) {
return true;
}
return false;
}
}
2.4 循环队列
如下图,就是一个循环队列。环形队列通常使用数组实现。
该怎么区分循环队列到底满没满?
1. 可以定义一个 usedSize,如果 usedSize == elem.length,说明满了
2. 可以定义一个 flag ,如果满了,就标记为 true
3. 可以浪费一个空间,来区分
一般用第三种方法,因为比较简单。
那么该怎么让数组变成一个循环数组呢?
622. 设计循环队列
首先,循环队列的底层是一个数组,所以我们要定义一个数组,并且把 front,rear 也一起定义上。
然后实现构造方法,因为我们选择浪费一个空间来区分循环队列满没满,所以我们要多初始化一个空间给数组,不然数组就放不下那么多元素了。
再来实现 isEmpty 方法 ,如下图,很明显,当 front == rear 的时候,队列为空。
再来实现 isFull 方法 ,因为浪费了一个空间来区分满没满,根据前面讲过的,如下图:
再来实现 front 和 rear 方法
先判断空不空,不为空就返回,为空就返回 -1,返回队尾元素的时候得注意 rear 下标,假如 rear 刚好为 0 ,index = rear - 1;这显然是不对的,他的上一个应该是 len - 1下标才对,所以得做判断。
再来实现 enQueue 方法 ,首先判断满没满,没满就插入,满了就返回 false
再来实现 deQueue 方法,先判断 空不空,不空就出队头,空就返回.
class MyCircularQueue {
public int elem[];
public int front;
public int rear;//队尾进元素,所以增加元素的时候,就放到 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;
}
return elem[front];
}
public int Rear() {
if (isEmpty()) {
return -1;
}
int index = (rear == 0) ? (elem.length - 1) : (rear - 1);
return elem[index];
}
public boolean isEmpty() {
if (front == rear) {
return true;
}
return false;
}
public boolean isFull() {
if (((rear + 1) % elem.length) == front) {
return true;
}
return false;
}
}
3. 双端队列 (Deque)
双端队列,就是两边都能进行出队入队操作的队列。元素可以从队头出队和入队,也可以从队尾出队和入队。
Deque 也是一个接口,实例化的时候也要创建LinkedList的对象。
4. 练习题
225. 用队列实现栈
思路:可以使用两个队列实现,只有当两个队列都为空的时候,栈才为空,因为队列是先进先出的结构,而栈是先进后出的结构,所以出栈的时候,就得出不为空的队列,将不为空的队列的所有元素出队放到另一个队列里,最后再出一次队即可,而入栈的时候也同理,就把元素放到不为空的队列里。
class MyStack {
private Queue<Integer> qu1;
private Queue<Integer> qu2;
public MyStack() {
qu1 = new LinkedList<>();
qu2 = new LinkedList<>();
}
public void push(int x) {
//入栈的时候入到不为空的队列里
if (empty()) {
qu1.offer(x);
} else {
if (!qu1.isEmpty()) {
qu1.offer(x);
}
if (!qu2.isEmpty()) {
qu2.offer(x);
}
}
}
public int pop() {
if (empty()) {
return -1;//栈为空
}
if (!qu1.isEmpty()) {
int cnt = qu1.size() - 1;
while (cnt != 0) {
int tmp = qu1.poll();
qu2.offer(tmp);
cnt--;
}
return qu1.poll();
}
int cnt = qu2.size() - 1;
while (cnt != 0) {
int tmp = qu2.poll();
qu1.offer(tmp);
cnt--;
}
return qu2.poll();
}
public int top() {
if (empty()) {
return -1;
}
int tmp = 0;
if (!qu1.isEmpty()) {
int cnt = qu1.size();
while (cnt != 0) {
tmp = qu1.poll();
qu2.offer(tmp);
cnt--;
}
return tmp;
}
int cnt = qu2.size();
while (cnt != 0) {
tmp = qu2.poll();
qu1.offer(tmp);
cnt--;
}
return tmp;
}
public boolean empty() {
//两个队列都为空表示栈为空
if (qu1.isEmpty() && qu2.isEmpty()) {
return true;
}
return false;
}
}
232. 用栈实现队列
思路:利用两个栈来实现,假设一个叫 stack1,一个叫 stack2,简称 s1 和 s2。文章来源:https://www.toymoban.com/news/detail-733040.html
固定 入队就入 s1 ,出队首先判断队列是不是空,如果不是空,就出 s2,如果 s2 没元素,那就将 s1 的元素全部出到 s2 里,然后 s2 再来出栈。peek 也同理,只有当两个栈为空的时候,队列才为空。文章来源地址https://www.toymoban.com/news/detail-733040.html
class MyQueue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public MyQueue() {
stack1 = new Stack<>();//s1用来做输入栈
stack2 = new Stack<>();//s2用来做输出栈
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if (empty()) {
return -1;
}
if (stack2.empty()) {
int size = stack1.size();
while (size != 0) {
int tmp = stack1.pop();
stack2.push(tmp);
size--;
}
return stack2.pop();//是top元素
}
return stack2.pop();//如果s2不为空,说明之前已经按顺序弹出元素了
}
public int peek() {
if (empty()) {
return -1;
}
if (stack2.empty()) {
int size = stack1.size();
while (size != 0) {
int tmp = stack1.pop();
stack2.push(tmp);
size--;
}
return stack2.peek();//是top元素
}
return stack2.peek();
}
public boolean empty() {
if (stack1.empty() && stack2.empty()) {
return true;
}
return false;
}
}
到了这里,关于数据结构之栈和队列 - 超详细的教程,手把手教你认识并运用栈和队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!