栈(Stack)和队列(Queue)
一、栈(Stack)
1、概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
在现实生活中，也有这样的例子，如猎枪的子弹，羽毛球筒里的羽毛球，都和栈一样后进先出。
（同样的，不一定是进一个出一个，顺序可以是随机的，根据需求来）
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()); // 获取栈中有效元素个数---> 4
System.out.println(s.peek()); // 获取栈顶元素---> 4
s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
if(s.empty()){
System.out.println("栈空");
}else{
System.out.println(s.size());
}
}3、栈的模拟实现
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);
}
}
}4、练习
（1）括号匹配。
这题就可以通过栈的形式解决问题，首先判断字符串的长度，若是奇数则直接返回false。接着创建一个哈希表，用来存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。创建一个栈，将字符依次放入栈，放入前与栈顶进行比较，若是构成一对则弹出栈顶，这个字符也不用入栈，直接跳过。循环执行，直到遍历完整个字符串。再去判断栈是否为空，若为空则有效。
class Solution {
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}（2）逆波兰表达式求值。
（150. 逆波兰表达式求值 - 力扣（LeetCode））
逆波兰表达式也可以称作后缀算术表达式。举个简单的例子：
((2 + 1) * 3) = 9这是我们常见的表达式，其实这就是中缀表达式，我们将运算符移动到向外一层的括号后面，得到"2","1","+","3","*"这和起来就是后缀表达式，用后缀表达式就可以借助栈求解了。
我们直接创建一个栈，将所有的字符循环放进栈中，若是数字就依次堆叠，若是符号就在栈顶弹出两个数进行运算，并将运算结果重新放到栈顶。往复循环，直到遍历完整个数组，这是栈顶就是结果（此时栈内只有一个元素了）
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList<Integer>();
int n = tokens.length;
for (int i = 0; i < n; i++) {
String token = tokens[i];
if (isNumber(token)) {
stack.push(Integer.parseInt(token));
} else {
int num2 = stack.pop();
int num1 = stack.pop();
switch (token) {
case "+":
stack.push(num1 + num2);
break;
case "-":
stack.push(num1 - num2);
break;
case "*":
stack.push(num1 * num2);
break;
case "/":
stack.push(num1 / num2);
break;
default:
}
}
}
return stack.pop();
}
public boolean isNumber(String token) {
return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
}
}（3）出栈入栈次序匹配。
这题的思路其实很明确，想要判断出栈入栈匹配，只需要创建一个栈，进行入栈操作，同时和出栈序列进行比较，相同则出栈。最后返回stack.empty()（这个方法，如果栈为空，就返回true，不为空返回false）
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();
}二、队列(Queue)
1、概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头 （Head/Front）
2、队列的使用
#注：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());
}
}3、队列模拟实现
队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构和链式结构。
public class Queue {
// 双向链表节点
public static class ListNode{
ListNode next;
ListNode prev;
int value;
ListNode(int value){
this.value = value;
}
}
ListNode first; // 队头
ListNode last; // 队尾
int size = 0;
// 入队列---向双向链表位置插入新节点
public void offer(int e){
ListNode newNode = new ListNode(e);
if(first == null){
first = newNode;
// last = newNode;
}else{
last.next = newNode;
newNode.prev = last;
// last = newNode;
}
last = newNode;
size++;
}
// 出队列---将双向链表第一个节点删除掉
public int poll(){
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
int value = 0;
if(first == null){
return null;
}else if(first == last){
last = null;
first = null;
}else{
value = first.value;
first = first.next;
first.prev.next = null;
first.prev = null;
}
--size;
return value;
}
// 获取队头元素---获取链表中第一个节点的值域
public int peek(){
if(first == null){
return null;
}
return first.value;
}
public int size() {
return size;
}
public boolean isEmpty(){
return first == null;
}
}4、循环队列
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。 环形队列通常使用数组实现。
4.1数组下标循环的小技巧：
（1）下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length
（2）下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length
4.2如何区分空与满
（1）通过添加 size 属性记录
（2）保留一个位置
（3）使用标记
4.3设计循环队列
class MyCircularQueue {
public int front; // 队头指针，指向队列的第一个元素
public int rear; // 队尾指针，指向队列最后一个元素的下一个位置
public int[] elem; // 用于存储队列元素的数组
// 构造函数，初始化循环队列，容量为k
public MyCircularQueue(int k) {
elem = new int[k+1]; // 因为循环队列会浪费一个空间来判断满队列，所以数组大小为k+1
}
// 入队操作：向队列尾部插入一个元素value
public boolean enQueue(int value) {
if(isFull()){ // 如果队列已满，插入失败
return false;
}
elem[rear] = value; // 将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()) { // 队列为空时返回-1
return -1;
}
return elem[front]; // 返回队头元素
}
// 获取队尾元素
public int Rear() {
if(isEmpty()) { // 队列为空时返回-1
return -1;
}
// 计算队尾元素的位置：如果rear为0，则队尾在数组末尾；否则为rear-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; // 队尾指针的下一个位置是队头时队列已满
}
}三、双端队列
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
Deque是一个接口，使用时必须创建LinkedList的对象。
在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现四、用队列实现栈。
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
/** Initialize your data structure here. */
public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
queue2.offer(x);
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue1.poll();
}
/** Get the top element. */
public int top() {
return queue1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty();
}
}五、用栈实现队列。
class MyQueue {
Deque<Integer> inStack;
Deque<Integer> outStack;
public MyQueue() {
inStack = new ArrayDeque<Integer>();
outStack = new ArrayDeque<Integer>();
}
public void push(int x) {
inStack.push(x);
}
public int pop() {
if (outStack.isEmpty()) {
in2out();
}
return outStack.pop();
}
public int peek() {
if (outStack.isEmpty()) {
in2out();
}
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
private void in2out() {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-08-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
