java是如何實現隊列的

java是如何實現隊列的？針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

隊列是一種特殊的線性表，遵循的原則就是“先入先出”。在我們日常使用中，經常會用來并發操作數據。在并發編程中，有時候需要使用線程安全的隊列。如果要實現一個線程安全的隊列通常有兩種方式：一種是使用阻塞隊列，另一種是使用線程同步鎖。

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

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

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();
}
}

關于java是如何實現隊列的問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。