系列文章目录
目录
前言
本文介绍了队列的常用方法，分别使用双向链表和环形数组模拟实现队列，使用队列模拟实现栈，以及使用栈模拟实现队列。
一、队列和链表
队列是一种特殊的线性表，允许在一端进行数据的插入，另一端进行数据的删除。插入一端称为队尾，删除一端称为队头。
队列的底层是一个链表，Queue 是单链表的数据结构，Deque 是双端链表，LinkedList 既实现了Queue，也实现了 Deque，同时还实现了 List，因此 LinkedList 既可以实现队列，又可以实现栈；
如果使用单链表实现栈：
尾插法入栈的时间复杂度是 O(N)，尾删出栈的时间复杂度也是 O(N);
头插法入栈的时间复杂度是 O(1)，头删出栈的时间复杂度也是 O(1)；
如果增加尾指针：
尾插法入栈的时间复杂度是 O(1)，尾删出栈的时间复杂度还是 O(N)；
如果使用双向链表实现栈：
头插法入栈，头删出栈，尾插法入栈，尾删出栈的时间复杂度都是 O(1)；
因此栈的实现既可以是顺序栈，也可以是链式栈；
队列也可以使用环形数组进行实现。
二、队列的常用方法
offer(E e): boolean 元素入队；
poll(): E 元素出队；
peek(): E 查看队头元素；
size(): int 返回队列元素个数；
isEmpty(): boolean 判断队列是否为空；
三、队列的模拟实现
1. 使用双向链表实现队列
public class MyQueue {
static class ListNode{
private int val;
private ListNode prev;
private ListNode next;
public ListNode(int val){
this.val = val;
}
}
private ListNode front;
private ListNode rear;
private int usedSize;
public void offer(int x){
ListNode node = new ListNode(x);
if(this.front == null){
this.front = node;
this.rear = node;
}else{
this.rear.next = node;
node.prev = this.rear;
this.rear = node;
}
this.usedSize++;
}
public ListNode poll(){
if(this.front == null){
return null;
}
ListNode ret = this.front;
this.usedSize--;
if(this.front == this.rear){
this.front = null;
this.rear = null;
return ret;
}
this.front = this.front.next;
this.front.prev = null;
return ret;
}
public ListNode peek(){
if(this.front == null){
return null;
}
return this.front;
}
public int size(){
return this.usedSize;
}
public boolean isEmpty(){
return this.usedSize == 0;
}
}2. 使用环形数组实现队列
front 表示环形数组中第一个元素的下标；
rear 表示环形数组中能够存放元素的下标；
len 表示环形数组的长度；
如何识别空和满：
可以定义一个 usedSize，当 usedSize == len 时，数组满；
可以通过标记，满了就将标记置为 true；
可以浪费一个空间，当 rear + 1 == front 就是满；
如何解决从最后一个下标到 0 下标的问题：
rear = (rear + 1) % len
front = (front + 1) % len
通过上述公式，可以保证 front 和 rear 从最后一个下标往下走一步达到 0 下标；
以下采用浪费一个空间的方式使用环形数组模拟实现队列：
class MyCircularQueue {
private int[] queue;
private int front;
private int rear;
public MyCircularQueue(int k) {
this.queue = new int[k + 1];
}
public boolean enQueue(int value) {
if(isFull()) return false;
this.queue[this.rear] = value;
this.rear = (this.rear + 1) % this.queue.length;
return true;
}
public boolean deQueue() {
if(isEmpty()) return false;
this.front = (this.front + 1) % this.queue.length;
return true;
}
public int Front() {
if(isEmpty()) return -1;
return this.queue[this.front];
}
public int Rear() {
if(isEmpty()) return -1;
return this.queue[(rear - 1 + this.queue.length) % this.queue.length];
}
public boolean isEmpty() {
if(this.rear == this.front) {
return true;
}
return false;
}
public boolean isFull() {
if((this.rear + 1) % this.queue.length == this.front) {
return true;
}
return false;
}
}四、队列和栈
1. 使用两个队列模拟实现栈
入栈：当两个队列都为空，元素先放在队列 1 中，当有一个不为空，放到不为空的队列中；
出栈：当两个队列都为空，返回 -1，当有一个队列不为空，将该队列的前 n - 1 个元素放到另一个队列，弹出该队列的最后一个元素并返回；
查看栈顶元素：当两个队列都为空，返回 -1，当一个队列不为空，将该队列的前 n - 1 个元素放到另一个队列，弹出该队列的最后一个元素并保存，将该元素也存到另一个队列，并返回保存的值；
判断栈是否为空：当两个队列都为空，返回 true，否则返回 false；
import java.util.*;
public class QueueToStack {
private Queue<Integer> q1;
private Queue<Integer> q2;
public QueueToStack() {
q1 = new LinkedList<>();
q2 = new LinkedList<>();
}
public void push(int x) {
if(q1.isEmpty() && q2.isEmpty()){
q1.offer(x);
}else{
if(!q1.isEmpty()){
q1.offer(x);
}else{
q2.offer(x);
}
}
}
public int pop() {
if(empty()) return -1;
if(!q1.isEmpty()){
int size = q1.size();
while(--size > 0){
int t = q1.poll();
q2.offer(t);
}
return q1.poll();
}else{
int size = q2.size();
while(--size > 0){
int t = q2.poll();
q1.offer(t);
}
return q2.poll();
}
}
public int top() {
if(empty()) return -1;
int ret = 0;
if(!q1.isEmpty()){
int size = q1.size();
while(--size > 0){
int t = q1.poll();
q2.offer(t);
}
ret = q1.poll();
q2.offer(ret);
return ret;
}else{
int size = q2.size();
while(--size > 0){
int t = q2.poll();
q1.offer(t);
}
ret = q2.poll();
q1.offer(ret);
return ret;
}
}
public boolean empty() {
if(q1.isEmpty() && q2.isEmpty()){
return true;
}
return false;
}
}2. 使用两个栈模拟实现队列
入队：放到第一个栈；
出队：如果队列为空，返回 -1，否则从第二个栈出，如果第二个栈为空，就将第一个栈的元素出栈，放到第二个栈，直到第一个栈为空，从第二个栈出；
查看队头元素：如果队列为空，返回 -1，否则查看第二个栈栈顶元素，如果第二个栈为空，就将第一个栈的元素出栈，放到第二个栈，直到第一个栈为空，查看第二个栈栈顶元素；
判断队列是否为空：如果两个栈都为空，返回 true，否则返回 false；
import java.util.*;
public class StackToQueue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public StackToQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if(empty()) return -1;
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
int t = stack1.pop();
stack2.push(t);
}
}
int ret = stack2.pop();
return ret;
}
public int peek() {
if(empty()) return -1;
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
int t = stack1.pop();
stack2.push(t);
}
}
int ret = stack2.peek();
return ret;
}
public boolean empty() {
if(stack1.isEmpty() && stack2.isEmpty()){
return true;
}
return false;
}
}