本系列博客習(xí)題來(lái)自《算法(第四版)》，算是本人的讀書筆記宜雀，如果有人在讀這本書的切平，歡迎大家多多交流。為了方便討論辐董，本人新建了一個(gè)微信群(算法交流)悴品，想要加入的，請(qǐng)?zhí)砑游业奈⑿盘?hào)：zhujinhui207407 謝謝简烘。另外苔严，本人的個(gè)人博客 http://www.kyson.cn 也在不停的更新中，歡迎一起討論
知識(shí)點(diǎn)
- 兩個(gè)棧實(shí)現(xiàn)的隊(duì)列
題目
1.4.27 兩個(gè)棧實(shí)現(xiàn)的隊(duì)列孤澎。用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列届氢，使得每個(gè)隊(duì)列操作所需要的堆棧操作均攤后為一個(gè)常數(shù)。提示：如果將所有元素壓入棧再?gòu)棾龈残瘢鼈兊捻樞蚓捅活嵉沽送俗印Ｈ绻俅沃貜?fù)這個(gè)過程，它們的順序則會(huì)復(fù)原型将。
1.4.27 Queue with two stacks. Implement a queue with two stacks so that each queue operation takes a constant amortized number of stack operations. Hint: If you push elements onto a stack and then pop them all, they appear in reverse order. If you repeat this process, they’re now back in order.
分析
這道題要寫出來(lái)不難寂祥，但要符合“均攤后是一個(gè)常數(shù)”比較復(fù)雜。下面我們演示一下優(yōu)化過程七兜。
首先丸凭，我們使用兩個(gè)棧，暫且命名為stack1和stack2腕铸，我們可以這么操作：stack1用于存儲(chǔ)數(shù)據(jù)惜犀，stack2用于緩存。因此不難得出如下代碼：
public class QueueWithTowStacks<T> {
private Stack<T> stack1 ;
private Stack<T> stack2 ;
public QueueWithTowStacks(){
stack1 = new Stack<T>();
stack2 = new Stack<T>();
}
public void enqueue(T item){
stack1.push(item);
}
public T dequeue(){
if (stack1.size() < 1 && stack2.size() < 1)
{
System.out.println("Queue is empty");
return null;
}
//把stack1清空
while (stack1.size() > 1){
T element = stack1.pop();
stack2.push(element);
}
T ele = stack1.pop();
//把stack2 清空
while (stack2.size() > 0){
T element = stack2.pop();
stack1.push(element);
}
return ele;
}
public static void main(String[] args){
QueueWithTowStacks gfg = new QueueWithTowStacks();
gfg.enqueue("我的");
gfg.enqueue("名字");
gfg.enqueue("叫");
gfg.enqueue("頂級(jí)程序員不穿女裝");
gfg.enqueue("微博:https://m.weibo.cn/p/1005056186766482");
System.out.print(gfg.dequeue());
System.out.print(gfg.dequeue());
System.out.print(gfg.dequeue());
System.out.print(gfg.dequeue());
System.out.print(gfg.dequeue());
}
}
以上代碼在這里可以找到：QueueWithTowStacks.java
關(guān)于棧（Stack）的實(shí)現(xiàn)恬惯，如果大家還有疑問的向拆，可以查看我之前的博客：算法練習(xí)(26):Stack概念(1.3.1-1.3.2)，里面給出了棧的具體實(shí)現(xiàn)酪耳。
我們可以發(fā)現(xiàn)，每次enqueue是常數(shù)級(jí)別的，但每次dequeue就比較復(fù)雜碗暗，需要遍歷兩個(gè)stack颈将，假設(shè)Queue的總長(zhǎng)度為N，那么每次dequeue需要線性級(jí)別的復(fù)雜度言疗，所以跟題目的要求顯然不符合晴圾，所以我們接著優(yōu)化。
其實(shí)在做這一題之前噪奄，我們可以看到書中有類似的描述死姚，關(guān)于均攤分析的：
書中關(guān)于均攤分析的描述中，說(shuō)道了動(dòng)態(tài)調(diào)整數(shù)組的平均次數(shù)為常數(shù)勤篮。所以我們可以把這個(gè)思想用到這道題中：
出隊(duì)時(shí)都毒，判斷s2是否為空，如不為空碰缔，則直接彈出頂元素账劲；如為空，則將s1的元素逐個(gè)“倒入”s2金抡，把最后一個(gè)元素彈出并出隊(duì)瀑焦。這樣一來(lái)避免了反復(fù)“倒”棧，僅在需要時(shí)才“倒”一次梗肝。
答案
public class QueueWithTwoStacksFaster<T> {
private Stack<T> stack1 ;
private Stack<T> stack2 ;
public QueueWithTwoStacksFaster(){
stack1 = new Stack<T>();
stack2 = new Stack<T>();
}
public void enqueue(T item){
stack1.push(item);
}
public T dequeue() throws Exception {
if (stack1.size() < 1 && stack2.size() < 1)
{
throw new Exception("Queue is empty");
}
T ele = null;
//Stack2為空榛瓮，則將Stack1倒入Stack2
if (stack2.size() < 1){
while (stack1.size() > 1){
T element = stack1.pop();
stack2.push(element);
}
ele = stack1.pop();
}else{
ele = stack2.pop();
}
return ele;
}
public static void main(String[] args){
QueueWithTwoStacksFaster queueWithTwoStacksFaster = new QueueWithTwoStacksFaster();
queueWithTwoStacksFaster.enqueue("我的");
queueWithTwoStacksFaster.enqueue("名字");
queueWithTwoStacksFaster.enqueue("叫");
queueWithTwoStacksFaster.enqueue("頂級(jí)程序員不穿女裝");
queueWithTwoStacksFaster.enqueue("微博:https://m.weibo.cn/p/1005056186766482");
try {
System.out.print(queueWithTwoStacksFaster.dequeue());
System.out.print(queueWithTwoStacksFaster.dequeue());
System.out.print(queueWithTwoStacksFaster.dequeue());
System.out.print(queueWithTwoStacksFaster.dequeue());
System.out.print(queueWithTwoStacksFaster.dequeue());
} catch (Exception e) {
e.printStackTrace();
}
}
}
代碼索引
廣告
我的首款個(gè)人開發(fā)的APP壁紙寶貝上線了，歡迎大家下載巫击。
