目錄
- 一、背景
- 二、概念
- 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());
}
}
四、總結
通過以上堆疊和佇列相互交叉的實踐，我們對堆疊和佇列的重大特性有了深入了解：
- 堆疊和佇列都是線性連續結構，增加和洗掉元素不會影響破此連續性
- 堆疊通過堆疊頂的操作實作元素的增加與洗掉，也即只能在一端進行操作
- 佇列通過隊尾增加元素，隊頭洗掉元素，也即可以在兩端操作
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/167805.html
標籤：Java