<source id="wwucw"><optgroup id="wwucw"></optgroup></source>
  • <option id="wwucw"><optgroup id="wwucw"></optgroup></option>
  • 首頁 > 試題廣場 > 用兩個棧實現隊列
    [編程題]用兩個棧實現隊列
    用兩個棧來實現一個隊列,完成隊列的Push和Pop操作。 隊列中的元素為int類型。
    推薦
    class Solution 
       查看全部
    編輯于 2015-08-18 23:15:03 回復(62)
    這是左程云的《程序員代碼面試指南》的答案:
    import java.util.Stack;
    
    public class Solution {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        
        public void push(int node) {
            stack1.push(node);
        }
        
        public int pop() {
        	if(stack1.empty()&&stack2.empty()){
                throw new RuntimeException("Queue is empty!");
            }
            if(stack2.empty()){
                while(!stack1.empty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }

    發表于 2016-06-04 16:11:14 回復(53)
    //每次psuh是時先將stack2清空放入stck1(保證選入的一定在棧底),stack2始終是用來刪除的
    //在pop前,先將stack1中中的數據清空放入stack2(保存后入的在棧底),stack1始終用于push
    import java.util.Stack;
    
    public class Solution {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        
        public void push(int node) {
    	    	while(!stack2.isEmpty()){
    	    		stack1.push(stack2.pop());
    	    	}
    	       stack1.push(node);
    	    }
    	    
    	    public int pop() {
    	    	while (!stack1.isEmpty()){
    	    		stack2.push(stack1.pop());
    	    	}
    	    	return stack2.pop();
    	    }
    }
    發表于 2016-09-30 11:38:09 回復(12)
    思路:
    • 棧A用來作入隊列
    • 棧B用來出隊列,當棧B為空時,棧A全部出棧到棧B,棧B再出棧(即出隊列)
    # -*- coding:utf-8 -*-
    class Solution:
        def __init__(self):
            self.stackA = []
            self.stackB = []
            
        def push(self, node):
            # write code here
            self.stackA.append(node)
            
        def pop(self):
            # return xx
            if self.stackB:
                return self.stackB.pop()
            elif not self.stackA:
                return None
            else:
                while self.stackA:
                    self.stackB.append(self.stackA.pop())
                return self.stackB.pop()

    編輯于 2016-07-24 09:39:31 回復(20)
    Javascript 用來展示思路尤其方便。

    但是要考慮?pop() 時兩個棧為空的處理呀。。 js 是默認返回 undefined ,其他靜態語言比如 C++ 我記得會運行時異常吧,沒見到有幾個處理的。
    var inStack = [],
    ? ? outStack = [];
    function push(node) {
    ? ? // write code here
    ? ? inStack.push(node);
    }
    function pop() {
    ? ? // write code here
    ? ? if (!outStack.length) {
    ? ? ? ? while (inStack.length) {
    ? ? ? ? ? ? outStack.push(inStack.pop());
    ? ? ? ? }
    ? ? }
    ? ? return outStack.pop();
    }
    

    編輯于 2017-09-21 14:37:40 回復(4)
    class Solution
    {
    public:
        void push(int node) {
            stack1.push(node);
        }
    
        int pop() {
            //等待棧2出完后才能繼續入棧不然,不然就會占據棧頂
            if(stack2.empty()){
                while(!stack1.empty()){
                    stack2.push(stack1.top());
                    stack1.pop();
                }
            }
            int t=stack2.top();
            stack2.pop();
            return t;
        }
    
    private:
        stack<int> stack1;
        stack<int> stack2;
    };

    編輯于 2016-07-05 16:51:46 回復(0)
    import java.util.Stack;
    
    public class Solution {
    ??? Stack<Integer> stack1 = new Stack<Integer>();
    ??? Stack<Integer> stack2 = new Stack<Integer>();
    ?? ?
    ?? public void push(int node) {
    ?? ??? ?stack1.push(node);
    ??? }
    ?? ?
    ?? ?
    ?? public int pop() {
    ????? ?
    ?????? while(!stack2.isEmpty())
    ?? ??? ?{
    ?? ??? ??? ?return stack2.pop();
    ?? ??? ?}
    ?? ??? ?
    ?? ??? ?while(!stack1.isEmpty())
    ?? ??? ?{
    ?? ??? ??? ?stack2.push(stack1.pop());
    ?? ??? ?}
    ????? ?
    ?? ??? ?return stack2.pop();
    ??? }
    }

    發表于 2015-04-13 08:21:53 回復(7)
    import java.util.Stack;
    
    public class Solution {
    ? ? Stack<Integer> stack1 = new Stack<Integer>();
    ? ? Stack<Integer> stack2 = new Stack<Integer>();
    ? ??
    ? ? public void push(int node) {
     stack1.push(new Integer(node));
     }
    
     public int pop() {
     if(stack2.empty()){
     while(!stack1.empty()){
     stack2.push(stack1.pop());
     }
     }
     if(stack2.empty())
     System.out.println("stack1 is empty!");
     
     return stack2.pop().intValue();
    
     } 
    }
    

    發表于 2015-04-11 10:41:38 回復(4)
    C++:
    void push(int node)?
    {
    ? stack1.push(node);
    }
    int pop()
    {
    ? if(stack2.empty())
    {
    ? while(!stack1.empty())
    ? {
    ? ? ? stack2.push(stack1.top());
    ? ? ? stack1.pop();
    ? }
    }
    ?int result=stack2.top();
    ?stack2.pop();
    ?return result; ?
    }
    編輯于 2015-07-29 09:42:31 回復(3)
    最佳答案:通過所有測試用例的代碼:思路:有兩個棧,棧1和棧2.當入棧的時候,我們將它全放進棧1中,當需要出棧的時候,我們將棧1出棧到棧2中,然后再將棧2依次出棧。所以入棧的時候,思路很簡單,注意到要將int類型轉為Integer類型,我們使用了new Integer(int);當需要出棧的時候,我們用API提供的方法while(stack1.isEmpty())來將所有棧1的元素壓入棧2中,然后將棧2彈出就可以。這里又涉及到將Integer的類型轉為int類型的方法Integer.intValue();實現代碼如下:

    import java.util.Stack;
    public class Solution {
    ? ? Stack<Integer> stack1 = new Stack<Integer>();
    ? ? Stack<Integer> stack2 = new Stack<Integer>();
    ? ??
    ? ? public void push(int node) {
    ? ? ? ? stack1.push(new Integer(node));
    ? ? }
    ? ??
    ? ? public int pop() {
    ? ? if(stack2.isEmpty()){
    ? ? ? ? ? ? while(!stack1.isEmpty()){
    ? ? ? ? ? ? ? ? stack2.push(stack1.pop());
    ? ? ? ? ? ? }
    ? ? ? ? }
    ? ? ? ? return stack2.pop().intValue();
    ? ? }
    }
    編輯于 2015-08-24 21:26:48 回復(12)
    class Solution
    {
    public:
        void push(int node) {
            stack1.push(node);
        }
    
        int pop() {
            if(stack2.empty()){
                while(!stack1.empty()){
                    int tmp = stack1.top();
                    stack1.pop();
                    stack2.push(tmp);
                }
                int a = stack2.top(); stack2.pop();
                return a;
            }else{
                int a = stack2.top(); stack2.pop();
                return a;
            }
        }
    
    private:
        stack<int> stack1;
        stack<int> stack2;
    };
    
    發表于 2018-11-24 20:46:37 回復(0)
    # -*- coding:utf-8 -*-
    class Solution:
        def __init__(self):
            self.stack1 = []
            self.stack2 = []
            
        def push(self, node):
            # write code here
            if len(self.stack1) == 0:
                while len(self.stack2):
                    self.stack1.append(self.stack2.pop())
            self.stack1.append(node)
            
        def pop(self):
            # return xx
            if not len(self.stack2) == 0:
                return self.stack2.pop()
            else:
                while len(self.stack1) > 1:
                    self.stack2.append(self.stack1.pop())
                return self.stack1.pop()

    入隊時,判斷stack1是否為空,如不為空,將元素壓入stack1;如為空,先將stack2元素倒回stack1,再將新元素壓入stack1

    出隊時,判斷stack2是否為空,如不為空,則直接彈出頂元素;如為空,則將stack1的元素逐個“倒入”stack2,把stack1最后一個元素彈出并出隊。

    發表于 2017-08-31 15:53:01 回復(2)
    class Solution:
    ? ? def __init__(self):
    ? ? ? ? self.stack1 = []
    ? ? ? ? self.stack2 = []
    ? ? def push(self, node):
    ? ? ? ? # write code here
    ? ? ? ? self.stack1.append(node)
    ? ? def pop(self):
    ? ? ? ? # return xx
    ? ? ? ? if len(self.stack2) > 0:
    ? ? ? ? ? ? return self.stack2.pop()
    ? ? ? ? while self.stack1:
    ? ? ? ? ? ? self.stack2.append(self.stack1.pop())
    ? ? ? ? if len(self.stack2) > 0:
    ? ? ? ? ? ? return self.stack2.pop()
    

    發表于 2018-02-27 22:05:52 回復(2)
    //棧的特點:后進先出。隊列的特點:先進先出。所以在push方面是一樣的,在pop方面需要一個stac//k來做輔助,可以想象成從一杯中把水倒到另一杯中。 import java.util.Stack;
    
    public class Solution {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
    
        public void push(int node) {
            stack1.add(node);
        }
    
        public int pop() {
            if(stack2.size()==0){
                while (stack1.size()!=0){
                    stack2.push(stack1.pop());//stack1的第一個元素在stack2的末尾
                }
                return stack2.pop();
            }else {//因為stack1的size是在改變的所以當stack2中有元素時需要放到stack1的末尾先輸出
                stack1.push(stack2.pop());
                return stack1.pop();
            }
    
        }
    } 


    發表于 2017-02-10 14:39:37 回復(0)

    python solution:

    # -*- coding:utf-8 -*-
    class Solution:
        def __init__(self):
            self.arr=[]
        def push(self, node):
      
            self.arr.append(node)
        def pop(self):
        
            return self.arr.pop(0)
    編輯于 2017-10-01 20:27:22 回復(5)

    題目描述

    用兩個棧來實現一個隊列,完成隊列的PushPop操作。 隊列中的元素為int類型。

    解題思路

    隊列是先進先出,棧是先進后出,如何用兩個棧來實現這種先進先出呢?

    其實很簡單,我們假設用stack1專門來裝元素,那么直接stack1.pop肯定是不行的,這個時候stack2就要發揮作用了。

    我們的規則是:只要stack2中有元素就pop,如果stack2為空,則將stack1中所有元素倒進satck2中,就是說,新元素只進stack1,元素出來只從stack2出來。

    這樣子,就能保證每次從stack2pop出來的元素就是最老的元素了。

    我的答案

    import java.util.Stack;
    
    public class Solution{
        //負責裝元素
        Stack<Integer> stack1 = new Stack<Integer>();
        //負責出元素
        Stack<Integer> stack2 = new Stack<Integer>();
    
        public void push(int node) {
            stack1.push(node);
        }
    
        //主要思想是:stack2有元素就pop,沒有元素就將stack1中所有元素倒進來再pop
        public int pop() throws Exception{
            if(!stack2.isEmpty()){
                int node = stack2.pop();
                return node;
            }else{
                if(stack1.isEmpty()){
                    throw new Exception("no valid element");
                }
                while(!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
                return stack2.pop();
            }
        }
    }
    編輯于 2019-03-06 09:52:16 回復(0)
    #Python   感覺討論組里都是java啊
    #無力吐槽了,感覺后臺好傻逼,剛開始用隨便取了兩個變量名,說是越界啥子的,
    #后來改成stack1,stack2就過了
    
    class Solution:
        def __init__(self):
            self.stack1 = []
            self.stack2 = []
        def push(self, node):
            self.stack1.append(node)
        def pop(self):
            if len(self.stack2) != 0:
                return self.stack2.pop()
            while len(self.stack1) !=0:
                self.stack2.append(self.stack1.pop())
    
            return self.stack2.pop()

    編輯于 2016-11-01 19:44:55 回復(1)
    public class Solution {
    ? ? Stack<Integer> stack1 = new Stack<Integer>();
    ? ? Stack<Integer> stack2 = new Stack<Integer>();
    ? ??
    ? ? public void push(int node) {
    ? ? ? ? stack1.push(node);
    ? ? }
    ? ??
    ? ? public int pop() {
    ? ? ? ? int len = stack1.size();
    ? ? ? ? for(int i = 0;i < len - 1;i++) ?//有一種錯誤寫法,for(int i = 0;i < stack1.size();i++)
    ? ? ? ? {
    ? ? ? ? ? ? stack2.push(stack1.pop());
    ? ? ? ? }
    ? ? ? ? int result = stack1.pop();
    ? ? ? ? while(!stack2.isEmpty())
    ? ? ? ? {
    ? ? ? ? ? ? stack1.push(stack2.pop());
    ? ? ? ? }
    ? ? ? ? return result;
    ? ? }
    }
    棧是只能進出棧都在棧頂,而隊列是隊尾進隊,隊頭出隊。所以很明顯,直接用棧是不行的。
    然后進隊列是在隊尾,而棧進棧也可以看做是棧尾。所以很明顯,進隊列操作和進棧操作是一樣的,所以只需要使用一個棧就行了,這里我們假設使用stack1。
    所以接下來我們只要考慮如何使用兩個棧使得出隊操作是輸出棧頭部元素。輸出頭部元素,我們必須將除了第一個進棧的元素外的其他元素全部出棧,比如進棧操作12345,必須將2345出棧。我們很容易想到將2345存在另一個棧中( stack2.push(stack1.pop()) ),此時stack2順序是5432。然后將1出棧賦值給一個變量(result = stack1.pop()),這個變量就是return的值。然后再講stack2全部出棧賦值給stack1,此時stack1中元素就為2345( stack1.push(stack2.pop()) )。

    但是這里最容易出錯的地方:其實是循環,一開始我使用的是for(int i = 0;i < stack1.size();i++),發現答案是錯誤的。因為stack1.pop()之后,satck1.size()也發生了變化。導致執行了2次循環后就滿足條件了。因此,在stack1出棧操作之前,使用一個變量存儲stack1的初始長度。
    發表于 2016-08-19 11:32:08 回復(1)
    ? ? public void push(int node) {
    ? ? ? ? stack1.push(node);
    ? ? }
    ? ??
    ? ? public int pop() {
    ? ? ? ? if(stack2.empty()){
    ? ? ? ? ? ? while(!stack1.empty()){
    ? ? ? ? ? ? ? ? stack2.push(stack1.pop());
    ? ? ? ? ? ? }
    ? ? ? ? }
    ? ? ? ? return stack2.pop();
    ? ? }
    

    發表于 2018-08-23 11:26:57 回復(1)
    1、如果s2不為空,則返回頂部數據,
    2、如果s2為空,s1不為空,則將s1的數據復制到s2后,返回s2頂部數據
    3、如果s1也為空,則拋出異常
    老鐵們,看看我的答案吧
    import java.util.Stack;

    public class Solution {
    ? ? Stack<Integer> stack1 = new Stack<Integer>();
    ? ? Stack<Integer> stack2 = new Stack<Integer>();

    ? ? public void push(int node) {
    ? ? ? ? stack1.push(node);
    ? ? }

    ? ? public int pop() throws Exception {
    ? ? ? ? if (!stack2.isEmpty()){
    ? ? ? ? ? ? return stack2.pop();
    ? ? ? ? }else if (!stack1.isEmpty()){
    ? ? ? ? ? ? while (!stack1.isEmpty()){
    ? ? ? ? ? ? ? ? stack2.push(stack1.pop());
    ? ? ? ? ? ? }
    ? ? ? ? ? ? return stack2.pop();
    ? ? ? ? }else{
    ? ? ? ? ? ? throw new Exception("the queue is empty");
    ? ? ? ? }
    ? ? }
    }

    編輯于 2018-03-25 00:00:16 回復(0)
    //補一個js版本
    
    var stack1 = [], stack2 = [];
    function push(node)
    {
        // write code here
        stack1.push(node);
    }
    function pop()
    {
        // write code here
        if(stack2.length === 0){
            while(stack1.length !== 0){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    module.exports = {
        push : push,
        pop : pop
    };

    發表于 2017-03-24 14:50:13 回復(0)
    狠狠的撸2019手机看片电影最新版