关键词：
Java栈和队列·下
大家好，我是晓星航。今天为大家带来的是 Java栈和队列·下 的讲解！😀
继上一个讲完的栈后，我们这次开始讲解队列！
2. 队列(Queue)
2.1 概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）
在idea中看Queue(队列的底层逻辑代码)时 按下 alt + 7 可以查看它包含的所有方法：
2.2 实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
class Node
public int val;
public Node next;
public Node(int val)
this.val = val;
public class MyQueue
public Node head;
public Node last;
/**
* 尾插法
* @param val
*/
public void offer(int val)
Node node = new Node(val);
if (head == null)
head = node;
last = node;
else
last.next = node;
last = last.next;
public int poll()
if (isEmpty())
throw new RuntimeException("队列为空");
int oldVal = head.val;
head = head.next;
return oldVal;
public boolean isEmpty()
return this.head == null;
public int peek()
if (isEmpty())
throw new RuntimeException("队列为空");
return head.val;
下面为测试代码：
public class TestDemo
public static void main(String[] args)
MyQueue queue = new MyQueue();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.peek());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
Queue中方法总结：
add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常
remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
offer 添加一个元素并返回true 如果队列已满，则返回false
poll 移除并返问队列头部的元素 如果队列为空，则返回null
peek 返回队列头部的元素 如果队列为空，则返回null
put 添加一个元素 如果队列满，则阻塞
take 移除并返回队列头部的元素
2.3 相似方法的区别
1、add()和offer()区别:
add()和offer()都是向队列中添加一个元素。一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，调用 add() 方法就会抛出一个 unchecked 异常，而调用 offer() 方法会返回 false。因此就可以在程序中进行有效的判断！
2、poll()和remove()区别：
remove() 和 poll() 方法都是从队列中删除第一个元素。如果队列元素为空，调用remove() 的行为与 Collection 接口的版本相似会抛出异常，但是新的 **poll() 方法在用空集合调用时只是返回 null。**因此新的方法更适合容易出现异常条件的情况。
3、element() 和 peek() 区别：
element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。
2.4 循环队列
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。
数组下标循环的小技巧
-
- 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length
- 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length
如何区分空与满
- 通过添加 size 属性记录 使用size和数组长度比较，确定满或者空
-
使用标志位flag，最开始falg = false，
入队列时，每放一个元素，falg就置为true
出队列时，每出一个元素，falg就置为false
当front和rear相遇时，falg为true则队列为满，falg为false则队列为空。
- 浪费一个格子来区分空和满，每次存放元素之前，都先检查一下rear的下一个是不是front。如果是，那么就是满的
空：frontNext == rear
满：rearNext == front
3. 双端队列 (Deque)
3.1 概念
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
双端队列的所有方法：
4.java中的栈和队列
栈的方法：
普通队列方法：
双端队列方法：
5. 栈和队列面试题
- 括号匹配问题。OJ链接
import java.util.Stack;
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())
//右括号多
System.out.println("右括号多！");
return false;
char top = stack.peek();
if (top == '(' && ch == ')' || top == '[' && ch == ']' || top == '' && ch == '')
//如果左括号和右括号匹配 则弹出这个左括号
stack.pop();
else
//左右括号不匹配
System.out.println("左右括号不匹配");
return false;
if (!stack.empty())
//左括号多
System.out.println("左括号多！");
return false;
return true;
题目描述的很清楚，左右括号如果不匹配，无非是以下几种情况：
1、左括号多余右括号
2、右括号多余左括号
3、左右括号顺序不想匹配
在使用代码将这几种情况考虑完全后，便可轻易通过测试。
思路如下：
如果是左括号我们直接使其进栈，如果是右括号我们先判断右括号是否比左括号多，再看其是否相匹配，匹配则弹出相对应的左括号继续下一个括号的判断，如果不匹配则返回不匹配错误，在右括号全部判断完毕后，我们判断一下栈此时是否为空，如果为空则我们所有的括号都匹配成功即正确，如果不为空则是左括号比右括号要多，我们就返回false。
- 用队列实现栈。OJ链接
public class MyStack
private Queue<Integer> qu1;
private 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++)
int val = qu1.poll();
qu2.offer(val);
return qu1.poll();
if (!qu2.isEmpty())
int size = qu2.size();
for (int i = 0; i < size - 1; i++)
int val = qu2.poll();
qu1.offer(val);
return qu2.poll();
return -1;
public int top()
if (empty())
return -1;
if (!qu1.isEmpty())
int val = -1;
int size = qu1.size();
for (int i = 0; i < size; i++)
val = qu1.poll();
qu2.offer(val);
return val;
if (!qu2.isEmpty())
int val = -1;
int size = qu2.size();
for (int i = 0; i < size; i++)
val = qu2.poll();
qu1.offer(val);
return val;
return -1;
public boolean empty()
return qu1.isEmpty() && qu2.isEmpty();
1、入栈的时候，入到不为空的队列，刚开始都为空指定入到一个队列。
2、出栈的时候，找到不为空的队列，出size-1个元素到另一个队列，剩下这个元素就是出栈的元素。
注意：这里有一个小问题我们很容易疏忽，就是在使用top和pop方法进行移动时我们qu1和qu2中的元素个数时变化的，因此我们的qu1.size() qu2.size()也会跟着变化，为了避免这个情况，我们在for循环的外面自己定义一个Int size = qu1.size(); int size = qu2.size();在之后的for循环中我们只需要让i小于size即可，此时的size就不是一个会变动的值了。
- 用栈实现队列。OJ链接
class MyQueue
public Stack<Integer> stack1;
public 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.empty())
while (!stack1.isEmpty())
stack2.push(stack1.pop());
return stack2.pop();
public int peek()
if (empty())
return -1;
if (stack2.empty())
while (!stack1.isEmpty())
stack2.push(stack1.pop());
return stack2.peek();
public boolean empty()
return stack1.isEmpty() && stack2.isEmpty();
思路：1、入队的时候，统一入到第1个栈
2、出队的时候，同一出第2个栈里面的元素，如果第2个为空，那么把第一个栈里面所有的元素，全部倒过来，然后再出栈顶的元素。
- 实现一个最小栈。OJ链接
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())
int top = minStack.peek();
//比较 小于等于的话 也要放进来
if (val <= top)
minStack.push(val);
else
minStack.push(val);
public void pop()
int popVal = stack.pop();
if (!minStack.empty())
int top = minStack.peek();
if (top == popVal)
minStack.pop();
public int top()
return stack.peek();
public int getMin()
return minStack.peek();
思路：这里我们采取了使用两个栈(一个普通栈 一个最小栈)来比较的方法，例如我们在push元素时，普通栈我们是直接放进去的，而最小栈我们则是通过比较，如果要放的元素比我们最小栈栈顶的元素小或等于我们便在最小栈也放入一份。
在pop弹出栈顶元素时我们同样是直接弹出普通栈的栈顶元素，然后比较这个弹出的元素和最小栈栈顶元素的大小是否相等，如果相等我们则还需要再pop一次最小栈的栈顶元素。
top方法和我们stack栈中的peek方法一样，我们直接返回stack的peek方法即可。
getMin方法是返回栈中最小元素，我们这里有两个栈，而最小栈的原理就是将最小的元素通过压栈(头插)的方式进入最小栈，因此我们最小栈的最小值永远是栈顶的元素，我们直接返回最小栈的栈顶元素即可。
- 设计循环队列。OJ链接
class MyCircularQueue
public int[] elem;
public int front;//队头下标
public int rear;//队尾下标
public MyCircularQueue(int k)
this.elem = new int[k + 1];
/**
* 入队操作
* @param value
* @return
*/
public boolean enQueue(int value)
if (isFull())
return false;
this.elem[rear] = value;
//rear++;
rear = (rear + 1) % elem.length;
return true;
/**
* 出队操作
* @return
*/
public boolean deQueue()
if (isEmpty())
return false;
front = (front + 1) % elem.lengthjava集合与数据结构栈和队列(代码片段)
Java集合与数据结构栈和队列栈(Stack)基本方法栈的习题出栈顺序不可能中缀表达式转后缀表达式（逆波兰式）手动实现栈队列(Queue)基本方法链表实现队列循环队列用队列实现栈用栈实现队列括号匹配问题实现一个最小栈... 查看详情
java集合与数据结构栈和队列(代码片段)
Java集合与数据结构栈和队列栈(Stack)基本方法栈的习题出栈顺序不可能中缀表达式转后缀表达式（逆波兰式）手动实现栈队列(Queue)基本方法链表实现队列循环队列用队列实现栈用栈实现队列括号匹配问题实现一个最小栈... 查看详情
java和c++的栈和队列(代码片段)
Java和c++的栈和队列Java默认使用DequeDeque方法的区别传统的queue是以低地址端为队头，高地址端为队尾传统的stack是以低地址端为栈底，高地址端为栈顶pop(),push(),poll()，offer(),remove()这类传统方法在deque中都是以高... 查看详情
数据结构java版详解栈和队列的实现(代码片段)
...列的单链表实现2.4数组实现队列2.5循环队列2.6双端队列3.栈和队列练习题3.1有效的括号3.2用队列实现栈3.3用栈实现队列3.4实现一个最小栈3.5设计循环队列1.栈1.1概念栈：是一种特殊的线性表，其只允许在固定的一端进行插... 查看详情
数据结构java版详解栈和队列的实现(代码片段)
...列的单链表实现2.4数组实现队列2.5循环队列2.6双端队列3.栈和队列练习题3.1有效的括号3.2用队列实现栈3.3用栈实现队列3.4实现一个最小栈3.5设计循环队列1.栈1.1概念栈：是一种特殊的线性表，其只允许在固定的一端进行插... 查看详情
leetcode题解——数据结构之栈和队列(代码片段)
1.用栈实现队列2.用队列实现栈3.最小值栈4.用栈实现括号匹配5.数组中元素与下一个比它大的元素之间的距离6.循环数组中比当前元素大的下一个元素1.用栈实现队列232.ImplementQueueusingStacks(Easy)栈的顺序为后进先出，而队列的顺序... 查看详情
「java数据结构」-栈和队列(代码片段)
栈的认识栈的功能实现入栈取栈顶元素出栈栈是否为空队列的认识队列的功能实现入队列出队列取对头元素判断队列是否为空栈的认识栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据... 查看详情
java距离我上次知道栈和队列有多简单还是在上次(代码片段)
...午餐的学生数量1.3自我实现1.4双端队列(deque)三、Java中的栈和队列3.1Java中的栈3.2Java中的队列3.3Java中的双端队列引子栈、队列和线性表一样都是一种线性的数据结构 查看详情
栈和队列(代码片段)
栈:先进后出(底层用数组实现) 栈只有一个开口,先进去的就到最底下,后进来的就在前面,要是拿出去的话,肯定是从开口端拿出去, 所以说先进后出，后进先出。数据结构：java实现栈(基于数组)：/***栈只有一个开口,先进去... 查看详情
数据结构-栈和队列(代码片段)
数据结构-栈和队列介绍栈和队列是两种很简单，但也很重要的数据结构，在之后的内容也会用到的栈的特点就是FILO（firstinlastout）而队列则是FIFO（firstinfirstout）栈和队列也是列表栈和队列都可以认为是链表，只是插入删除的方... 查看详情
数据结构初阶：栈和队列(代码片段)
文章目录栈和队列1栈1.1栈的定义和结构栈结构体定义1.2栈的实现栈初始化和销毁栈的压入和弹出获取栈顶元素其他基本接口2队列2.1队列的定义和结构队列结构体定义2.2队列的实现队列初始化和销毁队尾入队和队头出队获取队头... 查看详情
栈和队列(代码片段)
顺序栈的实现#include<bits/stdc++.h>usingnamespacestd;constintN=1e4+5;classSeqstackpublic:Seqstack();~Seqstack()voidPush(intk);intPop();boolEmpty();intGettop();private:intdata[N];inttop 查看详情
栈和队列数据结构(代码片段)
前言：栈和队列都是基于List(线性表)来实现的，且其限制比List更严格(提供的操作更少)，即List比站栈和队列更灵活栈的实际应用场景非常多，队列的实际应用场景更多目录栈(Stack)概念栈的实现队列(Queue)概念队列... 查看详情
数据结构栈和队列oj练习(栈和队列相互实现+循环队列实现)(代码片段)
...队列实现栈2.用栈实现队列3.循环队列前言前面在学习了栈和队列的实现之后，相信大家对栈和队列的结构和使用方式都有了一些理解。下面我们就来进行一些练习，这这章的练习相对于原来在难度上有了一些提升。原来... 查看详情
表栈和队列(代码片段)
...erator本系列讨论最简单的和最基本的三种数据类型：表、栈和队列，实 查看详情
博客作业03--栈和队列(代码片段)
博客作业03--栈和队列1.学习总结(2分)1.1写出你认为本周学习中比较重要的知识点关键词，如逻辑结构、栈、队列、存储结构等。1.栈（1）栈的定义及操作，包括：建栈，初始化栈，入栈，出栈，判断栈是否为空，取栈顶元素，销... 查看详情
栈和队列----由两个栈组成队列(代码片段)
由两个栈组成队列 由两个栈实现一个队列，支持队列的基本操作(addpollpeek)，需要注意的是，stackPush向stackPop中压入数据，必须一次性的把stackPush中的元素全部压入，此外，如果stackPop不为空，不能向stackPop中压入数据。 pa... 查看详情
自定义栈和队列(代码片段)
一、栈首先来使用简单的方式LinkedList来定义importjava.util.LinkedList;/***Createdbylilion15/11/14.*/publicclassMyStackprivateLinkedListlinkedList;publicMyStack()linkedList=newLinkedList();publicvoidpush(Objecto)li 查看详情