目錄
Orignal From: 用隊列實現棧,用棧實現隊列,聽起來有點繞,都搞懂了就掌握了精髓!
- 一、背景
- 二、概念
- 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: 用隊列實現棧,用棧實現隊列,聽起來有點繞,都搞懂了就掌握了精髓!
留言
張貼留言