1.概念

隊列 : 只允許在一段進行插入數據操操作 , 在另一端進行刪除數據操作的特殊線性表 ; 隊列是先進先出

入隊列 : 進行插入操作的一端稱為隊尾

出隊列 : 進行刪除操作的一端稱為對頭

2.隊列的使用

在Java中 , Queue 是一個接口 , 底層通過鏈表實現的

public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();queue.offer(11);//添加元素到隊尾queue.offer(12);queue.offer(13);queue.offer(14);queue.offer(15);System.out.println(queue);//打印隊列  [11, 12, 13, 14, 15]int a1 = queue.poll();//移除頭元素,并返回System.out.println(a1);//11System.out.println(queue);//[12, 13, 14, 15]int a2 = queue.peek();//獲取隊頭元素System.out.println(a2);//12
}

3.隊列的模擬實現

①實現隊列

public class MyQueue {public static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val){this.val = val;}}public int usedSize = 0;public ListNode head = null;public ListNode last = null;public boolean isEmpty(){//檢查是否為空return usedSize == 0;//如果是空的 , usedSize為0 返回true}public void offer(int val){//入隊列,采用的是尾插法ListNode node = new ListNode(val);if(isEmpty()){head = last =  node;//把node節點賦值給head和lastusedSize++;}else {last.next = node;node.prev = last;last = node;usedSize++;}}public int poll(){//相應的出隊列應該采用,頭刪法if(isEmpty()) {return -1;}int vall = head.val;head = head.next;if(head != null){head.prev = null;}usedSize--;return vall;}public int size(){//返回大小return usedSize;}}

②測試

public static void main(String[] args) {MyQueue myQueue = new MyQueue();myQueue.offer(11);//添加元素到隊尾myQueue.offer(12);myQueue.offer(13);myQueue.offer(14);myQueue.offer(15);System.out.println(myQueue.poll());
}

4.循環隊列

• 循環隊列是一種線性數據結構，其操作表現基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個循環。它也被稱為“環形緩沖器”
• 循環隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間
• 但是使用循環隊列，我們能使用這些空間去存儲新的值

class MyCircularQueue {public int front;public int rear;public int[] elem;public MyCircularQueue(int k) {elem = new int[k+1];}//入隊列 public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] = value;rear = (rear+1)%elem.length;return true;}//出隊列 public boolean deQueue() {if(isEmpty()) {return false;}front = (front+1)%elem.length;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.雙端隊列(Deque)

雙端隊列 是 指允許兩端都可以進行入隊和出隊操作的隊列

Deque是一個接口, 使用時 必須創建LinkedList對象

Deque的接口比較多 , 棧和隊列均可以實現該接口

public static void main(String[] args) {Deque<Integer> stack = new LinkedList<>();//雙端隊列的鏈式實現Deque<Integer> queue = new ArrayDeque<>();//雙端隊列的線性實現
}

6.用隊列實現棧

1. 模擬的入棧操作 : 將元素放到不為空的隊列中
2. 模擬的出棧操作 : 把不為空的隊列中的size-1個元素放到另一個隊列中 ; 最后剩下的就是模擬棧中的頂層元素

import java.util.LinkedList;
import java.util.Queue;class MyStackUseQueue {public Queue<Integer> qu1;public Queue<Integer> qu2;public MyStackUseQueue() {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++) {qu2.offer( qu1.poll());}return qu1.poll();}else  {int size = qu2.size();for(int i = 0;i < size-1;i++) {qu1.offer( qu2.poll());}return qu2.poll();}}public int top() {if(empty()) {return -1;}if(!qu1.isEmpty()) {int size = qu1.size();int val = 0;for(int i = 0;i < size;i++) {val = qu1.poll();qu2.offer(val);}return val;}else  {int size = qu2.size();int val = 0;for(int i = 0;i < size;i++) {val = qu2.poll();qu1.offer(val);}return val;}}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}

7.用棧實現隊列

1. 模擬入隊操作 : 放到第一個棧中
2. 模擬出隊操作 : 判斷第二個棧是否為空 ?

如果為空 : 需要把第一個棧中的所有元素都放到第二個棧里 , 取出第二個棧中的頂層元素

如果不為空 : 直接取出第二個棧中的頂層元素

import java.util.ArrayDeque;class MyQueueUseStack {public ArrayDeque<Integer> stack1;public ArrayDeque<Integer> stack2;public MyQueueUseStack() {stack1 = new  ArrayDeque<>();stack2 = new  ArrayDeque<>();}public void push(int x) {stack1.push(x);}public int pop() {if(empty()) {return -1;}if(stack2.isEmpty()) {//第一個棧里面所有的元素 放到第二個棧當中 while(!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(empty()) {return -1;}if(stack2.isEmpty()) {//第一個棧里面所有的元素 放到第二個棧當中 while(!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}