隊列有幾種實作方式？

佇列有3種實作方式，分別為：1、基於鍊錶來實作佇列；2、使用linkedList來實作佇列；3、使用兩個堆疊來實作一個佇列。

佇列有3種實作方式，實作方式為：

1、基於鍊錶來實現佇列：

首先新增一個節點類，作為佇列中的節點元素

public class Node {//链表中的一个节点
Node next = null;
int data;
//构造函数，用于添加链表时候使用
public Node(int d) {
this.data = d;
};
}

再新建一個類別作為我們的佇列，在該類別中實作佇列的入隊和出隊以及求隊列的長度和判斷隊列是否為空等方法

①入隊操作：

             首先透過函數參數傳入要入隊的數據，根據傳入的參數，新增一個節點Node，在入隊方法中判斷該隊列是否為空，若該隊列為空（head==tail）,則該入隊的節點既是隊頭也是隊尾。若佇列不為空，則將尾節點tail的next指標指向該元素，然後將tail節點指向該節點。

public void put(Integer data) {
Node newNode = new Node(data);//构造一个新节点
if(head == null && tail == null) {//队列为空
head = newNode;
tail = newNode;
}else {
tail.next = newNode;
tail = newNode;
}
}

②出隊操作：

若佇列為空，則回傳空。若佇列不為空，則傳回該佇列的頭結點，然後將頭結點的下一個元素重新作為頭節點

public Integer pop() {
if(this.isEmpty()) {
return null;
}
int data = head.data;
head = head.next;
return data;
}

③判斷佇列空和對列長度很簡單，直接貼程式碼，不再多說。

public int size() {
int count = 0;
Node tmp = head;
while(tmp != null) {
count++;
tmp = tmp.next;
}
return count;
}

④詳細程式碼實作：

package com.wp.datastruct;
 
/**
 * 利用链表来实现队列
 * */
public class MyQueue {
Node head = null;//队列头
Node tail = null;//队列尾
/**
* 入队操作：
* 若该队列尾空，则入队节点既是头结点也是尾节点
* 若队列不为空，则先用tail节点的next指针指向该节点
* 然后将tail节点指向该节点
* */
public void put(Integer data) {
Node newNode = new Node(data);//构造一个新节点
if(head == null && tail == null) {//队列为空
head = newNode;
tail = newNode;
}else {
tail.next = newNode;
tail = newNode;
}
}
/**
* 判断队列是否为空：当头结点等于尾节点的时候该队列就为空
* */
public boolean isEmpty() {
return head == tail;
}
/**
* 出队操作：
* 若队列为空，则返回null
* 否则，返回队列的头结点，并将head节点指向下一个
* */
public Integer pop() {
if(this.isEmpty()) {
return null;
}
int data = head.data;
head = head.next;
return data;
}
public int size() {
int count = 0;
Node tmp = head;
while(tmp != null) {
count++;
tmp = tmp.next;
}
return count;
}
 
}

2、使用linkedList來實作佇列

該方法是使用java中的linkedList集合來實作一個佇列，透過呼叫linkedList中的方法來實現佇列的入隊出隊，判空等操作

首先new一個類別來作為我們的佇列，該類別中包含兩個屬性，一個是size：用來統計該佇列的長度，另一個是LinkedList對象，

代表我們的佇列。

private LinkedList<E> list = new LinkedList<>();
private int size = 0;//用于统计队列的长度

①入隊操作：

應該為linkedList集合中已經實現好了添加刪除操作，在這裡我們只需要簡單的調用方法就可以實現隊列的相關操作了，非常簡單又容易理解。

public synchronized void put(E data) {//保证线程安全，实现同步操作
list.add(data);
size++;
}

②出隊操作：

public synchronized E pop() {
size--;
return list.removeFirst();//从头取出
}

③詳細程式碼：

public class MyQueue2 {
private LinkedList<E> list = new LinkedList<>();
private int size = 0;//用于统计队列的长度
public synchronized void put(E data) {//保证线程安全，实现同步操作
list.add(data);
size++;
}
public synchronized E pop() {
size--;
return list.removeFirst();//从头取出
}
public synchronized int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}

 

3、使用兩個堆疊來實作一個佇列。

也可以使用兩個實作好的堆疊來實作一個佇列（這個問題可能面試筆試的時候回被問到）。

實作方法是：

建立兩個堆疊s1,s2。入隊的時候就只壓棧到s1中。

出隊分兩種情況：1.當s2不為空的使用，就彈出棧頂元素作為出隊元素。

                             2.當s2等於空，則先將s1中的元素全部彈出到s2中，再從s2中彈出棧頂元素作為出隊元素。

 

①入隊：

public synchronized void put(E data) {//使用同步处理，保证线程安全
s1.push(data);
}

②出隊:

public synchronized E pop() {
if(!s2.isEmpty()) {
return s2.pop();
}else {
s2.push(s1.pop());
return s2.pop();
}
}

③.詳細程式碼實作：

package com.wp.datastruct;
 
import java.util.Stack;
 
/**
 * 利用两个栈来模拟队列操作
 * 入队操作就只是想栈s1中添加，
 * 出栈操作分为两部分：
 * 1.当s2中不为空的时候，就直接弹出s2中的栈顶数据
 * 2.当s2中为空的时候，就先把s1中的数据全部弹出到s2中然后将栈顶数据出栈
 * 
 * */
public class MyQueue3<E> {
Stack<E> s1 = new Stack<>();
Stack<E> s2 = new Stack<>();
public synchronized void put(E data) {//使用同步处理，保证线程安全
s1.push(data);
}
public synchronized E pop() {
if(!s2.isEmpty()) {
return s2.pop();
}else {
s2.push(s1.pop());
return s2.pop();
}
}
public synchronized boolean isEmpty() {
return s1.isEmpty() && s2.empty();
}
}

 推薦教學： 《php影片教學》

以上是隊列有幾種實作方式？的詳細內容。更多資訊請關注PHP中文網其他相關文章！