java有幾種方式實現隊列

這篇文章將為大家詳細講解有關java中幾種實現隊列的方式，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

在計算機操作系統里，有各種隊列在安靜地工作著。打印作業在打印隊列中等待打印。當在鍵盤上敲擊時，也有一個存儲鍵入內容的隊列。同樣，如果使用文字處理程序敲擊一個鍵，而計算機又暫時要做其它的事，敲擊的內容不會丟失，它會排在隊列中等待，直到文字處理程序有時間來讀取它。利用隊列保證了鍵入內容在處理時其順序不會改變。

隊列的兩個基本操作是inserting(插入)一個數據項，即把一個數據項放入隊尾，另一個是removing(移除)一個數據項，即移除隊頭的數據項。這類似于電影愛好者排隊買票時先排到隊尾，然后到達隊頭買票后離開隊列。

棧中的插入和移除數據項方法的命名是很標準，稱為push和pop。隊列的方法沒有標準化的命名。"插入"可以稱為put、add或enque，而"刪除"可以叫delete、get或deque。插入數據項的隊尾，也可以叫作back、tail或end。而移除數據項的隊頭，也可以叫head。下面將使用insert、remove、front和rear。

隊列有3種實現方式，實現方式為：

1、使用兩個棧來實現一個隊列。

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

實現方法是：

創建兩個棧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();
}
}

2、基于鏈表來實現隊列：

首先添加一個節點類，作為隊列中的節點元素

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<E> {
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;
}
 
}

3、使用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<E> {
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;
}
}

關于java中幾種實現隊列的方式就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。