LeetCodeの問題:232.スタックを使って列を実現し、二つのスタックを使って入隊します.O(1)、出隊-O(n)、JavaScript、詳細な注釈

8516 ワード

ソースリンク:https://leetcode-cn.com/problems/implement-queue-using-stacks/
問題解決の考え方:
  • すべての要素はs 1が存在します.同時に最初の入隊要素をキャッシュします.
  • 隊を出る時、まずチームの先頭以外の要素をs 2にキャッシュして、s 1の残りの要素をpopします.
  • popが完了したら、s 2キャッシュの要素を順次s 1に戻す.
  • /**
     * Initialize your data structure here.
     */
    var MyQueue = function () {
         
      this.s1 = []; //     
      this.s2 = []; // pop       
      this.top = null; //     
    };
    
    /**
     * Push element x to the back of queue.
     * @param {number} x
     * @return {void}
     */
    MyQueue.prototype.push = function (x) {
         
      //              
      if (!this.s1.length) {
         
        this.top = x;
      }
      //         
      this.s1.push(x);
    };
    
    /**
     * Removes the element from in front of queue and returns that element.
     * @return {number}
     */
    MyQueue.prototype.pop = function () {
         
      // s1   1 ,     ,        ,         
      if (this.s1.length <= 1) {
         
        this.top = null;
      }
    
      //  s1           s2
      while (this.s1.length > 1) {
         
        this.top = this.s1.pop();
        this.s2.push(this.top);
      }
    
      //           
      const pop = this.s1.pop();
    
      //  s2      s1,         
      while (this.s2.length) {
         
        this.s1.push(this.s2.pop());
      }
    
      return pop;
    };
    
    /**
     * Get the front element.
     * @return {number}
     */
    MyQueue.prototype.peek = function () {
         
      return this.top;
    };
    
    /**
     * Returns whether the queue is empty.
     * @return {boolean}
     */
    MyQueue.prototype.empty = function () {
         
      return !this.s1.length;
    };