data-structures shift - 你如何在JavaScript中實現堆棧和隊列?




first element (17)

我使用鏈接列表實現堆棧隊列

// Linked List
function Node(data) {
  this.data = data;
  this.next = null;
}

// Stack implemented using LinkedList
function Stack() {
  this.top = null;
}

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

  newNode.next = this.top; //Special attention
  this.top = newNode;
}

Stack.prototype.pop = function() {
  if (this.top !== null) {
    var topItem = this.top.data;
    this.top = this.top.next;
    return topItem;
  }
  return null;
}

Stack.prototype.print = function() {
  var curr = this.top;
  while (curr) {
    console.log(curr.data);
    curr = curr.next;
  }
}

// var stack = new Stack();
// stack.push(3);
// stack.push(5);
// stack.push(7);
// stack.print();

// Queue implemented using LinkedList
function Queue() {
  this.head = null;
  this.tail = null;
}

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

  if (this.head === null) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    this.tail.next = newNode;
    this.tail = newNode;
  }
}

Queue.prototype.dequeue = function() {
  var newNode;
  if (this.head !== null) {
    newNode = this.head.data;
    this.head = this.head.next;
  }
  return newNode;
}

Queue.prototype.print = function() {
  var curr = this.head;
  while (curr) {
    console.log(curr.data);
    curr = curr.next;
  }
}

var queue = new Queue();
queue.enqueue(3);
queue.enqueue(5);
queue.enqueue(7);
queue.print();
queue.dequeue();
queue.dequeue();
queue.print();

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

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


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

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.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代碼。


/*------------------------------------------------------------------ 
 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))

在我看來,內置陣列對於堆棧很好。 如果你想在TypeScript中有一個Queue,那麼這是一個實現

/**
 * A Typescript implementation of a queue.
 */
export default class Queue {

  private queue = [];
  private offset = 0;

  constructor(array = []) {
    // Init the queue using the contents of the array
    for (const item of array) {
      this.enqueue(item);
    }
  }

  /**
   * @returns {number} the length of the queue.
   */
  public getLength(): number {
    return (this.queue.length - this.offset);
  }

  /**
   * @returns {boolean} true if the queue is empty, and false otherwise.
   */
  public isEmpty(): boolean {
    return (this.queue.length === 0);
  }

  /**
   * Enqueues the specified item.
   *
   * @param item - the item to enqueue
   */
  public enqueue(item) {
    this.queue.push(item);
  }

  /**
   *  Dequeues an item and returns it. If the queue is empty, the value
   * {@code null} is returned.
   *
   * @returns {any}
   */
  public dequeue(): any {
    // if the queue is empty, return immediately
    if (this.queue.length === 0) {
      return null;
    }

    // store the item at the front of the queue
    const item = this.queue[this.offset];

    // increment the offset and remove the free space if necessary
    if (++this.offset * 2 >= this.queue.length) {
      this.queue = this.queue.slice(this.offset);
      this.offset = 0;
    }

    // return the dequeued item
    return item;
  };

  /**
   * Returns the item at the front of the queue (without dequeuing it).
   * If the queue is empty then {@code null} is returned.
   *
   * @returns {any}
   */
  public peek(): any {
    return (this.queue.length > 0 ? this.queue[this.offset] : null);
  }

}

這是一個Jest測試

it('Queue', () => {
  const queue = new Queue();
  expect(queue.getLength()).toBe(0);
  expect(queue.peek()).toBeNull();
  expect(queue.dequeue()).toBeNull();

  queue.enqueue(1);
  expect(queue.getLength()).toBe(1);
  queue.enqueue(2);
  expect(queue.getLength()).toBe(2);
  queue.enqueue(3);
  expect(queue.getLength()).toBe(3);

  expect(queue.peek()).toBe(1);
  expect(queue.getLength()).toBe(3);
  expect(queue.dequeue()).toBe(1);
  expect(queue.getLength()).toBe(2);

  expect(queue.peek()).toBe(2);
  expect(queue.getLength()).toBe(2);
  expect(queue.dequeue()).toBe(2);
  expect(queue.getLength()).toBe(1);

  expect(queue.peek()).toBe(3);
  expect(queue.getLength()).toBe(1);
  expect(queue.dequeue()).toBe(3);
  expect(queue.getLength()).toBe(0);

  expect(queue.peek()).toBeNull();
  expect(queue.dequeue()).toBeNull();
});

希望有人認為這有用,

乾杯,

斯圖


Javascript數組shift()很慢,尤其是在持有很多元素時。 我知道兩種方式來實現具有分期O(1)複雜性的隊列。

首先是使用循環緩沖和表倍增。 我以前已經實現過。 你可以在這裡看到我的源代碼https://github.com/kevyuu/rapid-queue

第二種方法是使用兩個堆棧。 這是兩個堆棧的隊列的代碼

function createDoubleStackQueue() {
var that = {};
var pushContainer = [];
var popContainer = [];

function moveElementToPopContainer() {
    while (pushContainer.length !==0 ) {
        var element = pushContainer.pop();
        popContainer.push(element);
    }
}

that.push = function(element) {
    pushContainer.push(element);
};

that.shift = function() {
    if (popContainer.length === 0) {
        moveElementToPopContainer();
    }
    if (popContainer.length === 0) {
        return null;
    } else {
        return popContainer.pop();
    }
};

that.front = function() {
    if (popContainer.length === 0) {
        moveElementToPopContainer();
    }
    if (popContainer.length === 0) {
        return null;
    }
    return popContainer[popContainer.length - 1];
};

that.length = function() {
    return pushContainer.length + popContainer.length;
};

that.isEmpty = function() {
    return (pushContainer.length + popContainer.length) === 0;
};

return that;}

這是使用jsPerf進行性能比較

CircularQueue.shift()與Array.shift()

http://jsperf.com/rapidqueue-shift-vs-array-shift

正如你所看到的,對於大數據集來說,它顯著更快


陣列。

堆棧:

var stack = [];

//put value on top of stack
stack.push(1);

//remove value from top of stack
var value = stack.pop();

隊列:

var queue = [];

//put value on end of queue
queue.push(1);

//Take first value from queue
var value = queue.shift();

無數組(s)

//Javascript stack linked list data structure (no array)

function node(value, noderef) {
    this.value = value;
    this.next = noderef;
}
function stack() {
    this.push = function (value) {
        this.next = this.first;
        this.first = new node(value, this.next);
    }
    this.pop = function () {
        var popvalue = this.first.value;
        this.first = this.first.next;
        return popvalue;
    }
    this.hasnext = function () {
        return this.next != undefined;
    }
    this.isempty = function () {
        return this.first == undefined;
    }

}

//Javascript stack linked list data structure (no array)
function node(value, noderef) {
    this.value = value;
    this.next = undefined;
}
function queue() {
    this.enqueue = function (value) {
        this.oldlast = this.last;
        this.last = new node(value);
        if (this.isempty())
            this.first = this.last;
        else 
           this.oldlast.next = this.last;
    }
    this.dequeue = function () {
        var queuvalue = this.first.value;
        this.first = this.first.next;
        return queuvalue;
    }
    this.hasnext = function () {
        return this.first.next != undefined;
    }
    this.isempty = function () {
        return this.first == 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 temp_stack = new Array();
var stack = new Array();

temp_stack.push(1);
temp_stack.push(2);
temp_stack.push(3);

如果我現在彈出元素,那麼輸出將是3,2,1。 但是我們需要FIFO結構,因此您可以執行以下操作。

stack.push(temp_stack.pop());
stack.push(temp_stack.pop());
stack.push(temp_stack.pop());

stack.pop(); //Pop out 1
stack.pop(); //Pop out 2
stack.pop(); //Pop out 3

有很多方法可以在Javascript中實現堆棧和隊列。 上面的大多數答案都是非常淺的實現,我會嘗試實現更可讀的(使用es6的新語法特性)和強大的。

以下是堆棧實現:

class Stack {
  constructor(...items){
    this._items = []

    if(items.length>0)
      items.forEach(item => this._items.push(item) )

  }

  push(...items){
    //push item to the stack
     items.forEach(item => this._items.push(item) )
     return this._items;

  }

  pop(count=0){
    //pull out the topmost item (last item) from stack
    if(count===0)
      return this._items.pop()
     else
       return this._items.splice( -count, count )
  }

  peek(){
    // see what's the last item in stack
    return this._items[this._items.length-1]
  }

  size(){
    //no. of items in stack
    return this._items.length
  }

  isEmpty(){
    // return whether the stack is empty or not
    return this._items.length==0
  }

  toArray(){
    return this._items;
  }
}

這就是你如何使用堆棧:

let my_stack = new Stack(1,24,4);
// [1, 24, 4]
my_stack.push(23)
//[1, 24, 4, 23]
my_stack.push(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_stack.pop();
//[1, 24, 4, 23, 1, 2]
my_stack.pop(3)
//[1, 24, 4]
my_stack.isEmpty()
// false
my_stack.size();
//3

如果您想查看關於此實現的詳細描述以及如何進一步改進,請閱讀以下鏈接: http://jschap.com/data-structures-in-javascript-stack/ : http://jschap.com/data-structures-in-javascript-stack/

以下是es6中的隊列實現代碼:

class Queue{
 constructor(...items){
   //initialize the items in queue
   this._items = []
   // enqueuing the items passed to the constructor
   this.enqueue(...items)
 }

  enqueue(...items){
    //push items into the queue
    items.forEach( item => this._items.push(item) )
    return this._items;
  }

  dequeue(count=1){
    //pull out the first item from the queue
    this._items.splice(0,count);
    return this._items;
  }

  peek(){
    //peek at the first item from the queue
    return this._items[0]
  }

  size(){
    //get the length of queue
    return this._items.length
  }

  isEmpty(){
    //find whether the queue is empty or no
    return this._items.length===0
  }
}

以下是您可以如何使用此實現的方法:

let my_queue = new Queue(1,24,4);
// [1, 24, 4]
my_queue.enqueue(23)
//[1, 24, 4, 23]
my_queue.enqueue(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_queue.dequeue();
//[24, 4, 23, 1, 2, 342]
my_queue.dequeue(3)
//[1, 2, 342]
my_queue.isEmpty()
// false
my_queue.size();
//3

要詳細了解如何實現這些數據結構以及如何進一步改進這些數據結構,您可能需要瀏覽jschap.com中的'使用JavaScript中的數據結構'系列。 以下是隊列的鏈接 - http://jschap.com/playing-data-structures-javascript-queues/


這是鏈接列表版本的一個隊列,也包含最後一個節點,正如@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;
};

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

對於隊列,請看這裡:

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

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

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


你可以使用你自己的基於概念的自定義類,這裡是你可以用來做這些事情的代碼片段

/*
*   Stack implementation in JavaScript
*/

function Stack(){
    this.top = null;
    this.count = 0;

    this.getCount = function(){
        return this.count;
    }

    this.getTop = function(){
        return this.top;
    }

    this.push = function(data){
        var node = {
            data : data,
            next : null
        }

        node.next = this.top;
        this.top = node;

        this.count++;
    }

    this.peek = function(){
        if(this.top === null){
            return null;
        }else{
            return this.top.data;
        }
    }

    this.pop = function(){
        if(this.top === null){
            return null;
        }else{
            var out = this.top;
            this.top = this.top.next;
            if(this.count>0){
                this.count--;
            }

            return out.data;
        }
    }

    this.displayAll = function(){
        if(this.top === null){
            return null;
        }else{
            var arr = new Array();

            var current = this.top;
            //console.log(current);
            for(var i = 0;i<this.count;i++){
                arr[i] = current.data;
                current = current.next;
            }

            return arr;
        }
    }
}

並檢查這個使用你的控制台,並嘗試這些行一個接一個。

>> var st = new Stack();

>> st.push("BP");

>> st.push("NK");

>> st.getTop();

>> st.getCount();

>> st.displayAll();

>> st.pop();

>> st.displayAll();

>> st.getTop();

>> st.peek();

  var x = 10; 
  var y = 11; 
  var Queue = new Array();
  Queue.unshift(x);
  Queue.unshift(y);

  console.log(Queue)
  // Output [11, 10]

  Queue.pop()
  console.log(Queue)
  // Output [11]

var stack = [];
stack.push(2);       // stack is now [2]
stack.push(5);       // stack is now [2, 5]
var i = stack.pop(); // stack is now [2]
alert(i);            // displays 5

var queue = [];
queue.push(2);         // queue is now [2]
queue.push(5);         // queue is now [2, 5]
var i = queue.shift(); // queue is now [5]
alert(i);              // displays 2

取自“ 9個你可能不知道的JavaScript技巧


在20世紀80年代,UNIX像兔子一樣傳播,大公司自己推銷。埃克森只有一個,歷史上丟失了數十個品牌。如何記憶是由許多實施者自行決定的。

典型的C程序在內存中平放,有機會通過更改brk()值來增加。通常,HEAP剛好低於此brk值,並且增加的brk增加了可用堆的數量。

單個STACK通常是HEAP下面的一個區域,它是一個內存區域,直到下一個固定內存塊的頂部才包含任何有價值的內容。下一個塊通常是CODE,它可以在其時代的一個著名黑客中被堆棧數據覆蓋。

一個典型的存儲器塊是BSS(零值塊),在一個製造商的產品中意外沒有歸零。另一個是包含初始化值的DATA,包括字符串和數字。第三個是包含CRT(C運行時),main,函數和庫的CODE。

UNIX中虛擬內存的出現改變了許多約束。沒有客觀原因,為什麼這些塊需要連續,或固定大小,或現在以特定方式排序。當然,在UNIX之前沒有受到這些限制的Multics。這是一個顯示那個時代的存儲器佈局之一的示意圖。







javascript data-structures stack queue