キューを使用してスタックを実装する


難易度 簡単に
よく聞かれる PayPal
デザイン キュー スタック

次の機能を実装します スタック の標準操作を使用したデータ構造 キュー,

  1. push(x)–>要素xをスタックにプッシュします
  2. pop()–>スタックの一番上の要素を削除します
  3. top()–>スタックの一番上にある要素を返します
  4. empty()–>スタックが空かどうかを返します

入力:
stack.push(1);
stack.push(2);
stack.top(); // 2を返します
stack.pop(); // 2を返します
stack.empty(); // falseを返します
出力:
2
2
false

キューを使用してスタックを実装するためのアルゴリズム

スタックは、2つのキュー(たとえば、q1とq2)を使用して実装できます。

push(x)

q1の最後でxを押して、top変数のスタックの一番上として保持します。
擬似コード

void push(int x) {
    q1.add(x);
    top = x;
}

時間計算量= O(1)

上()

スタックの最上位は常にtop変数で維持されるため、単に最上位を返します。
擬似コード

int top() {
    return top;
}

時間計算量= O(1)

空の()

キューq1が空の場合、スタックは空です。
擬似コード

boolean empty() {
    return q1.isEmpty();
}

時間計算量= O(1)

ポップ()

キューq1の背面にはスタックの最上位が含まれ、q1のサイズをnとします。

  1. キューq1の(n – 1)要素をキューq2に移動します。
  2. また、転送される現在の変数としてスタックの最上位を維持します。
  3. 現在、q1にはスタックの最上位にある要素が1つだけ含まれています。
  4. この要素を削除して、いくつかの変数(たとえばele)に格納します。
  5. すべての要素をキューq2からキューq1に移動します。
  6. eleを返します。

時間計算量= O(N) 
ここで、nはキュー内の要素の数です。

例を考えてみましょう。
q1 = 3-> 5-> 7-> 1-> 2
q2 = ヌル

要素をポップアウトします。

  1. q1からq1に(n – 2)を転送します
    q1 = 2およびq2 = 3-> 5-> 7-> 1
  2. 要素を削除してq1に保存します。
    q1 = nullおよびq2 = 3-> 5-> 7-> 1およびele = 2
  3. すべての要素をq2からq1に移動します。
    q1 = 3-> 5-> 7-> 1およびq2 = null
  4. eleを返します。

明確にするために下の画像を参照してください。

キューを使用してスタックを実装する

擬似コード

int pop() {
    int n = q1.size();
    for (int i = 0; i < n - 1; i++) {
        int curr = q1.remove();
        q2.add(curr);
        top = curr;
    }
    int ele = q1.remove();
    n = q2.size();
    for (int i = 0; i < n; i++) {
        q1.add(q2.remove());
    }
    return ele;
}

時間計算量= O(N)

キューを使用してスタックを実装するためのJAVAコード

import java.util.Queue; 
import java.util.LinkedList;
public class StackUsingQueues {
    // Two queues to implement stack
    private static Queue<Integer> q1 = new LinkedList<>();
    private static Queue<Integer> q2 = new LinkedList<>();
    // Stores the top element of stack
    private static int top;

    private static void push(int x) {
        // Add element at rear of q1
        q1.add(x);
        // update top as current element
        top = x;
    }

    private static int top() {
        // Top stores the top of stack
        return top;
    }

    private static int pop() {
        int n = q1.size();
        // Shift (n - 1) elements from q1 to q2 and update top as curr
        // element transferred
        for (int i = 0; i < n - 1; i++) {
            int curr = q1.remove();
            q2.add(curr);
            top = curr;
        }
        // q1 contains only 1 element which is top of stack
        // store the element in ele and remove it from q1
        int ele = q1.remove();
        n = q2.size();
        // Again transfer back the elements from q2 to q1
        for (int i = 0; i < n; i++) {
            q1.add(q2.remove());
        }
        // return ele, this is the top of stack
        return ele;
    }
    
    private static boolean empty() {
        // If q1 is empty then stack is empty
        return q1.isEmpty();
    }
    
    public static void main(String[] args) {
        // Example
        push(1);
        push(2);
        System.out.println(top());
        System.out.println(pop());
        System.out.println(empty());
    }
}

キューを使用してスタックを実装するためのC ++コード

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

// Two queues to implement stack
queue<int> q1;
queue<int> q2;
// Stores the top element of stack
int Top;

void push(int x) {
    // Add element at rear of q1
    q1.push(x);
    // update top as current element
    Top = x;
}

int top() {
    // Top stores the top of stack
    return Top;
}

bool empty() {
    // If q1 is empty then stack is empty
    return q1.empty();
}

int pop() {
    int n = q1.size();
    // Shift (n - 1) elements from q1 to q2 and update top as curr
    // element transferred
    for (int i = 0; i < n - 1; i++) {
        int curr = q1.front();
        q1.pop();
        q2.push(curr);
        Top = curr;
    }
    // q1 contains only 1 element which is top of stack
    // store the element in ele and remove it from q1
    int ele = q1.front();
    q1.pop();
    n = q2.size();
    // Again transfer back the elements from q2 to q1
    for (int i = 0; i < n; i++) {
        q1.push(q2.front());
        q2.pop();
    }
    // return ele, this is the top of stack
    return ele;
}

int main() {
    // Example
    push(1);
    push(2);
    cout<<top()<<endl;
    cout<<pop()<<endl;
    if (empty()) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    return 0;
}
2
2
false

参照1    参照2