Wie implementieren Sie einen Stapel und eine Warteschlange in JavaScript?

Was ist der beste Weg, um einen Stapel und eine Warteschlange in JavaScript zu implementieren?

Ich möchte den Shunt-Yard-Algorithmus ausführen und benötige diese Datenstrukturen.

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

entnommen aus " 9 Javascript-Tipps, die Sie möglicherweise nicht kennen "

Javascript verfügt über Push- und Pop-Methoden, die mit normalen Javascript-Array-Objekten arbeiten.

Warteschlangen finden Sie hier:

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

Warteschlangen können in JavaScript entweder mit den Push- und Shift-Methoden oder mit den Unshift- und Pop-Methoden des Array-Objekts implementiert werden. Obwohl dies eine einfache Methode zum Implementieren von Warteschlangen ist, ist sie für große Warteschlangen sehr ineffizient. Aufgrund der Methoden, die auf Arrays ausgeführt werden, verschieben die Shift- und Unshift-Methoden jedes Element im Array bei jedem Aufruf.

Queue.js ist eine einfache und effiziente Warteschlangenimplementierung für JavaScript, deren Warteschlangenfunktion in einer amortisierten konstanten Zeit ausgeführt wird. Infolgedessen kann es bei größeren Warteschlangen erheblich schneller sein als bei Verwendung von Arrays.

Arrays.

Stapel:

var stack = [];

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

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

Warteschlange:

var queue = [];

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

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

Wenn Sie Ihre eigenen Datenstrukturen erstellen möchten, können Sie Ihre eigenen erstellen:

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;
};

Und für die Warteschlange:

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;
};

Meine Implementierung Stackund QueueVerwendungLinked List

// 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 Array Shift () ist langsam, insbesondere wenn viele Elemente enthalten sind. Ich kenne zwei Möglichkeiten, um eine Warteschlange mit amortisierter O (1) -Komplexität zu implementieren.

Erstens wird ein Kreispuffer und eine Tabellenverdopplung verwendet. Ich habe dies schon einmal implementiert. Sie können meinen Quellcode hier https://github.com/kevyuu/rapid-queue sehen

Der zweite Weg ist die Verwendung von zwei Stapeln. Dies ist der Code für eine Warteschlange mit zwei Stapeln

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;}

Dies ist ein Leistungsvergleich mit jsPerf

CircularQueue.shift () vs Array.shift ()

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

Wie Sie sehen, ist es bei großen Datenmengen erheblich schneller

Es gibt einige Möglichkeiten, wie Sie Stapel und Warteschlangen in Javascript implementieren können. Die meisten der obigen Antworten sind recht flache Implementierungen, und ich würde versuchen, etwas Lesbareres (unter Verwendung der neuen Syntaxfunktionen von es6) und Robusteres zu implementieren.

Hier ist die Stack-Implementierung:

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;
  }
}

Und so können Sie den Stack verwenden:

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

Wenn Sie die detaillierte Beschreibung dieser Implementierung sehen möchten und wissen möchten, wie sie weiter verbessert werden kann, lesen Sie hier: http://jschap.com/data-structures-in-javascript-stack/

Hier ist der Code für die Implementierung der Warteschlange in 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
  }
}

So können Sie diese Implementierung verwenden:

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

Um das vollständige Tutorial zu lesen, wie diese Datenstrukturen implementiert wurden und wie diese weiter verbessert werden können, sollten Sie die Reihe "Spielen mit Datenstrukturen in Javascript" auf jschap.com durchgehen. Hier sind die Links für Warteschlangen - http://jschap.com/playing-data-structures-javascript-queues/

Sie können Ihre eigene Anpassungsklasse verwenden, die auf dem Konzept basiert, hier das Code-Snippet, mit dem Sie die Dinge erledigen können

/*
*   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;
    }
  }
}

und um dies zu überprüfen, verwenden Sie Ihre Konsole und versuchen Sie diese Zeile nacheinander.

>> var st = new Stack();

>> st.push("BP");

>> st.push("NK");

>> st.getTop();

>> st.getCount();

>> st.displayAll();

>> st.pop();

>> st.displayAll();

>> st.getTop();

>> st.peek();

/*------------------------------------------------------------------ 
 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("Stack Overflow")
                }
            },
            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))

Sie können auch zwei Arrays verwenden, um die Warteschlangendatenstruktur zu implementieren.

var temp_stack = new Array();
var stack = new Array();

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

Wenn ich die Elemente jetzt platziere, ist die Ausgabe 3,2,1. Wir möchten jedoch eine FIFO-Struktur, damit Sie Folgendes tun können.

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

Hier ist eine ziemlich einfache Implementierung der Warteschlange mit zwei Zielen:

• Im Gegensatz zu array.shift () wissen Sie, dass diese Dequeue-Methode eine konstante Zeit benötigt (O (1)).
• Um die Geschwindigkeit zu verbessern, werden bei diesem Ansatz viel weniger Zuordnungen verwendet als beim Ansatz mit verknüpften Listen.

Die Stack-Implementierung teilt nur das zweite Ziel.

// 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; };

Die Stapelimplementierung ist trivial, wie in den anderen Antworten erläutert.

Allerdings habe ich in diesem Thread keine zufriedenstellenden Antworten für die Implementierung einer Warteschlange in Javascript gefunden, daher habe ich meine eigenen erstellt.

In diesem Thread gibt es drei Arten von Lösungen:

• Arrays - Die schlechteste Lösung mit array.shift() für ein großes Array ist sehr ineffizient.
• Verknüpfte Listen - Es ist O (1), aber die Verwendung eines Objekts für jedes Element ist etwas übertrieben, insbesondere wenn es viele davon gibt und sie klein sind, wie das Speichern von Zahlen.
• Arrays mit verzögerter Verschiebung - Es besteht aus der Zuordnung eines Index zum Array. Wenn ein Element aus der Warteschlange entfernt wird, bewegt sich der Index vorwärts. Wenn der Index die Mitte des Arrays erreicht, wird das Array in zwei Teile geteilt, um die erste Hälfte zu entfernen.

Arrays mit verzögerter Verschiebung sind für mich die zufriedenstellendste Lösung, aber sie speichern immer noch alles in einem großen zusammenhängenden Array, was problematisch sein kann, und die Anwendung wird versetzt, wenn das Array in Scheiben geschnitten wird.

Ich habe eine Implementierung mit verknüpften Listen kleiner Arrays (jeweils maximal 1000 Elemente) durchgeführt. Die Arrays verhalten sich wie Arrays mit verzögerter Verschiebung, außer dass sie niemals in Scheiben geschnitten werden: Wenn jedes Element im Array entfernt wird, wird das Array einfach verworfen.

Das Paket ist auf npm mit grundlegenden FIFO-Funktionen, ich habe es erst kürzlich gepusht. Der Code ist in zwei Teile geteilt.

Hier ist der erste Teil

/** 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;
}

Und hier ist die Hauptklasse 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;
}

Typanmerkungen ( : X) können leicht entfernt werden, um ES6-Javascript-Code zu erhalten.

Wenn Sie Stapel mit den Funktionen push () und pop () verstehen, dient die Warteschlange nur dazu, eine dieser Operationen im entgegengesetzten Sinne durchzuführen. Das Gegenteil von push () ist unshift () und das Gegenteil von pop () ist shift (). Dann:

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

Hier ist die verknüpfte Listenversion einer Warteschlange, die auch den letzten Knoten enthält, wie von @perkins vorgeschlagen und am besten geeignet.

// 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;
};

Wenn Sie nach einer ES6 OOP-Implementierung der Stack- und Queue-Datenstruktur mit einigen grundlegenden Vorgängen (basierend auf verknüpften Listen) suchen, sieht dies möglicherweise folgendermaßen aus:

Queue.js

import LinkedList from '../linked-list/LinkedList';

export default class Queue {
  constructor() {
    this.linkedList = new LinkedList();
  }

  isEmpty() {
    return !this.linkedList.tail;
  }

  peek() {
    if (!this.linkedList.head) {
      return null;
    }

    return this.linkedList.head.value;
  }

  enqueue(value) {
    this.linkedList.append(value);
  }

  dequeue() {
    const removedHead = this.linkedList.deleteHead();
    return removedHead ? removedHead.value : null;
  }

  toString(callback) {
    return this.linkedList.toString(callback);
  }
}

Stack.js

import LinkedList from '../linked-list/LinkedList';

export default class Stack {
  constructor() {
    this.linkedList = new LinkedList();
  }

  /**
   * @return {boolean}
   */
  isEmpty() {
    return !this.linkedList.tail;
  }

  /**
   * @return {*}
   */
  peek() {
    if (!this.linkedList.tail) {
      return null;
    }

    return this.linkedList.tail.value;
  }

  /**
   * @param {*} value
   */
  push(value) {
    this.linkedList.append(value);
  }

  /**
   * @return {*}
   */
  pop() {
    const removedTail = this.linkedList.deleteTail();
    return removedTail ? removedTail.value : null;
  }

  /**
   * @return {*[]}
   */
  toArray() {
    return this.linkedList
      .toArray()
      .map(linkedListNode => linkedListNode.value)
      .reverse();
  }

  /**
   * @param {function} [callback]
   * @return {string}
   */
  toString(callback) {
    return this.linkedList.toString(callback);
  }
}

Die LinkedList-Implementierung, die in den obigen Beispielen für Stack und Queue verwendet wird, finden Sie hier auf GitHub .

Keine Arrays

//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;
    }

}

Die reguläre Array-Struktur in Javascript ist ein Stapel (first in, last out) und kann je nach den von Ihnen getätigten Aufrufen auch als Warteschlange (first in, first out) verwendet werden.

Überprüfen Sie diesen Link, um zu sehen, wie sich ein Array wie eine Warteschlange verhält:

Warteschlangen

Grüße,

In Javascript werden Stapel und Warteschlangen wie folgt implementiert:

Stapel: Ein Stapel ist ein Container mit Objekten, die nach dem LIFO-Prinzip (Last-In-First-Out) eingefügt und entfernt werden.

• Push: Die Methode fügt ein oder mehrere Elemente am Ende eines Arrays hinzu und gibt die neue Länge des Arrays zurück.
• Pop: Methode entfernt das letzte Element aus einem Array und gibt dieses Element zurück.

Warteschlange: Eine Warteschlange ist ein Container mit Objekten (eine lineare Sammlung), die nach dem FIFO-Prinzip (First-In-First-Out) eingefügt und entfernt werden.

• Unshift: Die Methode fügt ein oder mehrere Elemente am Anfang eines Arrays hinzu.

• Shift: Die Methode entfernt das erste Element aus einem Array.

let stack = [];
 stack.push(1);//[1]
 stack.push(2);//[1,2]
 stack.push(3);//[1,2,3]
 
console.log('It was inserted 1,2,3 in stack:', ...stack);

stack.pop(); //[1,2]
console.log('Item 3 was removed:', ...stack);

stack.pop(); //[1]
console.log('Item 2 was removed:', ...stack);


let queue = [];
queue.push(1);//[1]
queue.push(2);//[1,2]
queue.push(3);//[1,2,3]

console.log('It was inserted 1,2,3 in queue:', ...queue);

queue.shift();// [2,3]
console.log('Item 1 was removed:', ...queue);

queue.shift();// [3]
console.log('Item 2 was removed:', ...queue);

  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]

Mir scheint, dass das eingebaute Array für einen Stack in Ordnung ist. Wenn Sie eine Warteschlange in TypeScript möchten, finden Sie hier eine Implementierung

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

}

Und hier ist ein JestTest dafür

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();
});

Hoffe, jemand findet das nützlich,

Prost,

Stu

Erstellen Sie ein Klassenpaar, das die verschiedenen Methoden für jede dieser Datenstrukturen bereitstellt (Push, Pop, Peek usw.). Implementieren Sie nun die Methoden. Wenn Sie mit den Konzepten hinter Stack / Queue vertraut sind, sollte dies ziemlich einfach sein. Sie können den Stapel mit einem Array und eine Warteschlange mit einer verknüpften Liste implementieren, obwohl es sicherlich andere Möglichkeiten gibt, dies zu tun. Javascript macht dies einfach, da es schwach typisiert ist, sodass Sie sich nicht einmal um generische Typen kümmern müssen, was Sie tun müssten, wenn Sie es in Java oder C # implementieren würden.

Hier ist meine Implementierung von Stacks.

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());

Sie können WeakMaps zum Implementieren von Privateigentum in der ES6-Klasse und für die Vorteile von String-Eigenschaften und -Methoden in der folgenden JavaScript-Sprache verwenden:

const _items = new WeakMap();

class Stack {
  constructor() {
    _items.set(this, []);
  }

push(obj) {
  _items.get(this).push(obj);
}

pop() {
  const L = _items.get(this).length;
  if(L===0)
    throw new Error('Stack is empty');
  return _items.get(this).pop();
}

peek() {
  const items = _items.get(this);
  if(items.length === 0)
    throw new Error ('Stack is empty');
  return items[items.length-1];
}

get count() {
  return _items.get(this).length;
}
}

const stack = new Stack();

//now in console:
//stack.push('a')
//stack.push(1)
//stack.count   => 2
//stack.peek()  => 1
//stack.pop()   => 1
//stack.pop()   => "a"
//stack.count   => 0
//stack.pop()   => Error Stack is empty

Erstellen Sie eine Warteschlange mit zwei Stapeln.

O (1) sowohl für Warteschlangen- als auch für Warteschlangenoperationen.

class Queue {
  constructor() {
    this.s1 = []; // in
    this.s2 = []; // out
  }

  enqueue(val) {
    this.s1.push(val);
  }

  dequeue() {
    if (this.s2.length === 0) {
      this._move();
    }

    return this.s2.pop(); // return undefined if empty
  }

  _move() {
    while (this.s1.length) {
      this.s2.push(this.s1.pop());
    }
  }
}