劍指offer/LintCode494_用兩個隊列實現一個棧

rose 發布于2019-08-14 18:10 / 1937人閱讀

摘要：劍指用兩個隊列實現一個棧聲明文章均為本人技術筆記，轉載請注明出處解題思路實現功能用兩個隊列實現一個棧，實現，，和方法解題思路假設有隊列和實現棧的操作實現棧操作始終用來入隊實現實現棧的方法模擬棧的過程中，保證兩個隊列中始終有一個隊列為空，另一

劍指offer/LintCode494_用兩個隊列實現一個棧 聲明

文章均為本人技術筆記，轉載請注明出處https://segmentfault.com/u/yzwall

解題思路 實現功能：

用兩個隊列實現一個棧，實現push(element)，pop()，top()和isEmpty()方法；

解題思路

假設有隊列queue1和queue2；

實現棧的push(element)操作

實現棧push(element)操作：始終用來queue1入隊實現；

實現棧的pop()方法

模擬棧的過程中，保證兩個隊列中始終有一個隊列為空，另一個隊列不空，空棧時兩隊列全部為空；；

queue1和queue2運行過程中有時充當from，有時充當to；

非空隊列from中所有元素依次出隊并入隊to隊列中，直到from中只剩下一個元素，

實現pop()操作：彈出from中最后一個元素；

實現top()操作：保存from中最后一個元素并返回，from彈出并入隊to隊列中（保證每次操作完成后，兩個隊列中始終有一個隊列為空，另一個隊列不空，空棧除外）；

注意點

使用java.util.ArrayDeque實現隊列時，切記用offer()方法入隊而不用push()方法，用poll()方法出隊而不用pop()方法；

題目鏈接

lintcode 494: http://www.lintcode.com/en/problem/implement-stack-by-two-queues/;

Java代碼

/**
 * 用兩個隊列實現一個棧
 * http://www.lintcode.com/en/problem/implement-stack-by-two-queues/
 * @author yzwall
 */
import java.util.ArrayDeque;
class Stack {
    private ArrayDeque queue1;
    private ArrayDeque queue2;
    int top;
    
    Stack() {
        this.queue1 = new ArrayDeque<>();
        this.queue2 = new ArrayDeque<>();
    }
    
    // queue1始終負責實現棧的push操作
    public void push(int element) {
        queue1.offer(element);
    }
    
    // 將from隊列元素出隊，并依次入隊到to隊列，直到from隊列中只有一個元素
    public void move(ArrayDeque from,
                     ArrayDeque to) {
        while (from.size() > 1) {
            to.offer(from.poll());
        }
    }
    
    public void pop() {
        if (!isEmpty()) {
            if (!queue1.isEmpty()) {
                move(queue1, queue2);
                // queue1隊列pop后為空
                queue1.poll();
            } else if (!queue2.isEmpty()) {
                move(queue2, queue1);
                // queue1隊列pop后為空
                queue2.poll();
            }
        }
    }
    
    public int top() {
        if (!isEmpty()) {
            if (!queue1.isEmpty()) {
                move(queue1, queue2);
                // 獲取模擬棧頂元素，清空棧頂所在隊列
                top = queue1.peek();
                queue2.offer(queue1.poll());
            } else if (!queue2.isEmpty()) {
                move(queue2, queue1);
                // 獲取模擬棧頂元素，清空棧頂所在隊列
                top = queue2.peek();
                queue1.offer(queue2.poll());
            }
            return top;
        }
        return 0;
    }
    
    public boolean isEmpty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

云服務器 GPU云服務器兩個主體用一個域名兩個域名用一個空間用java實現一個線程池兩個棧

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/67039.html

劍指offer/LintCode40_用兩個棧模擬隊列

摘要：劍指用兩個棧模擬隊列聲明文章均為本人技術筆記，轉載請注明出處解題思路實現功能用兩個棧模擬實現一個隊列的，和操作解題思路假設有兩個棧隊列實現始終用入棧實現隊列和實現由于依次出棧并壓入中，恰好保證中順序與模擬隊列順序一致，始終保證棧頂元素為模擬劍指offer/LintCode40_用兩個棧模擬隊列聲明文章均為本人技術筆記，轉載請注明出處https://segmentfault.com...

bawn 2019-08-14 18:12 評論0 收藏0
劍指offer/LintCode12_最小棧

摘要：劍指最小棧聲明文章均為本人技術筆記，轉載請注明出處解題思路實現功能實現一個最小棧，要求操作均為復雜度，解題思路用棧存儲數據用最小棧存儲中最小元素，保證棧頂元素與棧頂元素同步，表示此時最小值將與此時最小值比較，將更小的一方壓棧，保證中棧頂始終劍指offer/LintCode12_最小棧聲明文章均為本人技術筆記，轉載請注明出處https://segmentfault.com/u/yz...

Betta 2019-08-14 18:12 評論0 收藏0
【轉】《劍指Offer》JavaScript實戰——用兩個棧實現隊列

摘要：題目描述用兩個棧來實現一個隊列，完成隊列的和操作。隊列中的元素為類型。下面是實現代碼。題目描述 ????用兩個棧來實現一個隊列，完成隊列的Push和Pop操作。隊列中的元素為int類型。解題方法 let stack1=[],//兩個數組模擬棧的行為 stack2=[]; function push(node) { // write code here //...

senntyou 2019-08-23 16:22 評論0 收藏0
【劍指offer】6.用兩個棧實現隊列

摘要：題目用兩個棧來實現一個隊列，完成隊列的和操作。隊列中的元素為類型。基本思路棧用于入隊列存儲棧出隊列時將棧的數據依次出棧，并入棧到棧中棧出棧即棧的底部數據即隊列要出的數據。注意棧為空才能補充棧的數據，否則會打亂當前的順序。題目用兩個棧來實現一個隊列，完成隊列的Push和Pop操作。隊列中的元素為int類型。基本思路棧1: 用于入隊列存儲棧2: 出隊列時將棧1的數據依次出棧，并...

fredshare 2019-08-23 14:44 評論0 收藏0