使用堆棧排隊  


難度級別 容易獎學金
經常問 ol石 土磚 亞馬遜 Flipkart 高盛 信息邊緣 的InMobi 我的旅行 空氣質量 Microsoft微軟 摩根士丹利(Morgan Stanley) 神諭 沃爾瑪實驗室
隊列

在隊列中使用 問題,我們必須使用堆棧數據結構的標準功能來實現隊列的以下功能,

  1. 排隊:將元素添加到隊列的末尾
  2. 出隊:從隊列開始處刪除元素

例  

輸入:
入隊(5)
入隊(11)
入隊(39)
Dequeue()//返回5
入隊(12)
Dequeue()//返回11
Dequeue()//返回39
輸出:
5
11
39

算法  

可以使用兩個堆棧來實現隊列,有兩種方法可以使用堆棧來實現隊列,一種是通過增加入隊操作的成本,第二種是使用出隊操作的成本。

使用堆棧的隊列的方法1(成本大增入隊操作)  

創建兩個堆棧st1和st2。 可視化 隊列 在st1中,st1的頂部位於隊列的前面,而在st1中的向下移動類似於在隊列中的向前移動。

入隊(x)

將x推送到隊列的後面與將x推送到堆棧st1的底部相同。

  1. 從st1刪除所有元素,然後將它們推到st2。
  2. 按x到st2。
  3. 從st2刪除所有元素,然後將它們推回st1。

時間複雜度= 氧(n)A

使用堆棧排隊

出隊()

從隊列的最前面刪除元素類似於刪除堆棧st1的頂部。 因此,如果st1不為空,請彈出st1的頂部並返回。

也可以看看
反轉隊列的前K個元素

時間複雜度= O(1)

方法1的整體空間複雜度= O(N)

使用堆棧的JAVA代碼隊列

import java.util.Stack;

public class QueueUsingStacks {
    // Costly Enqueue Operation
    private static Stack<Integer> st1;
    private static Stack<Integer> st2;

    private static void enqueue(int x) {
        // remove all the elements from st1 and push them to st2
        while (!st1.isEmpty()) {
            st2.push(st1.pop());
        }

        // push x to st2
        st2.push(x);

        // remove all the elements from st2 and push them back to st1
        while (!st2.isEmpty()) {
            st1.push(st2.pop());
        }
    }

    private static int dequeue() {
        if (st1.isEmpty()) {
            return -1;
        }

        // if st1 is not empty return and remove the top of st1
        return st1.pop();
    }

    public static void main(String[] args) {
        st1 = new Stack<>();
        st2 = new Stack<>();
        
        // Example
        enqueue(5);
        enqueue(11);
        enqueue(39);
        System.out.println(dequeue());
        enqueue(12);
        System.out.println(dequeue());
        System.out.println(dequeue());
    }
}
5
11
39

C ++代碼

#include<bits/stdc++.h> 
using namespace std;

// Costly Enqueue Operation

stack<int> st1;
stack<int> st2;

void enqueue(int x) {
    // remove all the elements from st1 and push them to st2
    while (!st1.empty()) {
        int curr = st1.top();
        st1.pop();
        st2.push(curr);
    }
    
    // push x to st2
    st2.push(x);
    
    // remove all the elements from st2 and push them back to st1
    while (!st2.empty()) {
        int curr = st2.top();
        st2.pop();
        st1.push(curr);
    }
}

int dequeue() {
    if (st1.empty()) {
        return -1;
    }
    
    // if st1 is not empty return and remove the top of st1
    int top = st1.top();
    st1.pop();
    return top;
}

int main() {
    // Example
    enqueue(5);
    enqueue(11);
    enqueue(39);
    cout<<dequeue()<<endl;
    enqueue(12);
    cout<<dequeue()<<endl;
    cout<<dequeue()<<endl;
    
    return 0;
}
5
11
39

使用堆棧的隊列的方法2(成本出隊操作)  

創建兩個堆棧st1和st2。 可視化st1中的隊列,st1的頂部表示隊列的後部,在st1中向上移動類似於在隊列中向前移動。

也可以看看
合併重疊間隔

入隊(x)

將x推送到隊列的後麵類似於將x推送到stack_st1的頂部。 因此,將x推到st1的頂部。

時間複雜度= O(1)

出隊()

從隊列的最前面刪除一個元素類似於從stack_st1的最下面刪除一個元素。 因此,如果st1不為空,

  1. 從st1刪除所有元素,然後將它們推到st2。
  2. 彈出st2的頂部並將其存儲在可變頂部。
  3. 從st2刪除所有元素,然後將它們推回st1。
  4. 返回頂部

時間複雜度= O(N)

使用堆棧排隊

方法2的整體空間複雜度= O(N)

JAVA代碼

import java.util.Stack;

public class QueueUsingStacks {
    // Costly Dequeue Operation
    private static Stack<Integer> st1;
    private static Stack<Integer> st2;

    private static void enqueue(int x) {
        // push x to top of st1
        st1.push(x);
    }

    private static int dequeue() {
        if (st1.isEmpty()) {
            return -1;
        }

        // if st1 is not empty
        // remove all the elements from st1 and push them to st2
        while (!st1.isEmpty()) {
            st2.push(st1.pop());
        }

        // pop the top of st2 and store it in a variable top
        int top = st2.pop();

        // remove all the elements from st2 and push them back to st1
        while (!st2.isEmpty()) {
            st1.push(st2.pop());
        }
        
        // return top
        return top;
    }

    public static void main(String[] args) {
        st1 = new Stack<>();
        st2 = new Stack<>();

        // Example
        enqueue(5);
        enqueue(11);
        enqueue(39);
        System.out.println(dequeue());
        enqueue(12);
        System.out.println(dequeue());
        System.out.println(dequeue());
    }
}
5
11
39

C ++代碼

#include<bits/stdc++.h> 
using namespace std;

// Costly Dequeue Operation

stack<int> st1;
stack<int> st2;

void enqueue(int x) {
    // push x to top of st1
    st1.push(x);
}

int dequeue() {
    if (st1.empty()) {
        return -1;
    }
    
    // if st1 is not empty
    // remove all the elements from st1 and push them to st2
    while (!st1.empty()) {
        int curr = st1.top();
        st1.pop();
        st2.push(curr);
    }
    
    // pop the top of st2 and store it in a variable top
    int top = st2.top();
    st2.pop();
    
    // remove all the elements from st2 and push them back to st1
    while (!st2.empty()) {
        int curr = st2.top();
        st2.pop();
        st1.push(curr);
    }
    
    // return top
    return top;
}

int main() {
    // Example
    enqueue(5);
    enqueue(11);
    enqueue(39);
    cout<<dequeue()<<endl;
    enqueue(12);
    cout<<dequeue()<<endl;
    cout<<dequeue()<<endl;
    
    return 0;
}
5
11
39

參考1     參考2