2スタックを持つキューの実装

始まり
私はあなたの語彙に精通していると仮定している

スタック

PUSH = Add to end
POP = Get from end

キュー

ENQUEUE = Add to end
DEQUEUE = Return from beginning

前提条件:あなたはこれを知っている必要があります
Javaの

ArrayListに「追加」すると、最後に追加されます.

同様に、JavaScriptを使用する場合、配列に“push”すると、配列の最後に値が追加されます.

それで、私は2つのスタック(LIFO)で単純な待ち行列(FIFO)を実装することのこの単純で興味深い話題に遭遇しました
大学でこのプログラムを行ったこと(私はC +でのスクラッチの実装を使用しています)、私は今、より多くの簡潔さがインタビュー準備のために必要であると信じています.

import java.util.ArrayList;
import java.util.List;

public class MyStack {

    private final List<Integer> stack = new ArrayList<>();

    void push(int item) {
        stack.add(item);
    }

    int pop() {
        if (!stack.isEmpty()) {
            return stack.remove(stack.size() - 1);
        }
        return -1;  // if nothing found
    }

    int size() {
        return stack.size();
    }

    boolean isEmpty() {
        return stack.isEmpty();
    }
}

だから、今私たちのスタックを持って-それは簡単です
そして、我々の待ち行列は、ここにあります

public class MyQueueWithTwoStacks {

    private final MyStack firstStack;
    private final MyStack secondStack;

    public MyQueueWithTwoStacks() {
        this.firstStack = new MyStack();
        this.secondStack = new MyStack();
    }

    boolean isEmpty() {
        return firstStack.isEmpty() && secondStack.isEmpty();
    }

    int size() {
        return firstStack.size() + secondStack.size();
    }

    void enqueue(int item) {
        firstStack.push(item);
    }

    /**
     * We will use the second stack to out the values, if the second bucket is
     * empty that means we need to copy over all stack1 entries to it
     *
     * @return returns the value
     */
    int dequeue() {
        if (secondStack.isEmpty()) {
            while (!firstStack.isEmpty()) {
                secondStack.push(firstStack.pop());
            }
        }

        return secondStack.pop();
    }
}

参照:

あなたが理論的な概観が好きであるならば、ここではスーパーニースです

エンド.