目录
1.队列（Queue）之概念
定义：队列是一种特殊的线性表，它只允许在一端进行插入（队尾）数据操作，在另一端进行删除（队头）数据操作。
队列具有先进先出的特点
队列的实现也是有两种方式
数组实现，链表实现
2.队列（Queue）之模拟实现
以单链表实现，并且做一点改动
先写一个上面这样结构的单链表
static class Node {
public int val;
public Node next;
public Node(int val) {
this.val = val;
}
}
public Node head;//队列头
public Node tail;//队列尾（1）入队offer()
public void offer(int val) {
Node node = new Node(val);
if (head == null) {
head = node;
tail = node;
}else {
tail.next = node;
tail = tail.next;
}
}（2）出队poll()
public int poll() {
if(head == null) {
return -1;
}
int oldVal = head.val;
if (head.next == null) {
head = tail = null;
}else {
head = head.next;
}
return oldVal;
}（3）查看当前对头元素peek()
public int peek() {
if(head == null) {
return -1;
}
return head.val;
}3.队列（Queue）之使用
public static void main(String[] args) {
java.util.Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(5);
queue.offer(7);
queue.offer(45);
System.out.println(queue.size());
System.out.println(queue.peek());
queue.poll();
System.out.println(queue.poll());
}
4.队列（Queue）之循环队列
先看顺序队列中元素的入队出队操作，因为队列元素出队是在对头，
那也就是，队列中所有元素的移动都是在向前移动，而这样向前移动就会出现这样的问题
所以，相对来说 对于队列最好的方法是使用链表实现，否则就会造成假溢出
那么java中对于假溢出解决的办法是使用循环队列
正常情况下，顺序队列中会发生假溢出，也就是开辟的数组空间还有剩余空间，却因为rear越界表现为溢出，
使用循环队列，就是将队列的首尾相连，这样rear移动到LENGTH时，就会再从0开始循环
1. 那么如何区分队列的空与满 因为当rear== front时，既表示空又表示满
（1）最直接的方法就是计数
（2）牺牲一个存储空间 front前面不存数据，当rear在front前面的时候就是满了（尾在头前就是满了）
（3） 是设置一个标志变量flag，当front == rear,且flag = 0时为队列空，当front == rear,且flag= 1时为队列满
看一个练习题
题目要求 
分析一下
入队和出队除了要考虑队满和队空的条件，还要考虑，当这一圈转完，到下一圈，不能时不能只加加，还要模个数组长度，得出第二圈的下标
上代码
class MyCircularQueue {
public int[] elem;
public int front;//队头下标
public int rear;//队尾下标
public MyCircularQueue(int k) {
this.elem = new int[k+1];
}
//入队
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
this.elem[rear] = value;
rear = (rear+1) % elem.length;
return true;
}
//出队
public boolean deQueue() {
if (isEmpty()) {
return false;
}
front = (front+1) % elem.length;//如果是K到0那就要%
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;
}
}
5.队列（Queue）之双端队列(Deque)
双端队列（Deque）是指在两端都可以进行入队和出队的操作的队列
不过需要注意的是，不能将一个数据，在一端进行入队和出队操作，不然这样就成了栈
Deque是一个接口，使用时必须要创建LinkedList的对象
Deque<Integer> myQueue2 = new LinkedList<>();6.力扣中的练习题
6.1 用队列实现栈
题目要求
分析一下
上代码
class MyStack {
Queue<Integer> qu1;
Queue<Integer> qu2;
public int usedSize;
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);
}
usedSize++;
}
public int pop() {
if(empty()) {
return -1;
}
if(!qu1.isEmpty()) {
int curSize = qu1.size();
for(int i = 0; i < curSize-1; i++) {
qu2.offer(qu1.poll());
}
usedSize--;
return qu1.poll();
}else {
int curSize = qu2.size();
for(int i = 0; i < curSize-1; i++) {
qu1.offer(qu2.poll());
}
usedSize--;
return qu2.poll();
}
}
public int top() {
if(empty()) {
return -1;
}
if(!qu1.isEmpty()) {
int curSize = qu1.size();
int ret = -1;
for(int i = 0; i < curSize; i++) {
ret = qu1.poll();
qu2.offer(ret);
}
return ret;
}else {
int curSize = qu2.size();
int ret = -1;
for(int i = 0; i < curSize; i++) {
ret = qu2.poll();
qu1.offer(ret);
}
return ret;
}
}
public boolean empty() {
return usedSize == 0;
}
}
6.2 用栈实现队列
题目要求
分析一下
上代码
class MyQueue {
Stack<Integer> s1;
Stack<Integer> s2;
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
public void push(int x) {
s1.push(x);
}
public int pop() {
if(empty()) {
return -1;
}
if(s2.empty()) {
//将s1中所有元素倒过来
while(!s1.empty()) {
s2.push(s1.pop());
}
}
return s2.pop();
}
public int peek() {
if(empty()) {
return -1;
}
if(s2.empty()) {
//将s1中所有元素倒过来
while(!s1.empty()) {
s2.push(s1.pop());
}
}
return s2.peek();
}
public boolean empty() {
return s1.empty() && s2.empty();
}
}6.3 最小栈
题目要求
分析一下
上代码
class MinStack {
private Stack<Integer> s;//普通栈
private Stack<Integer> minStack;//最小栈
public MinStack() {
s = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
s.push(val);
if(minStack.empty()) {
//最小栈为null，直接放
minStack.push(val);
}else {
int peekV = minStack.peek();
if(val <= peekV) {
minStack.push(val);
}
}
}
public void pop() {
int popV = s.pop();
int peekVMinS = minStack.peek();
if(popV == peekVMinS) {
minStack.pop();
}
}
public int top() {
return s.peek();
}
public int getMin() {
return minStack.peek();
}
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/87350.html
