一、隊(duì)列介紹
?? 隊(duì)列（Queue）是一種特殊的線性表，只能在頭尾兩端進(jìn)行操作
?? 隊(duì)尾（rear）：只能從隊(duì)尾添加元素，一般叫做 enQueue，入隊(duì)
?? 隊(duì)頭（front）：只能從隊(duì)頭移除元素，一般叫做 deQueue，出隊(duì)
?? 先進(jìn)先出的原則，First In First Out，FIFO
二、使用 LinkedList 實(shí)現(xiàn)隊(duì)列
/**
* 利用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)棧
*/
public class Queue<E> {
// 通過【組合】的方式使用 LinkedList
private final List<E> list = new LinkedList<>();
/**
* 獲取隊(duì)列中的元素個(gè)數(shù)
*/
public int size() {
return list.size();
}
/**
* 判斷隊(duì)列中是否一個(gè)元素都沒有（判斷是否是一個(gè)空隊(duì)列）
*/
public boolean isEmpty() {
return list.isEmpty();
}
/**
* 往隊(duì)列中添加元素（入隊(duì)）
*/
public void enQueue(E element) {
list.add(0, element);
}
/**
* 取出隊(duì)首元素, 并刪之（出隊(duì)）
*
* @return 隊(duì)首元素
*/
public E deQueue() {
return list.remove(size() - 1);
}
/**
* 獲取隊(duì)列的頭元素
*/
public E front() {
return list.get(size() - 1);
}
/**
* 清空隊(duì)列
*/
public void clear() {
list.clear();
}
}
?? 隊(duì)列內(nèi)部的實(shí)現(xiàn)可以直接利用動(dòng)態(tài)數(shù)組和鏈表
?? 優(yōu)先使用雙向鏈表。① 隊(duì)列主要是往頭尾兩端操作元素；② 雙向鏈表由于有頭指針first和尾指針last的存在，在頭尾進(jìn)行元素操作都是O(1)的復(fù)雜度
三、LeetCode：用【?！繉?shí)現(xiàn)隊(duì)列
https://leetcode.cn/problems/implement-queue-using-stacks/
(1) 老師講之前我自己的實(shí)現(xiàn)（Correct）
?? 代碼是正確的，通過了 LeetCode 的檢查
public class MyQueue {
private Stack<Integer> stackLeft = new Stack<>(); // 左棧
private Stack<Integer> stackRight = new Stack<>(); // 右棧
/**
* 構(gòu)造方法
*/
public MyQueue() {
}
/**
* 入隊(duì)
*/
public void push(int x) {
stackLeft.push(x);
}
/**
* 出隊(duì)
*/
public int pop() {
// 先把【左?！康脑厝砍鰲２⑷霔５健居覘！恐?/span>
while (!stackLeft.isEmpty()) {
stackRight.push(stackLeft.pop());
}
Integer elem = stackRight.pop();
// 把【右棧】元素放入【左?！?/span>
while (!stackRight.isEmpty()) {
stackLeft.push(stackRight.pop());
}
return elem;
}
/**
* 返回隊(duì)首元素
*/
public int peek() {
// 先把【左棧】的元素全部出棧并入棧到【右?！恐?/span>
while (!stackLeft.isEmpty()) {
stackRight.push(stackLeft.pop());
}
Integer elem = stackRight.peek();
// 把【右棧】元素放入【左?！?/span>
while (!stackRight.isEmpty()) {
stackLeft.push(stackRight.pop());
}
return elem;
}
public boolean empty() {
return stackLeft.isEmpty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
(2) 實(shí)現(xiàn)思路
?? 準(zhǔn)備 2 個(gè)棧：inStack、outStack
??入隊(duì)時(shí)，把元素 push 到 inStack 中
??出隊(duì)時(shí)
??如果 outStack 為空，① 將 inStack 所有元素逐一彈出，push 到 outStack；② outStack 彈出棧頂元素
??如果 outStack 不為空， outStack 彈出棧頂元素
(3) 代碼實(shí)現(xiàn)
public class MyQueue {
// 入隊(duì)時(shí), 往 inStack 插入元素
private Stack<Integer> inStack = new Stack<>();
private Stack<Integer> outStack = new Stack<>();
/**
* 構(gòu)造方法
*/
public MyQueue() {
}
/**
* 入隊(duì)（只要是入隊(duì), 就往 inStack 插入元素）
*/
public void push(int x) {
inStack.push(x);
}
/**
* 出隊(duì)
*/
public int pop() {
if (outStack.isEmpty()) { // 如果 outStack 為空
// 將 inStack 所有元素逐一彈出, push 到 outStack 中
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
return outStack.pop();
}
/**
* 返回隊(duì)首元素
*/
public int peek() {
if (outStack.isEmpty()) { // 如果 outStack 為空
// 將 inStack 所有元素逐一彈出, push 到 outStack 中
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
四、jdk 的 Queue
?? offer()：入隊(duì)
?? poll()：出隊(duì)
?? peek()：返回隊(duì)頭元素
?? jdk 的 Queue 底層也是 LinkedList
五、雙端隊(duì)列（Deque）
?? 雙端隊(duì)列是能在頭尾兩端添加、刪除的隊(duì)列
?? 英文 deque 是 double ended queue 的簡(jiǎn)稱
☆ 隊(duì)尾是鏈表的末尾
☆ 隊(duì)頭是鏈表的第一個(gè)元素
/**
* 雙端隊(duì)列
*/
public class Deque<E> {
private final List<E> linkedList;
public Deque() {
this.linkedList = new LinkedList<>();
}
public int size() {
return linkedList.size();
}
public boolean isEmpty() {
return linkedList.isEmpty();
}
public void clear() {
linkedList.clear();
}
/**
* 從隊(duì)尾入隊(duì)
*/
public void enQueueRear(E element) {
linkedList.add(element);
}
/**
* 從隊(duì)頭入隊(duì)
*/
public void enQueueFront(E element) {
linkedList.add(0, element);
}
/**
* 從隊(duì)頭出隊(duì)
*/
public E deQueueFront() {
return linkedList.remove(0);
}
/**
* 從隊(duì)尾出隊(duì)
*/
public E deQueueRear() {
return linkedList.remove(size() - 1);
}
/**
* 獲取隊(duì)列的頭元素
*/
public E front() {
return linkedList.get(0);
}
/**
* 獲取隊(duì)列的【尾】元素
*/
public E rear() {
return linkedList.get(size() - 1);
}
}
六、循環(huán)隊(duì)列
(1) 分析
?? 隊(duì)列底層也可以使用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)，并且各項(xiàng)接口也可以優(yōu)化到 O(1) 的時(shí)間復(fù)雜度
?? 用數(shù)組實(shí)現(xiàn)并且優(yōu)化之后的隊(duì)列也叫做：循環(huán)隊(duì)列（Circle Queue）
?? 循環(huán)雙端隊(duì)列：可以進(jìn)行兩端添加、刪除操作的循環(huán)隊(duì)列
(2) 入隊(duì)
/**
* 往隊(duì)列中添加元素（入隊(duì)）
*/
public void enQueue(E element) {
elements[(front + size) % elements.length] = element;
size++;
}
(3) 出隊(duì)
/**
* 取出隊(duì)首元素, 并刪之（出隊(duì)）
*
* @return 隊(duì)首元素
*/
public E deQueue() {
E frontElem = elements[front];
elements[front] = null;
front = (front + 1) % elements.length;
size--;
return frontElem;
}
(4) 動(dòng)態(tài)擴(kuò)容
① 我自己的垃圾實(shí)現(xiàn)
?? 也是能夠滿足要求的，但代碼效率不行 ??
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
// 如果所需容量足夠, 則不擴(kuò)容
if (oldCapacity >= capacity) return;
// 申請(qǐng)全新的數(shù)組空間（新容量是舊容量的 1.5 倍）
capacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[capacity];
// 把舊數(shù)組中的數(shù)據(jù)復(fù)制到新數(shù)組中
int index = 0;
int flagSize = 0;
E[] oldElements = this.elements;
while (!this.isEmpty()) {
E e = this.deQueue();
flagSize++;
newElements[index] = e;
index++;
}
// elements 指針指向新數(shù)組
this.elements = newElements;
// 隊(duì)頭 front 指向 0
front = 0;
size = flagSize;
System.out.println(oldCapacity + "擴(kuò)容為" + capacity);
}
② 老師的代碼實(shí)現(xiàn)
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
// 如果所需容量足夠, 則不擴(kuò)容
if (oldCapacity >= capacity) return;
// 申請(qǐng)全新的數(shù)組空間（新容量是舊容量的 1.5 倍）
capacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[capacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[(i + front) % elements.length];
}
// elements 指針指向新數(shù)組
this.elements = newElements;
// 隊(duì)頭 front 指向 0
front = 0;
System.out.println(oldCapacity + "擴(kuò)容為" + capacity);
}
(5) 索引映射封裝
public int realIndex(int index) {
return (front + index) % elements.length;
}
(6) 循環(huán)隊(duì)列完整代碼
/**
* 循環(huán)隊(duì)列
*/
@SuppressWarnings("all")
public class CircleQueue<E> {
private int front; // 記錄著隊(duì)頭元素的下標(biāo)
private int size;
private E[] elements;
public static final int DEFAULT_CAPACITY = 10;
public CircleQueue(int capacity) {
capacity = (capacity > DEFAULT_CAPACITY) ? capacity : DEFAULT_CAPACITY;
elements = (E[]) new Object[capacity];
}
public CircleQueue() {
this(DEFAULT_CAPACITY);
}
/**
* 獲取隊(duì)列中的元素個(gè)數(shù)
*/
public int size() {
return size;
}
/**
* 判斷隊(duì)列中是否一個(gè)元素都沒有（判斷是否是一個(gè)空隊(duì)列）
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 獲取隊(duì)列的頭元素
*/
public E front() {
return elements[front];
}
/**
* 往隊(duì)列中添加元素（入隊(duì)）
*/
public void enQueue(E element) {
// 擴(kuò)容檢測(cè)
ensureCapacity(size + 1);
elements[realIndex(size)] = element;
size++;
}
/**
* 我自己的垃圾實(shí)現(xiàn)
*/
// private void ensureCapacity(int capacity) {
// int oldCapacity = elements.length;
// // 如果所需容量足夠, 則不擴(kuò)容
// if (oldCapacity >= capacity) return;
//
// // 申請(qǐng)全新的數(shù)組空間（新容量是舊容量的 1.5 倍）
// capacity = oldCapacity + (oldCapacity >> 1);
// E[] newElements = (E[]) new Object[capacity];
//
// // 把舊數(shù)組中的數(shù)據(jù)復(fù)制到新數(shù)組中
// int index = 0;
// int flagSize = 0;
// E[] oldElements = this.elements;
// while (!this.isEmpty()) {
// E e = this.deQueue();
// flagSize++;
// newElements[index] = e;
// index++;
// }
//
// // elements 指針指向新數(shù)組
// this.elements = newElements;
// // 隊(duì)頭 front 指向 0
// front = 0;
// size = flagSize;
//
// System.out.println(oldCapacity + "擴(kuò)容為: " + capacity);
// }
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
// 如果所需容量足夠, 則不擴(kuò)容
if (oldCapacity >= capacity) return;
// 申請(qǐng)全新的數(shù)組空間（新容量是舊容量的 1.5 倍）
capacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[capacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[realIndex(i)];
}
// elements 指針指向新數(shù)組
this.elements = newElements;
// 隊(duì)頭 front 指向 0
front = 0;
System.out.println(oldCapacity + "擴(kuò)容為" + capacity);
}
private void print(String s, E[] es) {
System.out.println("s = " + s);
for (E e : es) {
System.out.println(e);
}
System.out.println("s = " + s);
}
/**
* 取出隊(duì)首元素, 并刪之（出隊(duì)）
*
* @return 隊(duì)首元素
*/
public E deQueue() {
E frontElem = elements[front];
elements[front] = null;
front = realIndex(1);
size--;
return frontElem;
}
/**
* 清空隊(duì)列
*/
public void clear() {
for (E element : elements) {
element = null;
}
size = 0;
front = 0;
}
public int realIndex(int index) {
return (front + index) % elements.length;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{size=").append(size).
append(", capacity=").append(elements.length).
append(", [");
for (int i = 0; i < elements.length; i++) {
// 不是第 0 個(gè)元素就拼接【, 】
if (i != 0) {
sb.append(", ");
}
sb.append(elements[i]);
}
sb.append("]}");
return sb.toString();
}
}
七、循環(huán)雙端隊(duì)列
?? 用數(shù)組實(shí)現(xiàn)并且優(yōu)化之后的隊(duì)列也叫做：循環(huán)隊(duì)列（Circle Queue）
?? 循環(huán)雙端隊(duì)列不需要存在一個(gè)叫做
rear的變量來存儲(chǔ)隊(duì)尾元素的下標(biāo)
?? 隊(duì)尾元素的下標(biāo):front + size - 1文章來源：http://www.zghlxwxcb.cn/news/detail-530566.html
略…文章來源地址http://www.zghlxwxcb.cn/news/detail-530566.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】7、隊(duì)列（Queue）的實(shí)現(xiàn)【用棧實(shí)現(xiàn)隊(duì)列】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![【LeetCode】數(shù)據(jù)結(jié)構(gòu)題解（12）[用棧實(shí)現(xiàn)隊(duì)列]](https://imgs.yssmx.com/Uploads/2024/02/635811-1.png)
