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

一、背景

二、概念
- 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: 用隊列實現棧，用棧實現隊列，聽起來有點繞，都搞懂了就掌握了精髓！

3C資訊

搜尋此網誌