2つのスタックを使用してキューを実装するにはどうすればいいですか? 質問する

2 つのスタックを保持し、それらを およびinboxと呼びますoutbox。

エンキュー:

• 新しい要素をプッシュするinbox

デキュー:

• 空の場合はoutbox、各要素をポップしinboxて上に押し込むことで補充します。outbox

• 先頭の要素をポップして返すoutbox

この方法を使用すると、各要素は各スタックに正確に 1 回存在します。つまり、各要素は 2 回プッシュされ、2 回ポップされるため、償却定数時間の操作が行われます。

以下は Java での実装です。

public class Queue<E>
{

    private Stack<E> inbox = new Stack<E>();
    private Stack<E> outbox = new Stack<E>();

    public void queue(E item) {
        inbox.push(item);
    }

    public E dequeue() {
        if (outbox.isEmpty()) {
            while (!inbox.isEmpty()) {
               outbox.push(inbox.pop());
            }
        }
        return outbox.pop();
    }

}