篇章七 数据结构——栈和队列

article/2025/8/12 4:05:37

目录

1. 栈(Stack)

1.1 概念

1.图示栈概念：

2.栈在现实生活中的例子：

1.2 栈的使用

1.3 栈的模拟实现

1.接口

2.数组实现

1.4 栈的应用场景

1. 改变元素的序列

2.单链表是否可以实现栈？

2.1 数组实现：顺序栈  

2.2 链表实现：链式栈  

1. 单链表：

2. 双链表：

3.将递归转化为循环

4.括号匹配

5. 逆波兰表达式求值

6. 出栈入栈次序匹配

1.5 概念区分

栈、虚拟机栈、栈帧有什么区别呢？          

2. 队列(Queue)

2.1 概念

1.队列接口图及含义​编辑

2.2 队列的使用

2.3 队列模拟实现

2.4 循环队列

3. 双端队列 (Deque)

4. 练习

4.1 用队列实现栈。OJ链接

 4.2 用栈实现队列。OJ链接

1. 栈(Stack)

1.1 概念

1.图示栈概念：

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

 

2.栈在现实生活中的例子：

1.2 栈的使用

 

public static void main(String[] args) {Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size());   // 获取栈中有效元素个数---> 4System.out.println(s.peek());   // 获取栈顶元素---> 4s.pop();   // 4出栈，栈中剩余1   2   3，栈顶元素为3System.out.println(s.pop());   // 3出栈，栈中剩余1 2   栈顶元素为3if(s.empty()){System.out.println("栈空");}else{System.out.println(s.size());}
}

1.3 栈的模拟实现

1.接口

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。  

public class MyStack {int[] array;int size;public MyStack(){array = new int[3];}public int push(int e){ensureCapacity();array[size++] = e;return e;}public int pop(){int e = peek();size--;return e;}public int peek(){if(empty()){throw new RuntimeException("栈为空，无法获取栈顶元素");}return array[size-1];}public int size(){return size;}public boolean empty(){return 0 == size;}private void ensureCapacity(){if(size == array.length){array = Arrays.copyOf(array, size*2);}}
}

2.数组实现

注意：

        此处usedSize的值 —— pop逻辑

 

import java.util.Arrays;/*** Created with IntelliJ IDEA* Description* User: 王杰* Date: 2025-05-30* Time: 13:42*/
public class MyStack {public int[] elem;public int usedSize;public MyStack() {this.elem = new int[10];}public void push(int val) {if (isFull()) {this.elem = Arrays.copyOf(elem, 2 * elem.length);}elem[usedSize++] = val;}public boolean isFull() {return usedSize == elem.length;}public int pop() {if (isEmpty()) {throw new EmptyStackException();}int val = elem[usedSize - 1];usedSize--;return val;}public int peek() {if (isEmpty()) {return -1;}return elem[usedSize - 1];}public boolean isEmpty() {return usedSize == 0;}
}

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

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

2.单链表是否可以实现栈？

2.1 数组实现：顺序栈  

2.2 链表实现：链式栈  
1. 单链表：

2. 双链表：

LinkedList 拿双向链表实现栈

public static void main(String[] args) {LinkedList<Integer> stack = new LinkedList<>();stack.push(12);stack.push(23);stack.push(34);stack.push(45);System.out.println(stack.pop());System.out.println(stack.peek());
}

3.将递归转化为循环

逆序打印链表

// 递归方式
void printList(Node head){if(null != head){printList(head.next);System.out.print(head.val + " ");}
}
// 循环方式
void printList(Node head){if(null == head){return;}Stack<Node> s = new Stack<>();// 将链表中的结点保存在栈中Node cur = head;while(null != cur){s.push(cur);cur = cur.next;}// 将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val + " ");}
}

4.括号匹配

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.isEmpty()) {return false;}// 此时开始判断是否匹配char ch1 = stack.peek();if(ch1 == '(' && ch == ')' || ch1 == '{' && ch == '}' || ch1 == '[' && ch == ']') {stack.pop();}else {return false;}}}if(!stack.isEmpty()) {return false;}return true;}
}

5. 逆波兰表达式求值

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for(String str : tokens) {if(!isOperator(str)) {int x = Integer.parseInt(str);stack.push(x);}else {int val2 = stack.pop();int val1 = stack.pop();switch(str) {case "+":stack.push(val1 + val2);break;case "-":stack.push(val1 - val2);break;case "*":stack.push(val1 * val2);break;case "/":stack.push(val1 / val2);break;}}}return stack.pop();}private boolean isOperator(String str) {if(str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {return true;}return false;}
}

6. 出栈入栈次序匹配

 

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int j = 0;for(int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);while(!stack.empty() && j < popV.length && stack.peek() == popV[j]) {stack.pop();j++;}}return stack.empty();}
}

7.155. 最小栈 - 力扣（LeetCode）

class MinStack {public Stack<Integer> stack;public 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()) {minStack.push(val);}}}public void pop() {if(stack.empty()) {return;}int popVal = stack.pop();if(popVal == minStack.peek()) {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)

2.1 概念

1.队列接口图及含义

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）  

2.2 队列的使用

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

 

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。  

public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5);                  // 从队尾入队列System.out.println(q.size());System.out.println(q.peek());  // 获取队头元素q.poll();System.out.println(q.poll());  // 从队头出队列，并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}
}

2.3 队列模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构 和 链式结构。

此处为链表实现队列

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;/*** Created with IntelliJ IDEA* Description 栈和队列测试* User: 王杰* Date: 2025-05-30* Time: 13:36*/
public class Test {public static void main(String[] args) {MyQueue queue = new MyQueue();queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());}public static void main5(String[] args) {Queue<Integer> queue = new LinkedList<>();queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);System.out.println(queue.poll());System.out.println(queue.peek());}public static void main4(String[] args) {MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);System.out.println(minStack.getMin());minStack.pop();System.out.println(minStack.top());System.out.println(minStack.getMin());}public static void main3(String[] args) {LinkedList<Integer> stack = new LinkedList<>();stack.push(12);stack.push(23);stack.push(34);stack.push(45);System.out.println(stack.pop());System.out.println(stack.peek());}public static void main2(String[] args) {MyStack stack = new MyStack();stack.push(12);stack.push(23);stack.push(34);stack.push(45);System.out.println(stack.pop());System.out.println(stack.peek());}public static void main1(String[] args) {Stack<Integer> stack = new Stack<Integer>();stack.push(12);stack.push(23);stack.push(34);stack.push(45);System.out.println(stack.pop());System.out.println(stack.peek());}}

2.4 循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。循环队列通常使用数组实现。

此处为数组实现的循环队列

 

此处我们采用浪费一个空间的方案 

class MyCircularQueue {public int front;public int rear;public int[] elem;public MyCircularQueue(int k) {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() {return rear == front;}public boolean isFull() {return (rear + 1) % elem.length == front;}
}

3. 双端队列 (Deque)

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

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

 

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

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

4. 练习

4.1 用队列实现栈。OJ链接

 

class MyStack {public Queue<Integer> qu1;public Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList();qu2 = new LinkedList();}public void push(int x) {if(!qu1.isEmpty()) {qu1.offer(x);}else if(!qu2.isEmpty()) {qu2.offer(x);}else {qu1.offer(x);}}public int pop() {if(empty()) {return -1;}if(!qu1.isEmpty()) {int size = qu1.size();for(int i = 0; i < size - 1; i++) {qu2.offer(qu1.poll());}return qu1.poll();}else {int size = qu2.size();for(int i = 0; i < size - 1; i++) {qu1.offer(qu2.poll());}return qu2.poll();}}public int top() {if(empty()) {return -1;}if(!qu1.isEmpty()) {int size = qu1.size();int val = 0;for(int i = 0; i < size; i++) {val = qu1.poll();qu2.offer(val);}return val;}else {int size = qu2.size();int val = 0;for(int i = 0; i < size; i++) {val = qu2.poll();qu1.offer(val);}return val;}}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}

 4.2 用栈实现队列。OJ链接

注意：

        使用 isEmpty（）：统一判断是否为空的接口

 

class MyQueue {public ArrayDeque<Integer> stack1;public ArrayDeque<Integer> stack2;public MyQueue() {stack1 = new ArrayDeque<>();stack2 = new ArrayDeque<>();}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();}
}

 


http://www.hkcw.cn/article/fJbBeOdeKd.shtml

相关文章

LM393红外避障电路Multisim仿真

LM393红外避障电路Multisim仿真

电路分析&#xff1a; 开关S1模拟物体的靠近&#xff0c;当按键按下时&#xff0c;表示有物体靠近。 当没有检测到物体时&#xff08;按键没有按下&#xff09;&#xff0c;LM393D的同相端被R2拉高&#xff0c;电压为5V。 此时反相端的电压经过两个电阻分压后&#xff0c;电压…
阅读更多...
C语言进阶--文件操作

C语言进阶--文件操作

1.为什么使用文件&#xff1f; 使用文件可以将数据直接存放在电脑的硬盘上&#xff0c;做到了数据的持久化。 2.什么是文件&#xff1f; 硬盘上的文件都是文件。但是在程序化设计中&#xff0c;我们一般谈到的文件有两种&#xff1a;程序文件、数据文件&#xff08;从文件功…
阅读更多...
力扣刷题Day 66：分割回文串（131）

力扣刷题Day 66：分割回文串（131）

1.题目描述 2.思路 用了回溯的方法。首先写一个验证字符串是否是回文串的函数&#xff0c;然后遍历s&#xff0c;依次判断从当前字符到下一字符是否是回文串&#xff0c;是的话继续往后走&#xff0c;不是的话往回退。 3.代码&#xff08;Python3&#xff09; class Solutio…
阅读更多...
【IC】多角多模式信号完整性优化

【IC】多角多模式信号完整性优化

随着互连效应增强和时钟频率加快&#xff0c;串扰噪声、毛刺和意外信号延迟的发生概率也随之增加&#xff0c;信号完整性 (SI) 问题也日益凸显。由于 65 纳米和 45 纳米设计中横向导线电容的影响日益增大&#xff0c;与 SI 相关的时序违规显著增多。设计必须运行的操作模式和工…
阅读更多...
2，QT-Creator工具创建新项目教程

2，QT-Creator工具创建新项目教程

目录 1，创建一个新项目 demo_01.pro（项目配置文件） 类似 CMakeList.txt widget.h（头文件）​ main.cpp（程序入口）​ widget.cpp（源文件）​ widget.ui（界面设计文件）​ 1，创建一个新项目 依次选择： 设置路径： 选择编译器： 如果选择CMake, 就会生成cmakel…
阅读更多...
【RocketMQ 生产者和消费者】- 生产者发送同步、异步、单向消息源码分析（1）

【RocketMQ 生产者和消费者】- 生产者发送同步、异步、单向消息源码分析（1）

文章目录 1. 前言2. send 方法发送同步消息3. sendDefaultImpl 发送消息4. sendKernelImpl 发送同步、异步、单向消息5. sendMessage 发送消息6. 同步发送 sendMessageSync6.1 invokeSyncImpl 同步调用 7. 异步发送 sendMessageAsync7.1 invokeAsyncImpl 异步调用 8. 单向发送 …
阅读更多...
【harbor】--配置https

【harbor】--配置https

使用自建的 CA 证书来自签署和启用 HTTPS 通信。 &#xff08;1&#xff09;生成 CA认证 使用 OpenSSL 生成一个 2048位的私钥这是 自建 CA&#xff08;证书颁发机构&#xff09; 的私钥&#xff0c;后续会用它来签发证书。 # 1创建CA认证 cd 到harbor [rootlocalhost harbo…
阅读更多...
SOC-ESP32S3部分：23-文件系统

SOC-ESP32S3部分：23-文件系统

飞书文档https://x509p6c8to.feishu.cn/wiki/SXf5w6seIijVVskvic5cNT2wng4 目前&#xff0c;ESP-IDF 框架支持三种文件系统。 SPIFFS&#xff08;SPI Flash File System&#xff09; 简介&#xff1a;SPIFFS 是专门为 SPI NOR Flash 设备设计的轻量级文件系统&#xff0c;适…
阅读更多...
[Godot] 如何导出安卓 APK 并在手机上调试

[Godot] 如何导出安卓 APK 并在手机上调试

在之前的文章中&#xff0c;我们已经详细介绍了如何配置 Godot 的安卓应用开发环境&#xff0c;包括安装 Android SDK、配置 Java 环境、设置 Godot 的 Android 导出模板等。本篇文章将进一步讲解如何将 Godot 项目导出为安卓 APK 文件&#xff0c;并实现在手机上进行调试运行。…
阅读更多...
通用人工智能 (AGI): 定义、挑战与未来展望

通用人工智能 (AGI): 定义、挑战与未来展望

摘要 通用人工智能 (AGI) 代表人工智能领域的理想追求&#xff0c;其目标是创造具备人类般广泛智能能力的系统。本文深入探讨 AGI 的核心概念&#xff0c;详细梳理通向 AGI 的潜在技术路径&#xff0c;同时分析实现过程中面临的挑战与应对策略&#xff0c;并对 AGI 的未来发展进…
阅读更多...
【CF】Day72——Codeforces Round 890 (Div. 2) CDE1 (二分答案 | 交互 + 分治 | ⭐树上背包)

【CF】Day72——Codeforces Round 890 (Div. 2) CDE1 (二分答案 | 交互 + 分治 | ⭐树上背包)

C. To Become Max 题目&#xff1a; 思路&#xff1a; 二分挺好想的&#xff0c;但是check有点不好写 看到最大值&#xff0c;试试二分&#xff0c;如果 x 可以&#xff0c;那么 x - 1 肯定也可以&#xff0c;所以具有单调性&#xff0c;考虑二分 如何check呢&#xff1f;由于…
阅读更多...
Java进阶---JVM

Java进阶---JVM

JVM概述 JVM作用&#xff1a; 负责将字节码翻译为机器码&#xff0c;管理运行时内存 JVM整体组成部分&#xff1a; 类加载系统(ClasLoader)&#xff1a;负责将硬盘上的字节码文件加载到内存中 运行时数据区(RuntimeData Area)&#xff1a;负责存储运行时各种数据 执行引擎(Ex…
阅读更多...
Linux《文件系统》

Linux《文件系统》

在之前的系统IO当中已经了解了“内存”级别的文件操作&#xff0c;了解了文件描述符、重定向、缓冲区等概念&#xff0c;在了解了这些的知识之后还封装出了我们自己的libc库。接下来在本篇当中将会将视角从内存转向磁盘&#xff0c;研究文件在内存当中是如何进行存储的&#xf…
阅读更多...
SRD-12VDC-SL-C 继电器‌接线图解

SRD-12VDC-SL-C 继电器‌接线图解

这个继电器可以使用12伏的直流电源控制250伏和125伏的交流电&#xff0c;也可以控制30伏和28伏的直流电&#xff0c;电流都为10安。 此继电器有5个引脚&#xff0c;各个的作用如下&#xff1a; 引脚4和引脚5为触点&#xff0c; 引脚1和引脚3为线圈引脚&#xff0c;接12伏的直…
阅读更多...
Linux下目录递归拷贝的单进程实现

Linux下目录递归拷贝的单进程实现

1.实验目的 掌握Linux应用程序命令行参数传递方法掌握POSIX API中文件I/O操作方法&#xff0c;包括&#xff1a;打开文件、关闭文件、创建文件、读写文件、确定和改变文件当前位置 2.实验内容 利用POSIX API在Linux系统上编写应用程序&#xff0c;仿写cp命令的部分功能&#…
阅读更多...
哈希：闭散列的开放定址法

哈希：闭散列的开放定址法

我还是曾经的那个少年 1.概念 通过其要存储的值与存储的位置建立映射关系。 如&#xff1a;基数排序也是运用了哈希开放定址法的的思想。 弊端&#xff1a;仅适用于数据集中的情况 2.开放定址法 问题&#xff1a;按照上述哈希的方式&#xff0c;向集合插入数据为44&#xff…
阅读更多...
数据库基础

数据库基础

MySQL基础 一、什么是数据库 mysql是数据库服务的客户端 mysql是数据库服务的服务器端 本质&#xff1a;基于C&#xff08;mysql&#xff09;S&#xff08;mysqld&#xff09;模式的一种服务网络&#xff0c;一套给我们提供数据存取的服务的网络程序 数据库&#xff1a;一…
阅读更多...
多线程——线程池

多线程——线程池

课程&#xff1a; 什么是线程池 可以自己实现这个功能&#xff0c;自己写一个线程池 jdk也给提供了线程池 为什么要有线程池 Executor框架 任务&#xff1a;就是代码 执行&#xff1a;谁去执行这个代码&#xff0c;之前是Thread执行的&#xff0c; thread: Executor: …
阅读更多...
2006-2021年 中国社会状况综合调查CSS数据（含Excel、Stata格式）

2006-2021年 中国社会状况综合调查CSS数据（含Excel、Stata格式）

2006-2021年 中国社会状况综合调查CSS数据&#xff08;含Excel、Stata格式&#xff09;.ziphttps://download.csdn.net/download/2401_84585615/89784651 https://download.csdn.net/download/2401_84585615/89784651 2006至2021年&#xff0c;中国社会状况综合调查&#xff08…
阅读更多...
ReLU的变体

ReLU的变体

在深度学习中&#xff0c;ReLU&#xff08;Rectified Linear Unit&#xff09;是最常用的激活函数之一&#xff0c;但其存在一些局限性&#xff08;如死亡ReLU问题&#xff09;。为解决这些问题&#xff0c;研究者们提出了多种变体。以下是常见的ReLU变体及其核心特点&#xff…
阅读更多...
推荐文章

Copyright @ 2022~2023