java有幾種方式實現(xiàn)隊列

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

成都創(chuàng)新互聯(lián)公司是一家專業(yè)提供水城企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站制作、做網(wǎng)站、HTML5建站、小程序制作等業(yè)務(wù)。10年已為水城眾多企業(yè)、政府機構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)絡(luò)公司優(yōu)惠進行中。

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

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

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

隊列有3種實現(xiàn)方式，實現(xiàn)方式為：

1、使用兩個棧來實現(xiàn)一個隊列。

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

實現(xiàn)方法是：

創(chuàng)建兩個棧s1,s2。入隊的時候就只壓棧到s1中。

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

2.當(dāng)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();
}
}

③.詳細代碼實現(xiàn)：

package com.wp.datastruct;
 
import java.util.Stack;
 
/**
 * 利用兩個棧來模擬隊列操作
 * 入隊操作就只是想棧s1中添加，
 * 出棧操作分為兩部分：
 * 1.當(dāng)s2中不為空的時候，就直接彈出s2中的棧頂數(shù)據(jù)
 * 2.當(dāng)s2中為空的時候，就先把s1中的數(shù)據(jù)全部彈出到s2中然后將棧頂數(shù)據(jù)出棧
 * 
 * */
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、基于鏈表來實現(xiàn)隊列：

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

public class Node {//鏈表中的一個節(jié)點
Node next = null;
int data;
//構(gòu)造函數(shù)，用于添加鏈表時候使用
public Node(int d) {
this.data = d;
};
}

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

①入隊操作：

首先通過函數(shù)參數(shù)傳入要入隊的數(shù)據(jù)，根據(jù)傳入的參數(shù)，新增一個節(jié)點Node，在入隊方法中判斷該隊列是否為空，若該隊列為空（head==tail）,則該入隊的節(jié)點既是隊頭也是隊尾。若隊列不為空，則將尾節(jié)點tail的next指針指向該元素，然后將tail節(jié)點指向該節(jié)點。

public void put(Integer data) {
Node newNode = new Node(data);//構(gòu)造一個新節(jié)點
if(head == null && tail == null) {//隊列為空
head = newNode;
tail = newNode;
}else {
tail.next = newNode;
tail = newNode;
}
}

②出隊操作：

若隊列為空，則返回空。若隊列不為空，則返回該隊列的頭結(jié)點，然后將頭結(jié)點的下一個元素重新作為頭節(jié)點

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

④詳細代碼實現(xiàn)：

package com.wp.datastruct;
 
/**
 * 利用鏈表來實現(xiàn)隊列
 * */
public class MyQueue<E> {
Node head = null;//隊列頭
Node tail = null;//隊列尾
/**
* 入隊操作：
* 若該隊列尾空，則入隊節(jié)點既是頭結(jié)點也是尾節(jié)點
* 若隊列不為空，則先用tail節(jié)點的next指針指向該節(jié)點
* 然后將tail節(jié)點指向該節(jié)點
* */
public void put(Integer data) {
Node newNode = new Node(data);//構(gòu)造一個新節(jié)點
if(head == null && tail == null) {//隊列為空
head = newNode;
tail = newNode;
}else {
tail.next = newNode;
tail = newNode;
}
}
/**
* 判斷隊列是否為空：當(dāng)頭結(jié)點等于尾節(jié)點的時候該隊列就為空
* */
public boolean isEmpty() {
return head == tail;
}
/**
* 出隊操作：
* 若隊列為空，則返回null
* 否則，返回隊列的頭結(jié)點，并將head節(jié)點指向下一個
* */
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來實現(xiàn)隊列

該方法是使用java中的linkedList集合來實現(xiàn)一個隊列，通過調(diào)用linkedList中的方法來實現(xiàn)隊列的入隊出隊，判空等操作

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

代表我們的隊列。

private LinkedList<E> list = new LinkedList<>();
private int size = 0;//用于統(tǒng)計隊列的長度

①入隊操作：

應(yīng)為linkedList集合中已經(jīng)實現(xiàn)好了添加刪除操作，在這里我們只需要簡單的調(diào)用方法就可以實現(xiàn)隊列的相關(guān)操作了，非常簡單而且容易理解。

public synchronized void put(E data) {//保證線程安全，實現(xiàn)同步操作
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;//用于統(tǒng)計隊列的長度
public synchronized void put(E data) {//保證線程安全，實現(xiàn)同步操作
list.add(data);
size++;
}
public synchronized E pop() {
size--;
return list.removeFirst();//從頭取出
}
public synchronized int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}

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

分享文章：java有幾種方式實現(xiàn)隊列
文章轉(zhuǎn)載：http://bm7419.com/article42/phodhc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站維護、網(wǎng)站導(dǎo)航、云服務(wù)器、動態(tài)網(wǎng)站、、域名注冊

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容