你如何在JavaScript中實現堆棧和隊列?


Answers

Javascript具有push和pop方法,它們在普通的Javascript數組對像上運行。

對於隊列,請看這裡:

http://safalra.com/web-design/javascript/queues/

可以使用推送和移位方法或數組對象的非移位和彈出方法在JavaScript中實現隊列。 雖然這是實現隊列的一種簡單方法,但對於大型隊列來說效率非常低 - 因為這些方法在數組上運行,所以每次調用時,shift和unshift方法都會移動數組中的每個元素。

Queue.js是一個簡單且高效的JavaScript隊列實現,它的出列函數以分攤的恆定時間運行。 因此,對於更大的隊列,它可以比使用陣列快得多。

Question

在JavaScript中實現堆棧和隊列的最佳方式是什麼?

我正在尋找分流碼算法,我將需要這些數據結構。




/*------------------------------------------------------------------ 
 Defining Stack Operations using Closures in Javascript, privacy and
 state of stack operations are maintained

 @author:Arijt Basu
 Log: Sun Dec 27, 2015, 3:25PM
 ------------------------------------------------------------------- 
 */
var stackControl = true;
var stack = (function(array) {
        array = [];
        //--Define the max size of the stack
        var MAX_SIZE = 5;

        function isEmpty() {
            if (array.length < 1) console.log("Stack is empty");
        };
        isEmpty();

        return {

            push: function(ele) {
                if (array.length < MAX_SIZE) {
                    array.push(ele)
                    return array;
                } else {
                    console.log("")
                }
            },
            pop: function() {
                if (array.length > 1) {
                    array.pop();
                    return array;
                } else {
                    console.log("Stack Underflow");
                }
            }

        }
    })()
    // var list = 5;
    // console.log(stack(list))
if (stackControl) {
    console.log(stack.pop());
    console.log(stack.push(3));
    console.log(stack.push(2));
    console.log(stack.pop());
    console.log(stack.push(1));
    console.log(stack.pop());
    console.log(stack.push(38));
    console.log(stack.push(22));
    console.log(stack.pop());
    console.log(stack.pop());
    console.log(stack.push(6));
    console.log(stack.pop());
}
//End of STACK Logic

/* Defining Queue operations*/

var queue = (function(array) {
    array = [];
    var reversearray;
    //--Define the max size of the stack
    var MAX_SIZE = 5;

    function isEmpty() {
        if (array.length < 1) console.log("Queue is empty");
    };
    isEmpty();

    return {
        insert: function(ele) {
            if (array.length < MAX_SIZE) {
                array.push(ele)
                reversearray = array.reverse();
                return reversearray;
            } else {
                console.log("Queue Overflow")
            }
        },
        delete: function() {
            if (array.length > 1) {
                //reversearray = array.reverse();
                array.pop();
                return array;
            } else {
                console.log("Queue Underflow");
            }
        }
    }



})()

console.log(queue.insert(5))
console.log(queue.insert(3))
console.log(queue.delete(3))



這是鏈接列表版本的一個隊列,也包含最後一個節點,正如@perkins所建議的那樣,並且是最合適的。

// QUEUE Object Definition

var Queue = function() {
  this.first = null;
  this.last = null;
  this.size = 0;
};

var Node = function(data) {
  this.data = data;
  this.next = null;
};

Queue.prototype.enqueue = function(data) {
  var node = new Node(data);

  if (!this.first){ // for empty list first and last are the same
    this.first = node;
    this.last = node;
  } else { // otherwise we stick it on the end
    this.last.next=node;
    this.last=node;
  }

  this.size += 1;
  return node;
};

Queue.prototype.dequeue = function() {
  if (!this.first) //check for empty list
    return null;

  temp = this.first; // grab top of list
  if (this.first==this.last) {
    this.last=null;  // when we need to pop the last one
  }
  this.first = this.first.next; // move top of list down
  this.size -= 1;
  return temp;
};



創建一對提供各種數據結構所具有的各種方法的類(push,pop,peek等)。 現在執行這些方法。 如果你熟悉棧/隊列背後的概念,這應該是非常簡單的。 你可以用一個數組和一個帶有鍊錶的隊列來實現堆棧,儘管肯定還有其他方法可以解決它。 Javascript會讓這一切變得簡單,因為它是弱類型的,所以你甚至不必擔心泛型類型,如果你用Java或C#實現它,你就不得不這樣做。




這是一個相當簡單的隊列實現,有兩個目的:

  • 與array.shift()不同,你知道這個出隊方法需要一定的時間(O(1))。
  • 為了提高速度,這種方法比鏈接表方法使用的分配少得多。

堆棧實現僅與第二個目標共享。

// Queue
function Queue() {
        this.q = new Array(5);
        this.first = 0;
        this.size = 0;
}
Queue.prototype.enqueue = function(a) {
        var other;
        if (this.size == this.q.length) {
                other = new Array(this.size*2);
                for (var i = 0; i < this.size; i++) {
                        other[i] = this.q[(this.first+i)%this.size];
                }
                this.first = 0;
                this.q = other;
        }
        this.q[(this.first+this.size)%this.q.length] = a;
        this.size++;
};
Queue.prototype.dequeue = function() {
        if (this.size == 0) return undefined;
        this.size--;
        var ret = this.q[this.first];
        this.first = (this.first+1)%this.q.length;
        return ret;
};
Queue.prototype.peek = function() { return this.size > 0 ? this.q[this.first] : undefined; };
Queue.prototype.isEmpty = function() { return this.size == 0; };

// Stack
function Stack() {
        this.s = new Array(5);
        this.size = 0;
}
Stack.prototype.push = function(a) {
        var other;
    if (this.size == this.s.length) {
            other = new Array(this.s.length*2);
            for (var i = 0; i < this.s.length; i++) other[i] = this.s[i];
            this.s = other;
    }
    this.s[this.size++] = a;
};
Stack.prototype.pop = function() {
        if (this.size == 0) return undefined;
        return this.s[--this.size];
};
Stack.prototype.peek = function() { return this.size > 0 ? this.s[this.size-1] : undefined; };



如果您通過push()和pop()函數了解堆棧,則隊列就是使其中一個操作具有反義意義。 push()的對像是unshift(),pop()是es(shift)()。 然後:

//classic stack
var stack = [];
stack.push("first"); // push inserts at the end
stack.push("second");
stack.push("last");
stack.pop(); //pop takes the "last" element

//One way to implement queue is to insert elements in the oposite sense than a stack
var queue = [];
queue.unshift("first"); //unshift inserts at the beginning
queue.unshift("second");
queue.unshift("last");
queue.pop(); //"first"

//other way to do queues is to take the elements in the oposite sense than stack
var queue = [];
queue.push("first"); //push, as in the stack inserts at the end
queue.push("second");
queue.push("last");
queue.shift(); //but shift takes the "first" element



如果你想製作自己的數據結構,你可以建立自己的數據結構:

var Stack = function(){
  this.top = null;
  this.size = 0;
};

var Node = function(data){
  this.data = data;
  this.previous = null;
};

Stack.prototype.push = function(data) {
  var node = new Node(data);

  node.previous = this.top;
  this.top = node;
  this.size += 1;
  return this.top;
};

Stack.prototype.pop = function() {
  temp = this.top;
  this.top = this.top.previous;
  this.size -= 1;
  return temp;
};

對於隊列:

var Queue = function() {
  this.first = null;
  this.size = 0;
};

var Node = function(data) {
  this.data = data;
  this.next = null;
};

Queue.prototype.enqueue = function(data) {
  var node = new Node(data);

  if (!this.first){
    this.first = node;
  } else {
    n = this.first;
    while (n.next) {
      n = n.next;
    }
    n.next = node;
  }

  this.size += 1;
  return node;
};

Queue.prototype.dequeue = function() {
  temp = this.first;
  this.first = this.first.next;
  this.size -= 1;
  return temp;
};



Javascript中的常規Array結構是Stack(先入先出),也可以用作Queue(先入先出),具體取決於您所做的調用。

查看此鏈接以了解如何使Array像Queue一樣工作:

Queues




這是我的堆棧實現。

function Stack() {
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.clear = clear;
this.length = length;
}
function push(element) {
this.dataStore[this.top++] = element;
}
function peek() {
return this.dataStore[this.top-1];
}
function pop() {
return this.dataStore[--this.top];
}
function clear() {
this.top = 0;
}
function length() {
return this.top;
}

var s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
console.log("length: " + s.length());
console.log(s.peek());



正如其他答案中所解釋的那樣,堆棧實現是微不足道的。

然而,在這個線程中,我沒有找到任何令人滿意的答案來實現JavaScript中的隊列,所以我創建了自己的。

這個線程有三種類型的解決方案:

  • 數組 - 最糟糕的解決方案是在大數組上使用array.shift()效率非常低
  • 鏈接列表 - 它是O(1),但是為每個元素使用一個對像有點過分,特別是如果它們中有很多它們很小,比如存儲數字
  • 延遲移位數組 - 它由索引與數組關聯組成。 當一個元素出隊時,索引向前移動。 當索引到達數組的中間位置時,數組將被分成兩部分以刪除前半部分。

延遲移位數組是我心目中最令人滿意的解決方案,但它們仍將所有內容都存儲在一個大型連續數組中,這可能會造成問題,並且在數組切片時應用程序會錯開。

我使用小數組鍊錶(每個最多1000個元素)進行實現。 這些數組的行為類似於延遲移位數組,除非它們從不切片:當數組中的每個元素都被移除時,數組將被簡單地丟棄。

該軟件包在npm上具有基本的FIFO功能,我剛推出它。 代碼分為兩部分。

這是第一部分

/** Queue contains a linked list of Subqueue */
class Subqueue <T> {
  public full() {
    return this.array.length >= 1000;
  }

  public get size() {
    return this.array.length - this.index;
  }

  public peek(): T {
    return this.array[this.index];
  }

  public last(): T {
    return this.array[this.array.length-1];
  }

  public dequeue(): T {
    return this.array[this.index++];
  }

  public enqueue(elem: T) {
    this.array.push(elem);
  }

  private index: number = 0;
  private array: T [] = [];

  public next: Subqueue<T> = null;
}

這裡是主要的Queue類:

class Queue<T> {
  get length() {
    return this._size;
  }

  public push(...elems: T[]) {
    for (let elem of elems) {
      if (this.bottom.full()) {
        this.bottom = this.bottom.next = new Subqueue<T>();
      }
      this.bottom.enqueue(elem);
    }

    this._size += elems.length;
  }

  public shift(): T {
    if (this._size === 0) {
      return undefined;
    }

    const val = this.top.dequeue();
    this._size--;
    if (this._size > 0 && this.top.size === 0 && this.top.full()) {
      // Discard current subqueue and point top to the one after
      this.top = this.top.next;
    }
    return val;
  }

  public peek(): T {
    return this.top.peek();
  }

  public last(): T {
    return this.bottom.last();
  }

  public clear() {
    this.bottom = this.top = new Subqueue();
    this._size = 0;
  }

  private top: Subqueue<T> = new Subqueue();
  private bottom: Subqueue<T> = this.top;
  private _size: number = 0;
}

類型註釋( : X )可以輕鬆刪除以獲取ES6 JavaScript代碼。




Related