数据结构之队列
系列文章目录
数据结构之ArrayList-CSDN博客
数据结构之LinkedList-CSDN博客
数据结构之栈-CSDN博客
目录
系列文章目录
前言
一、队列和链表
二、队列的常用方法
三、队列的模拟实现
1. 使用双向链表实现队列
2. 使用环形数组实现队列
四、队列和栈
1. 使用两个队列模拟实现栈
2. 使用两个栈模拟实现队列
前言
本文介绍了队列的常用方法，分别使用双向链表和环形数组模拟实现队列，使用队列模拟实现栈，以及使用栈模拟实现队列。
一、队列和链表
队列是一种特殊的线性表，允许在一端进行数据的插入，另一端进行数据的删除。插入一端称为队尾，删除一端称为队头。
队列的底层是一个链表，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;}
}