數據結構——隊列（Java）

一.基本概念

隊列用來存儲邏輯關系為“一對一”的數據，是一種“特殊”的線性存儲結構。

特點：

?先進先出：隊列中元素的添加（入隊enqueue）和移除（出隊dequeue）遵循先進先出的原
則。
?端點：隊列有兩個主要的端點——隊頭（front）和隊尾（rear）。隊頭是隊列中最先入隊
的元素所在的位置，而隊尾則是最后入隊的元素所在的位置。

強調：棧和隊列不要混淆，棧是一端開口、另一端封口，元素入棧和出棧遵循“先進后出”原則；隊列是兩端都開口，但元素只能從一端進，從另一端出，且進出隊列遵循“先進先出”的原則。

????????實現方法：

? ? ? ? 1.順序表實現

????????2.鏈表實現

以鏈表的方式為例子

二.鏈表實現隊列

? ? ? ? 隊列的API設計

隊列初始化

? ? ? ?

class Queue <T>
{//結點類class Node{public T data;//存儲數據public Node next;//下一個結點public Node(T data , Node next){this.data = data;this.next = next;}}//創建首結點private Node head;//尾結點private Node last;//隊列個數private int N;public Queue(){this.head =new Node(null,null);this.last =null;this.N =0;}

判斷隊列是否為空

思路分析：用布爾類型，直接返回數量

 //判斷隊列是否為空public boolean isEmpty(){return N == 0;}

獲取隊列個數

思路分析：直接返回數量

//返回隊列元素個數public int size(){return N;}

插入元素

思路分析：

1.如果隊列為空，將頭結點指向新結點

2.創建變量1代替原先尾結點的數據

3.創建一個變量2當尾結點

4.將變量1的next引用指向變量2的值

 //插入元素public void enqueue(T data){//保存當前的尾結點Node oldLast = last;//創建新結點為新的尾結點last = new Node(data, null);//判斷隊列是否為空if(isEmpty()){head.next = last;}else{//將原先尾結點的next指向新結點oldLast.next = last;}N++;}

元素取出

思路分析：根據先進先出原則，我們需要更新頭結點的next所指向的值

 //從隊列拿出一個元素public T dequeue(){//為空，返回nullif(isEmpty()){return null;}//保存當前首結點Node oldFirst = head.next;//將首結點更新到下一個結點head.next = oldFirst.next;N--;//如果隊列被刪除完了，重置Last為nullif(isEmpty()){last = null;}return oldFirst.data;//返回取出元素}

三.用棧來實現隊列

思路分析：

棧是后進先出（LIFO）的數據結構，隊列是先進先出（FIFO）的數據結構。我們可以使用兩個棧，一個用于入隊操作（記為?inStack?），一個用于出隊等操作（記為?outStack?）。?

當執行?push?操作時，直接將元素壓入?inStack?。因為?inStack?只負責接收新元素，就像隊列的尾部接收新元素一樣。?

當執行?pop?和?peek?操作時，需要先判斷?outStack?是否為空。如果?outStack?為空，就將?inStack?中的所有元素依次彈出并壓入?outStack?，此時?outStack?棧頂元素就是隊列的開頭元素（因為?inStack?中先進入的元素會在轉移到?outStack?后處于棧頂）。然后再執行相應的?pop?或?peek?操作。?

執行?empty?操作時，只需判斷?inStack?和?outStack?是否都為空。??

完整代碼

import java.util.Stack;class MyQueue {private Stack<Integer> inStack; // 用于入隊操作的棧private Stack<Integer> outStack; // 用于出隊等操作的棧public MyQueue() {inStack = new Stack<>(); // 初始化入隊棧outStack = new Stack<>(); // 初始化出隊棧}public void push(int x) {inStack.push(x); // 將元素x壓入入隊棧，模擬隊列的入隊操作}public int pop() {if (outStack.isEmpty()) { // 如果出隊棧為空while (!inStack.isEmpty()) { // 當入隊棧不為空時outStack.push(inStack.pop()); // 將入隊棧的元素依次彈出并壓入出隊棧}}return outStack.pop(); // 彈出并返回出隊棧的棧頂元素，即隊列開頭的元素}public int peek() {if (outStack.isEmpty()) { // 如果出隊棧為空while (!inStack.isEmpty()) { // 當入隊棧不為空時outStack.push(inStack.pop()); // 將入隊棧的元素依次彈出并壓入出隊棧}}return outStack.peek(); // 返回出隊棧的棧頂元素，即隊列開頭的元素（不彈出）}public boolean empty() {return inStack.isEmpty() && outStack.isEmpty(); // 判斷入隊棧和出隊棧是否都為空，都為空則隊列空}
}
public class StudentMS4
{public static void main(String[] args){MyQueue myQueue = new MyQueue();//調用pushmyQueue.push(1);myQueue.push(2);//調用peekSystem.out.println("隊列開頭的元素是："+myQueue.peek());//調用popSystem.out.println("移除并返回隊列開頭的元素："+myQueue.pop());//調用empty方法System.out.println("隊列是否為空："+myQueue.empty());}
}