デイリーアルゴリズム: 2 つのスタックを持つキューの実装

[[422522]]

この記事はWeChatの公開アカウント「3分でフロントエンドを学ぶ」から転載したもので、著者はsisterAnです。この記事を転載する場合は、「3分で学ぶフロントエンド」公式アカウントまでご連絡ください。

2 つのスタックを使用してキューを実装します。キューは次のように宣言されています。キューの末尾に整数を挿入し、キューの先頭から整数を削除するには、それぞれ appendTail と deleteHead という 2 つの関数を実装してください。 (キューに要素がない場合、deleteHead 操作は -1 を返します)

例1:

入力：
 [ "CQueue" 、 "appendTail" 、 "deleteHead" 、 "deleteHead" ]
 [[],[3],[],[]]
出力: [ null , null ,3,-1]

例2:

入力：
 [ "CQueue" 、 "deleteHead" 、 "appendTail" 、 "appendTail" 、 "deleteHead" 、 "deleteHead" ]
 [[],[],[5],[2],[],[]]
出力: [ null ,-1, null , null ,5,2]

ヒント：

• 1 <= 値 <= 10000
• 最大で、appendTail と deleteHead は 10,000 回呼び出されます。

解決：

• スタックはLIFO、キューはFIFO
• ダブルスタックはシーケンスの反転を実現できます。stack1=[1, 2, 3]、stack2=[] があるとします。ループがスタック1をポップし、ポップされた要素をスタック2にプッシュすると、ループの終了後、stack1=[]、stack2=[3, 2, 1] になります。つまり、stack1 の要素の反転は、stack2 を通じて実現されます。
• キューの最初の要素を削除する必要がある場合は、stack2 をポップするだけで済みます。stack2 が空の場合は、stack1 の要素を stack2 に反転してから、stack2 をポップする必要があります。stack1 も空の場合、つまりキューに要素がない場合は、-1 を返します。

コード実装:

定数CQueue =関数() {
    this.stack1 = []
    this.stack2 = []
 };
 CQueue.prototype.appendTail =関数(値) {
    this.stack1.push(値)
 };
 CQueue.prototype.deleteHead =関数() {
    if(this.stack2.length) {
 this.stack2.pop()を返す
    }
    if (!this.stack1.length) は-1を返します
    while(this.stack1.length) {
        this.stack2.push(this.stack1.pop())
    }
 this.stack2.pop()を返す
};

複雑性分析:

時間計算量: appendTailの時間計算量はO(1)、deleteHeadの時間計算量はO(n)です。

空間計算量: O(n)