【数据结构】栈和队列

目录

一、栈

1、栈的定义

 2、栈的模拟实现（顺序栈）

1、创建一个顺序结构的栈

2、实现压栈方法（push）

3、模拟实现pop方法（出栈）

4、模拟实现peek(查看)

5、测试上述方法

3、栈的应用场景 

1、改变元素的序列

 2、逆序打印链表

3、逆波兰表达式求值（后缀表达式求值）

 4、括号匹配

5、出栈入栈次序匹配

6、最小栈

4、栈的链式存储结构

1、链栈优点

 2、实现链栈的进栈和出栈

二、对列

1、概念

 2、队列的基本方法

3、链式对列的模拟实现

1、单链表实现队列

2、使用双链表实现队列

3、单链表模拟实现队列

4、对列的顺序存储结构

1、循环队列

4、双端队列

1、定义

5、Java集合的使用

三、 栈和队列的练习

1、用队列实现栈

 2、用栈实现队列

---

一、栈

1、栈的定义

• 栈：一种特殊的线性表，其只允许在固定的一段进行插入和删除元素操作。
• 栈顶（Top）:线性表允许进行插入删除的那一端。
• 栈底（Bottom）:固定的，不允许进行插入和删除的另一端。
• 空栈：不含任何元素的空表。

栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

• 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
• 出战：栈的删除操作叫做出栈，出数据在栈顶。

---

 2、栈的模拟实现（顺序栈）

方法	功能
Stack()	构造一个空的栈
E   push（E   e）	将e入栈，并返回e
E    pop()	将栈顶元素出栈并返回
E   peek()	查看栈顶元素
int  size()	获取栈中有效元素个数
boolean   empty()	检测栈是否为空

1、创建一个顺序结构的栈

public class MyStack {public int[] elem;public int usedSize;public MyStack(){this.elem = new int[10];}
}

2、实现压栈方法（push）

    //压栈public void push(int val){if(isFull()){//扩容elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize++] = val;//后置++,先赋值，后运算}public boolean isFull(){//判断栈是否已满return usedSize == elem.length;}

---

3、模拟实现pop方法（出栈）

    //出栈public int pop(){if(isEmpty()){//栈为空，报异常throw new EmptyException("栈是空的!");}
//写法一：int val = elem[usedSize-1];usedSize--;
//写法二：// int val = elem[--usedSize];//因为usedSize记录的是元素的个数，先减1，得到数组的最后一个元素的下标return val;//返回出栈元素}public boolean isEmpty(){return usedSize == 0;}

---

4、模拟实现peek(查看)

因为只是查看栈顶元素，所以usedSize不变。

    public int peek(){if(isEmpty()){throw new EmptyException("栈是空的！");}return elem[usedSize - 1];}

5、测试上述方法

public class Test {public static void main(String[] args) {MyStack stack = new MyStack();stack.push(1);//进栈stack.push(7);stack.push(6);stack.push(8);Integer a = stack.pop();//出栈System.out.println(a);Integer b = stack.peek();//查看System.out.println(b);Integer b2 = stack.peek();System.out.println(b2);System.out.println(stack.isEmpty());//查看栈是否为空}

---

3、栈的应用场景 

1、改变元素的序列

1️⃣. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（C）

A: 1,4,3,2                        B: 2,3,4,1                      C: 3,1,4,2                     D: 3,4,2,1

2️⃣.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序（B）。

A: 12345ABCDE          B: EDCBA54321          C：ABCDE12345              D: 54321EDCBA

 2、逆序打印链表

1、递归的方式，逆序打印链表

在归的时候，才会打印链表的值，回归的时候从后往前，这样就实现了逆序打印链表

public class MySingleLIst {class Node{public int val;//存储数据public Node next;//存储下一个节点的地址public Node(int val) {this.val  = val;}}public Node head;//递归打印链表public void display(Node pHead){if(pHead == null){//pHead为空return;}if(pHead.next == null){//pHead只有一个节点System.out.print(pHead.val+" ");}//上述两个if可以做为递归的结束条件display(pHead.next);//自己调用自己，递归}
}

 2、通过栈的方式，逆序输出

    public void display1() {//将链表当中的节点保存在栈中Stack<Node> stack = new Stack<>();//申请一个栈，这个栈中放的是一个一个的节点Node cur = head;
//在进行测试的时候通过链表的方式，将值放入链表的节点当中while (cur != null) {//cur遍历链表，若链表不为空，将cur所指的节点放入到栈中stack.push(cur);cur = cur.next;//向后走}//遍历栈while (!stack.isEmpty()) {Node top = stack.pop();System.out.println(top.val + " ");}System.out.println();}

---

3、逆波兰表达式求值（后缀表达式求值）

逆波兰表达式求值也叫后缀表达式求值，将中缀表达式转为后缀表达式。

中缀表达式：我们平时常写的表达式，例如：1+((2+3)*4)-5

后缀表达式：将上述的中缀表达式转为后缀表达式为：1 2 3 + 4 * + 5 -

中缀表达式转后缀表达式1+((2+3)*4)-5

• 第一步：添加括号

• 第二步：挪动运算符号，到相应的括号外

 

• 第三步：去掉括号

后缀表达式求值的算法思想：

从左至右扫描表达式，遇到数字时，将数字压入栈，遇到运算符时，弹出栈顶的两个数，用运算符对他们做相应的计算（此顶元素  —> 运算符 —>栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得到的值即为表达式的结果。

举例：1 2 3 + 4 * + 5 -

扫描到的元素	栈的状态（栈底 ->栈顶）	说明
1	1	数字，入栈，读取下一个元素
2	1 2	数字，入栈，读取下一个元素
3	1 2 3	数字，入栈，读取下一个元素
+	1 5	运算符，弹出两个操作数进行计算2+3=5，结果入栈
4	1 5 4	数字，入栈，读取下一个元素
*	1   20	运算符，弹出两个操作数进行计算5*4= 20，结果入栈。
+	21	运算符，弹出两个操作数进行计算1+20=21，结果入栈
5	21    5	数字，入栈，读取下一个元素
-	16	运算符，弹出两个操作数21-5 = 16，结果入栈
结束	16	串已读完，结果为栈中唯一的元素

❗❗❗ 注意：在将元素压入栈中之后，读取下一个数据的时候，遇到的是运算符，弹出操作数的时候，将栈顶元素放在运算符的右边，次顶元素放在运算符的左边。

【代码示例】

public class Test { public int evalRPN(String[] tokens){Stack<Integer> stack = new Stack<>();for(String x:tokens){//循环遍历元素if(!isOperation(x)){//判断不是运算符stack.push(Integer.parseInt(x));//x在遍历的时候定义的String类型，要放入栈中，栈指定的类型是Integer，需要将其转为整数}else{//若是运算符int num2 = stack.pop();int num1 = stack.pop();switch(x){//判断运算符是那个运算符case "+":stack.push(num1+num2);break;case "-":stack.push(num1-num2);break;case "*":stack.push(num1*num2);break;case "/":stack.push(num1/num2);break;}}}return stack.pop();//当上述运算完之后，直接返回栈中的栈顶元素，因为栈中只剩下运算的结果}//判断是否为运算符private boolean isOperation(String x){if(x.equals("+") || x.equals("-") || x.equals("/") || x.equals("*")){return true;}return false;}
}

---

 4、括号匹配

先来看一下不匹配的情况

 【代码思路】

• 这个问题使用栈来解决，规定将左括号放入栈中，
• 当遇到右括号的时候将栈中的栈顶元素弹出，
• 若两个括号匹配，就进行下一组比较，
• 若不匹配，程序结束

【代码示例】 

public class Test { public boolean isValid(String s){Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);//若ch拿到左括号，入栈；若ch拿到右括号，则继续向下走，if(ch =='{' || ch == '[' || ch == '('){//如果都是左括号入栈stack.push(ch);}else{//如果遇到右括号if(stack.empty()){//判断栈空还是不空，若空，则是右括号多return false;}
//通过将ch拿到的值和ch2拿到的值，比较若拼配弹出，不匹配结束。char ch2 = stack.peek();//若不是空，则通过查看操作来看一下if(ch2 == '('&& ch == ')' || ch2 =='{'&& ch == '}'|| ch2 == '[' && ch ==']' ){stack.pop();}else{return false;}}}if(!stack.empty()){//判断栈，若不为空，返回falsereturn false;}return true;//若为空，返回true}
}

---

5、出栈入栈次序匹配

【题目描述】

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

 【解题思路】

给定两个整数序列，第一个序列表示入栈，第二个用来和入栈后的栈顶元素相比较，若相等则出栈，若不想等则结束代码。

【代码示例】 

public class Test {public boolean isPopOrder(int [] pushA,int [] popA ){if(pushA == null){return false;}if(popA == null){return false;}Stack<Integer> stack = new Stack<>();int j = 0;//通过遍历将pushA的值压入栈中，压一个值，和popA中一个值比较一次for (int i = 0; i < pushA.length; i++) {stack.push(pushA[i]);while(j < popA.length && !stack.empty() && stack.peek().equals(popA[j])){stack.pop();j++;}}return stack.empty();//最后检查栈是否为空}
}

【画图理解】 

---

6、最小栈

【题目要求】

设计一个支持 push ，pop ，teek 操作，并能在常数时间内检索到最小元素的栈。常数时间内，要求的是编写这个方法的时间复杂度为O(1).

【代码思路】

 【代码示例】

import java.util.Stack;
public 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 {//如果最小栈中有值if (val <= minStack.peek()) {//如果val小于等于最小栈的栈顶元素minStack.push(val);}}}public void pop() {if(!stack.empty()){//若普通栈不为空，才能将栈中元素弹出int val = stack.pop();//这里发生了拆箱，数值范围扩大，在下面比较的时候可以直接使用==，若val是Integer类型是，可以使用equals来比较//维护最小栈if(val == minStack.peek()) {minStack.pop();}}}//这个方法就是查看栈中的元素public int top() {if(!stack.empty()) {//栈不为空，进入return stack.peek();//返回查看到的栈顶元素}return -1;//栈为空，返回-1}public int getMin() {return minStack.peek();//获取最小元素，直接返回最小栈的栈顶元素}
}

---

4、栈的链式存储结构

• 我们不仅可以使用顺序表实现栈，也可以通过链表来实现栈。
• 以单链表实现栈为例：可以从链表的头部也可以是尾部插入或删除节点，实现进栈和出栈。
• 但是我们以顺序表实现栈的时候，进栈和出栈时间复杂度都为O(1)，那么这里我们就需要考虑用单链表实现栈的时候时间复杂度是否也可以达到O(1)。当然双链表实现栈的时候，时间复杂度就是O(1)，由于双链表存在一个last指针永远指向链表的结尾，所以删除和插入节点，都不需要遍历链表，时间复杂度为O(1).
• 下面我们来了解一下单链表实现栈，单链表实现栈通过头插法和头删法来实现栈的入栈和出栈

1、链栈优点

采用链式存储的栈称为链栈，链栈的优点是便于斗个栈构想存储空间和提高其效率，且不存在栈满的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。

 2、实现链栈的进栈和出栈

• 由于栈是先进后出的原则，所以用单链表实现的时候，从头部插入，头部删除。
• 进栈使用的头插法。
• 出栈的时候使用的头删法，使用headNext记录下一个节点，将首节点删除之后，head要引用新的首节点。

public class MySingleLIst {class Node {public int val;//存储数据public Node next;//存储下一个节点的地址public Node(int val) {this.val = val;}}public Node head;//进栈public void push(int val) {Node node = new Node(val);node.next = head;node = head;}//出栈public Object pop() {if (head == null) {return null;}Node headNext = head.next;head.next = null;head = headNext;headNext = headNext.next;return head.val;}

---

二、对列

1、概念

队列：只允许在一段进行插入数据操作，在另一端进行删除操作的特殊线性表。

队列具有先进先出FIFO(Frist In Frist Out)

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

出队列：进行删除操作的一段称为队头（Head/Front）

 2、队列的基本方法

方法	功能
boolean     offer(E e)	入队列
E   poll()	出队列
peek()	获取队头元素
int   size()	获取队列中的有效元素个数
boolean  isEmpty()	检测队列是否为空

3、链式对列的模拟实现

1、单链表实现队列

单链表实现队列：使用last记录单链表的最后一个节点，在队头使用头删法出队列，队尾使用尾插法进入队列 。这样可以保证在进行出入队列时，时间复杂度为O(1).

❗❗❗注意：这种实现队列的方式还是有一定的局限性，他只能从尾巴插入，头部删除。

---

2、使用双链表实现队列

双向链表实现队列：链表的头和尾都可以实现进入队列和删除队列，他的时间复杂度为O(1)

 ❗❗❗注释：

• 所以说双向链表是最常用的链表。
• 因为双向链表实现队列非常简单，只需要在模拟实现双向链表的时候，加入头删法和尾删法，就可以用双向链表实现队列。
• 这里我们用单链表来模拟实现队列

---

3、单链表模拟实现队列

public class MyQueue {//实现队列static class Node {//实现队列当中的节点public int val;public Node next;public Node(int val) {this.val = val;}}public Node head;public Node last;public int usedSize;//入队public void offer(int val) {Node node = new Node(val);if (head == null) {//当没有单链表的时候，插入一个节点，head和last都指向这个节点。head = node;last = node;} else {//当链表不为空的时候，尾插法实现入栈last.next = node;//链接node节点last = node;//last指针后移}usedSize++;//记录队列当中有多少个元素}//出队public int poll(){if(empty()){//队列是否为空，若为空返回-1或者抛异常，不为空，将元素抛出。//这里可以抛异常，也可以直接返回-1return -1;//若链表为空，则返回-1.}int ret = head.val;//将出队列的值，记录下来head = head.next;//将head引用向后移，头节点没有被引用，别回收，实现了出队的操作if(head == null){//当head后移，将元素删完head=null时，队列当中应该没有元素了所
//以last也要置为空，否则last还引用队列当中的元素,理论上对列没有空。但是这个方法有
//usedSize计数，不加if判断最终实现的效果上，没有问题last = null;}           usedSize--;return ret;}public boolean empty(){//判断链表是否为空return usedSize == 0;}//查看队头元素public int peek(){if(empty()){throw new EmptyException("队列为空");}return head.val;}//查看队列当中的元素个数public int getUsedSize(){return usedSize;}
}

测试：

public class Test {public static void main(String[] args) {MyQueue myQueue = new MyQueue();myQueue.offer(1);myQueue.offer(2);myQueue.offer(3);myQueue.offer(4);System.out.println(myQueue.peek());System.out.println(myQueue.poll());System.out.println(myQueue.getUsedSize());}

---

4、对列的顺序存储结构

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素。队尾指针rear指向队尾元素的下一个位置。

通过数组模拟入队列时的操作

模拟出队列时的操作 

•  顺序队列的缺点就是会出现假溢出的问题。
• 为了解决顺序队列的“假溢出”也就是空间只能用一次，严重浪费的问题，数据结构引出了循环队列的概念

---

1、循环队列

循环队列就是将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环。

通过上图可以看到当队列为空或者满的时候， 队头指针（front）和队尾指针（rear）都会指向同一个节点，换句话说两个指针会重合。那么这里就会产生两个问题

• ❓❓❓rear从7下标到0下标或者说两个指针相遇，此时队列到底是空还是满？？
• ❓❓❓循环队列实际上还是以数组的形式实现的，环形只不过是方便了理解臆造的。rear从7下标如何到0下标？？

 第一个问题判断队列是否已满。

1. 第一种方法：在实现循环对列的时候，定义一个usedSize，用来记录数组中元素的个数，想要判断循环对列是否已满，可以直接输出usedSzie的值，进行判断。这种方法不浪费空间。
2. 第二种方法：牺牲一个空间，如上图，当rear走到7下标位置，判断rear的下一个位置是否为front，若是，则判断队列已满，若不是队列没满。

 第二个问题从7下标如何到0下标位置，这个问题的解决前提就是牺牲一个空间的方法

rear存在从7下标位置到0下标位置，同样在出队列的时候front也存在这样的问题。

这里使用取余的方式rear = (rear + 1)%array.len ，添加几个元素，则rear向后挪动几步，因为取余，1%8 =1，2%8=2...9%8 = 1。当除数小于被除数时，结果都是除数本身。

总结：

判断队列是否已满的问题，也是可以通过第二个问题当中的公式来进行判断的，

（rear+1）%array.len == front 

 【代码示例】

public 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) {//1、检查队列是否已满if(isFull()){return false;}//2、没满elem[rear] =value;//这里不能使用++后移，在走到最后一个下标位置的时候，通过++，结果不会变为0后移就会数组越界。//rear++;//这种写法，当rear走到最后一个位置的时候，取余之后结果为0，rear指向0下标位置rear = (rear+1)%elem.length;return false;}//出队列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;//判断若只有一个元素,则用elem.length - 1计算数组下标，若数组中有多个元素，则使用rear - 1来计算数组下标return elem[index];}//判断是否为空public boolean isEmpty() {return front == rear;}//判断是否已满public boolean isFull() {
//        if((rear+1)%elem.length ==front){
//            return true;
//        }
//        return false;return (rear+1)%elem.length ==front;
//这里两种写法都可以}
}

---

4、双端队列

1、定义

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，如下图所示。其元素的逻辑结构仍是线性结构。将队列的两端给别成为前端和后端，两端都可以入队和出队。

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

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

由于ArrayDeque和ListedList都实现了Deque接口，所以双端队列可以实现链式的，也可以实现线性结构的

Deque<Integer> queue1 = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue2 = new LinkedList<>();//双端队列的链式实现

---

5、Java集合的使用

通过之前的学习，我们知道通过LinkedList可以实现很多数据结构，

比如通过LinkedList实现链表，栈，队列。

Deque<Integer> deque = new LinkedList<>();//此时LinkedList就被当作了双端队列
Queue<Integer> queue = new LinkedList<>();//此时LinkedList就被当作了普通队列
LinkedList<Integer> stack = new LinkedList<>();//此时LinkedList就被当做了链式栈
List<Integer> list = new LinkedList<>();//此时LinkedList被当作了链表（单向、双向）

LinkedList当中这些数据结构的方法都存在，使用的时候只需要调用相应的数据结构的方法就行。

---

三、 栈和队列的练习

1、用队列实现栈

队列数据的操作方式是：先进的先出，栈的数据操作方式是：先进的后出。

两种数据结构的操作方式是相反的，所以要用队列实现栈，那么就要用两个队列来实现。

import java.util.LinkedList;
import java.util.Queue;public class MyStack2 {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack2() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}//入队列public void push(int x) {if(!qu1.isEmpty()){//qu1不为空qu1.offer(x);}else if(!qu2.isEmpty()){//qu2不为空qu2.offer(x);}else{//qu1和qu2都为空qu1.offer(x);}}//出队列public int pop() {if(empty()){return -1;//判断两个队列都为空,意味着当前的栈为空}if(!qu1.isEmpty()){//qu1队列不为空int size = qu1.size();for(int i = 0;i < size - 1;i++){int val = qu1.poll();//记录出qu1队列的值qu2.offer(val);//将qu1中出来的值，放入到qu2中}return qu1.poll();}else{//qu2队列不为空int size = qu2.size();for(int i = 0;i < size - 1;i++){int val = qu2.poll();//记录出qu1队列的值qu2.offer(val);//将qu1中出来的值，放入到qu2中}return qu2.poll();}}//peek,查看栈顶元素public int top() {if(empty()){return -1;//判断两个队列都为空,意味着当前的栈为空}if(!qu1.isEmpty()){//qu1队列不为空int size = qu1.size();//在循环出队列的时候，队列当中的元素在减少，要使用一
//个在循环外的变量记录队列当中开始元素的个数，不能直接将qu1.size()作为循环的结束条件,
//若是将其作为循环的结束条件，则循环次数就会减少int val = -1;for(int i = 0;i < size - 1;i++){val = qu1.poll();//记录出qu1队列的值qu2.offer(val);//将qu1中出来的值，放入到qu2中}return val;}else{//qu2队列不为空int size = qu2.size();int val = -1;for(int i = 0;i < size - 1;i++){val = qu2.poll();//记录出qu1队列的值qu2.offer(val);//将qu1中出来的值，放入到qu2中}return val;}}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}}

---

 2、用栈实现队列

【代码示例】 

import java.util.Stack;
public class MyQueue2 {private Stack<Integer> stack1;private Stack<Integer> stack2;public MyQueue2() {stack1 = new Stack<>();stack2 = new Stack<>();}//入队列public void push(int x) {stack1.push(x);}//出队列public int pop() {if(empty()){//两个栈都为空，即队列为空return -1;}if(stack2.empty()){//如果第二个栈为空while(!stack1.empty()){//若第一个栈不为空，进入循环stack2.push(stack1.pop());//将第一个栈中所有的元素弹出，依次压入第二个栈中}}return stack2.pop();//弹出第二个栈中的栈顶元素，这样就实现了出队列}//查看队列的首元素public int peek() {if(empty()){//两个栈都为空，即队列为空return -1;}if(stack2.empty()){//如果第二个栈为空while(!stack1.empty()){//若第一个栈不为空，进入循环stack2.push(stack1.pop());//将第一个栈中所有的元素弹出，依次压入第二个栈中}}return stack2.peek();}public boolean empty() {return stack1.isEmpty()&&stack2.isEmpty();//判断两个栈是否都为空}
}