スタックを使用してキューに入れる


難易度 簡単に
よく聞かれる アコライト Adobe Amazon (アマゾン) DEショウ フリップカート ゴールドマン·サックス インフォエッジ インモビ MakeMyTrip MAQ マイクロソフト モルガン·スタンレー オラクル ウォルマート・ラボ
キュー スタック

を使用してキューに入れます スタック 問題は、スタックデータ構造の標準関数を使用して、キューの次の関数を実装する必要があることです。

  1. エンキュー:キューの最後に要素を追加します
  2. デキュー:キューの先頭から要素を削除します

入力:
エンキュー(5)
エンキュー(11)
エンキュー(39)
Dequeue()// 5を返します
エンキュー(12)
Dequeue()// 11を返します
Dequeue()// 39を返します
出力:
5
11
39

アルゴリズム

キューはXNUMXつのスタックを使用して実装できます。スタックを使用してキューを実装するには、XNUMXつはエンキュー操作のコストを高くする方法、もうXNUMXつはデキュー操作のコストを高くする方法です。

スタックを使用したキューの方法1(コストのかかるエンキュー操作)

1つのスタックst2とstXNUMXを作成します。 視覚化する キュー st1では、st1の先頭がキューの先頭にあり、st1で下に移動することは、キューで前に移動することと似ています。

エンキュー(x)

xをキューの後ろにプッシュすることは、xをスタックst1の一番下にプッシュすることと同じです。

  1. st1からすべての要素を削除し、それらをst2にプッシュします。
  2. xをst2にプッシュします。
  3. st2からすべての要素を削除し、それらをst1に押し戻します。

時間計算量= O(n)A

スタックを使用してキューに入れる

Dequeue()

キューの先頭から要素を削除することは、スタックst1の最上位を削除することに似ています。 したがって、st1が空でない場合は、st1の上部をポップして戻ります。

時間計算量= 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(コストのかかるデキュー操作)

1つのスタックst2とst1を作成します。 st1でキューを視覚化します。st1の上部はキューの後方を表し、stXNUMXで上に移動することは、キューで前に移動することと似ています。

エンキュー(x)

xをキューの後ろにプッシュすることは、xをstack_st1の一番上にプッシュすることに似ています。 したがって、xをst1の先頭にプッシュします。

時間計算量= O(1)

Dequeue()

キューの先頭から要素を削除することは、stack_st1の一番下から要素を削除することに似ています。 したがって、st1が空でない場合、

  1. st1からすべての要素を削除し、それらをst2にプッシュします。
  2. st2の上部をポップし、変数topに格納します。
  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