Wie implementieren Sie einen Stapel und eine Warteschlange in JavaScript?

741

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.

KingNestor
quelle

Antworten:

1347
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 "

Corey Ballou
quelle
218
Ich würde zur Vorsicht bei der Verwendung von queue.shift raten. IIRC ist nicht O (1), sondern O (n) und möglicherweise zu langsam, wenn die Warteschlange groß wird.
MAK
20
Ich würde sagen, dass dies von der Javascript-Implementierung abhängt. Ich glaube nicht, dass es in der Javascript-Spezifikation definiert ist.
Georg Schölly
9
Unter code.stephenmorley.org/javascript/queues finden Sie eine einfache Implementierung, die die Leistung der Warteschlange verbessert.
Gili
15
Informationen zu Problemen mit der Warteschlangenleistung finden Sie unter jsperf.com/queue-push-unshift-vs-shift-pop. Wenn nur jemand nett genug wäre, eine Version dieses jsperf aufzunehmen, wäre dies ein guter Vergleich von drei verschiedenen Arten von Stapelverhalten enthalten das JS-Skript, das @Gili erwähnt hat ...
Nenotlep
3
Ich habe den in dieser Antwort verlinkten Blog-Beitrag wiederbelebt , da archive.org nicht immer der leistungsstärkste ist. Ich habe Links und Bilder aktualisiert, damit sie funktionieren, aber ich habe nichts anderes geändert.
Chev
87

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.

Robert Harvey
quelle
2
Mit dem Link, den Sie geteilt haben, konnten die Benchmark-Ergebnisse überprüft werden. Beim Testen mit Google Chrome Version 59 werden keine Leistungssteigerungen festgestellt. Queue.js stimmt nicht mit der Geschwindigkeit überein, Chrome stimmte jedoch mit der Geschwindigkeit überein.
Shiljo Paulson
Außerdem habe ich mit der Datei queue.js eine Demo erstellt, bei der die Dequeue-Funktion das Element nicht wirklich aus der Warteschlange entfernt. Ich frage mich also, ob es vermutlich so funktioniert. Wenn ja, wie können Sie die neue Warteschlange abrufen, nachdem Sie das vorherige Element aus der Warteschlange entfernt haben? codepen.io/adamchenwei/pen/VxgNrX?editors=0001
Ezeewei
Es sieht so aus, als ob die Warteschlange in queue.js auch zusätzlichen Speicher benötigt, da das Array mit Slice geklont wird.
JaTo
Darüber hinaus wird das zugrunde liegende Array mit jedem hinzugefügten Element größer und größer. Obwohl die Implementierung von Zeit zu Zeit die Arraygröße verringert, nimmt die Gesamtgröße zu.
Philipp Mitterer
73

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();
Jani Hartikainen
quelle
1
Array.prototype.pop entfernt den Wert nicht vom oberen Rand (erstes Element) des Arrays. Es entfernt den Wert vom unteren (letzten Element) des Arrays.
Michael Geller
21
@MichaelGeller Die Oberseite des Stapels ist das letzte Element des Arrays. Array-Push- und Pop-Methoden verhalten sich wie ein Stapel.
mrdommyg
@mrdommyg Array.prototype.pop entfernt das letzte Element des Arrays (siehe developer.mozilla.org/en/docs/Web/JavaScript/Reference/… ). Zuletzt bedeutet in diesem Zusammenhang das Element mit dem höchsten Index. Ein Array in JS hat nichts mit einem Stapel zu tun. Es ist kein Stapel, nur weil es eine Pop-Methode hat. Pop bedeutet nur "das letzte Element entfernen und zurückgeben". Natürlich können Sie die Funktionalität eines Stapels mit einem Array nachahmen, aber ein Array ist per Definition immer noch kein Stapel. Es ist immer noch eine Liste (ein "list like" Objekt gemäß MDN).
Michael Geller
5
@MichaelGeller Das Verhalten eines Stacks ist "first in, last out". Wenn Sie es mit einem Array in JavaScript mit seinen pushund popMethoden implementieren , ist das Problem behoben. Ich verstehe Ihren Standpunkt hier nicht wirklich.
Rax Weber
2
@ MichaelGeller Ein Stack ist konzeptionell. Ein JS-Array ist (unter anderem) per Definition ein Stapel aufgrund der Implementierung der Stapelsemantik. Nur weil es auch Array-Semantik implementiert, ändert das nichts. Sie können ein JS-Array wie einen sofort einsatzbereiten Stapel verwenden. In diesem Zusammenhang ist das "Top" -Element das, was Sie pushen und platzieren.
Hans
32

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;
};
user2954463
quelle
13
Um zu vermeiden, dass Sie das gesamte Objekt durchlaufen müssen, um es an das Ende anzuhängen, speichern Sie über this.last = node einen Verweis auf den letzten.
Perkins
9
Implementieren Sie niemals eine solche Warteschlange, es sei denn, Sie haben einen wirklich guten Grund dafür ... Obwohl dies logisch korrekt erscheint, arbeiten CPUs nicht nach menschlichen Abstraktionen. Das Iterieren über eine Datenstruktur mit Zeigern überall führt zu Cache-Fehlern in der CPU, im Gegensatz zu einem sequentiellen Array, das hocheffizient ist. blog.davidecoppola.com/2014/05/… CPUs HASSEN Zeiger mit brennender Leidenschaft - sie sind wahrscheinlich die häufigste Ursache für Cache-Fehler und den Zugriff auf Speicher aus dem RAM.
Centril
1
Dies ist eine verlockende Lösung, aber ich sehe nicht, dass erstellte Nodes beim Poppen / Dequeuing gelöscht werden. Sitzen sie nicht einfach herum, um den Speicher zu belasten, bis der Browser abstürzt?
Cneuro
5
@cneuro Im Gegensatz zu C ++ ist JavaScript eine Sprache, in der Müll gesammelt wird. Es hat ein deleteSchlüsselwort, aber das ist nur nützlich, um eine Eigenschaft eines Objekts als nicht vorhandenundefined zu markieren - was sich von der Zuweisung nur zu der Eigenschaft unterscheidet . JavaScript hat auch einen newOperator, der jedoch nur verwendet wird, um thisbeim Aufrufen einer Funktion ein neues leeres Objekt festzulegen. In C ++ müssen Sie alle newmit einem deletekoppeln, aber nicht in JavaScript, weil GC. Um die Verwendung von Speicher in JavaScript zu beenden, hören Sie einfach auf, auf das Objekt zu verweisen, und es wird schließlich zurückgefordert.
Binki
Ist es nicht auch notwendig, einen Stapel auf Überlauf zu prüfen, indem eine maximale Stapelgröße festgelegt wird?
Biene
16

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

Rohit
quelle
10

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

Kevinvinu
quelle
8

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/

Anish K.
quelle
7

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();
jforjs
quelle
2
Downvote für eine Namenskonvention: Methode, die mit einem Kapital beginnt, das als Konstruktor angenommen wird.
Pavlo
6
/*------------------------------------------------------------------ 
 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))
Arijit Basu
quelle
5

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
Ni3
quelle
1
Dies funktioniert nur, wenn Sie nie pushnach dem ersten Mal Siepop
jnnnnn
5

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; };
snydergd
quelle
5

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.

coyotte508
quelle
4

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
Javier Giovannini
quelle
Ein Wort der Warnung für diejenigen, die leistungskritische Software schreiben. Die .shift()Methode ist keine ordnungsgemäße Warteschlangenimplementierung. Es ist eher O (n) als O (1) und ist bei großen Warteschlangen langsam.
Rudi Kershaw
3

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;
};
DrByrd
quelle
In der Warteschlange sollten Sie stattdessen temp.data zurückgeben. Denn genau das wurde in die Warteschlange gestellt.
kein Roboter
3

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 .

Oleksii Trekhleb
quelle
2

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

}
Andriy
quelle
Wie kann ich eine bestimmte interne Funktion wie Push Pop ausführen?
Chandan Kumar
2

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

Justin Niessner
quelle
2

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

Daniel Barrientos
quelle
1
  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]
Rajesh Kumar
quelle
1

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

Stuart Clark
quelle
0

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.

Echo
quelle
0

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());
Hitesh Joshi
quelle
0

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
Salar
quelle
0

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());
    }
  }
}
Yuki-Träumer
quelle