跳到主要內容

用隊列實現棧,用棧實現隊列,聽起來有點繞,都搞懂了就掌握了精髓!

目錄

  • 一、背景

  • 二、概念

    • 2.1 棧

    • 2.2 隊列


  • 三、棧和隊列的相互實現

    • 3.1 用隊列實現棧

    • 3.2 用棧實現隊列


  • 四、總結



一、背景


棧和隊列是數據結構中最常用到的兩種結構,有非常廣泛的運用,該篇文章將通過動畫的手段,展示棧和隊列相互實現的底層原理,讓我們真正搞懂棧和隊列的特性。


二、概念


2.1 棧


棧[Stack]:是一種限定僅在表尾進行插入和刪除操作的線性表;即後進先出(LIFO-last in first out),最後插入的元素最先出來




  • 入棧(push)

  • 出棧 (pop)


2.2 隊列


 隊列[Queue]:是一種限定僅在表頭進行刪除操作,僅在表尾進行插入操作的線性表;即先進先出(FIFO-first in first out):最先插入的元素最先出來。




  • 入隊(enqueue)


  • 出隊(dequeue)


三、棧和隊列的相互實現


3.1 用隊列實現棧


  • 模擬入棧的實現原理
    -- 棧的特性是新加入的元素出現在棧頂,保證後進先出。
    -- 隊列的特性為新加入的元素出現在隊尾,隊列的隊尾元素最後出隊。
    -- 按以上兩個前提,我們可以讓隊頭至隊尾前的其它所有元素依次出隊再入隊,直至在隊尾新加入的元素被移到隊頭,也即實現了讓新壓入的元素保留在棧頂


  • 模擬出棧的實現原理
    -- 由於在入棧時保證隊列中新加入隊尾的元素被移到了隊頭,出棧只需彈出隊頭元素即可。


  • 完整代碼實現



/**
* 用隊列模擬實現棧
*
* @author zhuhuix
* @date 2020-06-09
*/
public class QueueImplStack {

// 定義隊列
private Queue<Integer> queue;

public QueueImplStack() {
queue = new LinkedList();
}

// 入棧--在隊尾加入元素后,讓其他元素按順序出隊再入隊,保持新加入的元素永遠在隊頭
public void push(Integer e) {
queue.offer(e);
int size = queue.size();
int i = 0;
while (i < size - 1) {
queue.offer(queue.poll());
i++;
}
}

// 出棧--將隊尾前的其它所有元素出隊再入隊,直至隊尾元素移到隊頭
public Integer pop() {
return queue.poll();
}

// 查看棧頂元素--即隊頭元素
public Integer peek() {
return queue.peek();
}

// 是否為空
public boolean isEmpty() {
return queue.isEmpty();
}

public static void main(String[] args) {
QueueImplStack stack = new QueueImplStack();
stack.push(1);
System.out.println(stack.peek());
stack.push(2);
System.out.println(stack.peek());
stack.push(3);
System.out.println(stack.peek());
System.out.println("=============");
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());

}
}


3.2 用棧實現隊列


  • 模擬入隊的實現原理
    -- 隊列的特性最新入隊的元素需排在隊尾,最先入隊的元素排在隊頭,按隊頭到隊尾的順序依次出隊。
    -- 對應到棧的數據結構上,也即需將新加入的元素保留在棧頂,保證先進先出。
    -- 按以上兩個前提,需在存放數據的棧的基礎上再增加一個輔助棧,在每次入隊時,先將存放數據的棧彈入輔助棧,再把需加入的新元素壓入數據棧底,最後把輔助棧中的元素彈出依次壓入數據棧,這樣保證了新加入的元素,沉在棧底。

    - 模擬出隊的實現原理
    -- 由於在入隊時,通過數據棧與輔助棧的交換,實現了后加入的元素沉在棧底,先進入的元素保留在棧頂,直接通過出棧彈出即可。

    • 完整代碼實現



/**
* 用棧模擬實現隊列
*
* @author zhuhuix
* @date 2020-06-09
*/
public class StackImplQueue {
// 數據棧
private Stack<Integer> stack;
// 輔助棧
private Stack<Integer> aux;

StackImplQueue() {
stack = new Stack<>();
aux = new Stack<>();
}

// 入隊--通過數據棧與輔助棧相互交換,保證新加入的元素沉在數據棧底
public void enqueue(Integer e) {
while (!stack.isEmpty()) {
aux.push(stack.pop());
}
stack.push(e);
while(!aux.isEmpty()){
stack.push(aux.pop());
}

}

// 出隊--彈出數據棧元素
public Integer dequeue(){
return stack.pop();
}

// 查看隊頭元素
public Integer peek(){
return stack.peek();
}

// 是否為空
public boolean isEmpty(){
return stack.isEmpty();
}

public static void main(String[] args) {
StackImplQueue queue = new StackImplQueue();
queue.enqueue(1);
System.out.println(queue.peek());
queue.enqueue(2);
System.out.println(queue.peek());
queue.enqueue(3);
System.out.println(queue.peek());
System.out.println("=============");
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());

}
}


四、總結


通過以上棧和隊列相互交叉的實踐,我們對棧和隊列的重大特性有了深入了解:



  • 棧和隊列都是線性連續結構,增加和刪除元素不會影響破此連續性

  • 棧通過棧頂的操作實現元素的增加與刪除,也即只能在一端進行操作

  • 隊列通過隊尾增加元素,隊頭刪除元素,也即可以在兩端操作

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】



※為什麼 USB CONNECTOR 是電子產業重要的元件?



網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!



※台北網頁設計公司全省服務真心推薦



※想知道最厲害的網頁設計公司"嚨底家"!



※推薦評價好的iphone維修中心



網頁設計最專業,超強功能平台可客製化



※別再煩惱如何寫文案,掌握八大原則!



Orignal From: 用隊列實現棧,用棧實現隊列,聽起來有點繞,都搞懂了就掌握了精髓!

留言

這個網誌中的熱門文章

掃地機器人可以隨身帶上飛機嗎?我想要拿去送給國外的朋友

掃地機器人如果要隨身戴上飛機需要滿足兩個條件: 一個是掃地機器人連同你的隨身行李,整體的體積和重量要符合上機條件,這個具體每家航空公司都不同,可以諮詢,簡單的說就是隨身行李不要超寬超重。 還有一個就是由於掃地機器人內置了鋰電池,所以內置電池的容量要符合相關規定,每個掃地機器人電池容量都不同,具體自行查詢。 根據民航的相關安全要求,凡帶有鋰電池的電子設備均不可以托運,但符合重量要求,尺寸要求以及電量要求的鋰電池及其設備是可以帶上飛機的。 《鋰電池航空運輸規範》中內含鋰離子電池的設備電池額定能量不應超過100Wh的規定,符合國標GB31241-2014,並通過UN38.3航空運輸認證等國際安全標準,所以可以帶上飛機。但是不能托運,只能隨身攜帶。 掃地機器人     掃地機器人     掃地機器人吸塵器 http://www.greenh3y.com/?p=400 Orignal From: 掃地機器人可以隨身帶上飛機嗎?我想要拿去送給國外的朋友

不滿國際規範斷財路 非洲多國擬退野生動保公約

摘錄自2019年09月01日中央通訊社非洲報導 非洲南部多國揚言退出「瀕臨絕種野生動植物國際貿易公約」,因為公約多數成員拒絕放寬象牙與犀牛角交易,並且幾乎全面禁止將野生捕獲的大象送到動物園。 這個公約嚴格規範全球野生動物交易,包括限制象牙與犀牛角交易。 本週在日內瓦召開修訂「瀕臨絕種野生動植物國際貿易公約」(CITES)的會議期間,由於區域集團非南開發共同體(SADC)的多項提案遭否決,這個集團與公約的關係惡化。 全球大象數量最多的區域波札那、納米比亞與辛巴威要求販售取自自然死亡、充公與汰除的大象象牙,這項提議被居多數的101票否決。 40多年前制訂的CITES規範約3萬6000種動植物交易,並設計有助於遏止非法交易和制裁違規國家的機制。 不過有16個成員國的非南開發共同體部分會員批評CITES對非洲國家的問題視若無睹。 坦尚尼亞環境部長西蒙巴徹恩(George Simbachawene)於日內瓦召開的會議中表示:「結果無法採取進步、公平、包容與基於科學的的保育策略。」 他說:「該是認真重新考慮我們加入CITES是否有任何實質益處的時候了。」 本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理 【搬家相關資訊指南】 台中搬家 , 彰化搬家 , 南投搬家 前需注意的眉眉角角,別等搬了再說! 避免吃悶虧無故遭抬價! 台中搬家公司 免費估價,有契約讓您安心有保障! 評比 彰化搬家公司費用 , 南投搬家公司費用 收費行情懶人包大公開 彰化搬家費用 , 南投搬家費用 ,距離,噸數怎麼算?達人教你簡易估價知識! Orignal From: 不滿國際規範斷財路 非洲多國擬退野生動保公約

全球第一國 帛琉立法禁用、禁售防曬乳

摘錄自2018年11月2日蘋果日報帛琉報導 為了保護珊瑚礁生態,帛琉政府昨(1)日表示已立法嚴禁販售並使用防曬乳,此法將於2020年1月1日起正式生效。帛琉也成為全球首個全面禁止防曬乳的國家。 帛琉國會上周通過此法案,全面禁止使用和販售含有10種有害化學物質的防曬乳,違者將被處以1000美元(約3萬783元台幣)罰款。若遊客被發現私帶防曬乳入境,也會遭到沒收。帛琉總統雷蒙傑索(Tommy Remengesau)說:「沒收(防曬乳)已經足夠讓人不進行商業使用,而這也是很聰明的一招,一方面教育觀光客,又不會把他們嚇跑。」 根據官方說法,帛琉的熱門潛水點每小時會有4艘載著觀光客的船隻造訪,他們身上的防曬乳化學物質相當可觀。總統府發言人說:「帛琉各潛水和浮潛地點每天都有好幾加崙的防曬乳入海。我們只是盡力要防止環境遭受污染。」 本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理 【其他文章推薦】 ※ 台中搬家 , 彰化搬家 , 南投搬家 前需注意的眉眉角角,別等搬了再說! ※在找尋 搬家 公司嗎? ※搬家不受騙不被宰 桃園搬家公司 , 桃園市搬家公司 公開報價讓你比價不吃虧! Orignal From: 全球第一國 帛琉立法禁用、禁售防曬乳