datastrukturer - Hvordan implementerer man en Stabel og en Kø i JavaScript?

Hva er den beste måten å implementere en stabel og en kø på i JavaScript?

Jeg ser etter å gjøre shunting-yard-algoritmen, og jeg kommer til å trenge disse datastrukturene.

Svar #1

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

tatt fra "9 JavaScript-tips du kanskje ikke kjenner til"

Svar #2

Arrayer.

Stabel :

var stack = [];

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

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

Kø :

var queue = [];

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

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

Svar #3

Javascript har push- og pop-metoder, som opererer på vanlige Javascript-arrayobjekter.

For køer, se her:

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

Køer kan implementeres i JavaScript ved å bruke enten push- og shift-metodene eller unshift- og pop-metodene til array-objektet. Selv om dette er en enkel måte å implementere køer på, er det svært ineffektivt for store køer — fordi metodene opererer på arrays, flytter shift- og unshift-metodene hvert element i arrayet hver gang de kalles.

Queue.js er en enkel og effektiv køimplementering for JavaScript hvor dequeuet-funksjonen kjører i amortisert konstant tid. Som et resultat kan det for større køer være betydelig raskere enn å bruke arrays.

Svar #4

Hvis du ønsket å lage dine egne datastrukturer, kunne du bygge dine egne:

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

Og for kø:

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

Svar #5

Her er min implementering av en stakk og en kø ved hjelp av en lenket liste:

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

Svar #6

Stakkimplementeringen er triviel som forklart i de andre svarene.

Jeg fant imidlertid ingen tilfredsstillende svar i denne tråden for å implementere en kø i JavaScript, så jeg laget min egen.

Det er tre typer løsninger i denne tråden:

• Arrays - Den verste løsningen, å bruke array.shift() på et stort array er veldig ineffektivt.
• Lenkede lister - Det er O(1), men å bruke et objekt for hvert element er litt overdreven, spesielt hvis det er mange av dem og de er små, som å lagre tall.
• Forsinkede forskyvningsarrayer - Det består i å knytte en indeks til arrayen. Når et element fjernes fra køen, flyttes indeksen fremover. Når indeksen når midten av arrayen, deles arrayen i to for å fjerne den første halvdelen.

Forskjøvede skiftmatriser er den mest tilfredsstillende løsningen etter min mening, men de lagrer fortsatt alt i en stor sammenhengende matrise, noe som kan være problematisk, og applikasjonen vil hakke når matrisen skjæres.

Jeg laget en implementering ved å bruke lenkede lister av små arrayer (maks 1000 elementer hver). Arrayene oppfører seg som forsinkede shift-arrayer, bortsett fra at de aldri blir delt: når hvert element i arrayen fjernes, blir arrayen rett og slett kassert.

Pakken er på npm med grunnleggende FIFO-funksjonalitet, jeg lastet den nettopp opp nylig. Koden er delt inn i to deler.

Her er den første delen

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

Og her er hovedklassen 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;
}

Typeannotasjoner (: X) kan enkelt fjernes for å få ES6 JavaScript-kode.

Svar #7

Javascript-array shift() er treg, spesielt når den inneholder mange elementer. Jeg kjenner til to måter å implementere kø på med amortisert O(1)-kompleksitet.

Først er det ved å bruke sirkulærbuffer og tabellfordobling. Jeg har implementert dette før. Du kan se kildekoden min her https://github.com/kevyuu/rapid-queue

Den andre måten er ved å bruke to stakker. Dette er koden for kø med to stakker

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

Dette er ytelsessammenligning ved bruk av jsPerf

CircularQueue.shift() vs Array.shift()

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

Som du kan se er det betydelig raskere med store datasett

Svar #8

Som mange har sagt: innfødt array push og pop er fine som stakk-operasjoner, men å bruke shift som kø-ekstraksjonsoperasjon betyr at elementene som blir igjen i arrayet må flyttes, noe som potensielt er langsomt. Ideen om å bruke to stakker for å lage en kø i kevinyu's svar er en god idé for å fikse dette, og selvfølgelig kan det også gjøres med innfødte array-stakker. (Merk: Det var faktisk allerede et svar av Yuki-Dreamer som gjør dette, selv om det er mindre kompakt enn min versjon.)

Her er en kompakt implementering som bruker noen ES5/ES6-funksjoner som lager et køobjekt som oppfører seg så nært som mulig den innebygde push/shift-varianten, bortsett fra at den tar amortisert O(1) tid per operasjon:

const queue = () => {
    const a = [], b = [];
    return {
        push: (...elts) => a.push(...elts),
        shift: () => {
            if (b.length === 0) {
                while (a.length > 0) { b.push(a.pop()) }
            }
            return b.pop();
        },
        get length() { return a.length + b.length }
    }
}

Nå kan du gjøre:

const q = queue();
q.push(8);
q.push(9);
q.push(10);
console.log(q.length);          // outputs 3
console.log(q.shift());         // outputs 8
q.push(11);
console.log(q.shift());         // outputs 9
console.log(q.shift());         // outputs 10
console.log(q.shift());         // outputs 11
console.log(q.shift());         // outputs undefined

Implementeringen av queue bruker en getter-syntaks for length, for å få det til å se ut som en egenskap, og rest parameter-syntaks for push for å tillate å legge til mer enn én ting om gangen. Hvis du ikke vil ha det, kan du erstatte linje 4 med push: elt => a.push(elt),. (Merk imidlertid at du ikke kan erstatte det med push: a.push,, som jeg først prøvde selv med virkelig merkelige resultater: det er fordi det resulterer i at den native push-metoden kalles med this satt til køobjektet.)

OPTIMALISERING: Her er en liten hastighetsforbedring av koden. Erstatt while-linjen med de følgende to linjene for å spare ett push+pop ved hver overføring fra a til b:

                while (a.length > 1) { b.push(a.pop()) }
                return a.pop();

Svar #9

Det finnes ganske mange måter du kan implementere Stacks og Queues i Javascript på. De fleste av svarene ovenfor er ganske overfladiske implementeringer, og jeg ville prøvd å implementere noe mer lesbart (ved å bruke nye syntaksfunksjoner fra ES6) og robust.

Her er stakkimplementeringen:

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

Og slik kan du bruke stakken:

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

Hvis du ønsker å se en detaljert beskrivelse av denne implementeringen og hvordan den kan forbedres ytterligere, kan du lese her: http://jschap.com/data-structures-in-javascript-stack/

Her er koden for køimplementering i 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
  }
}

Slik kan du bruke denne implementeringen:

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

For å gå gjennom hele veiledningen om hvordan disse datastrukturene har blitt implementert og hvordan de kan forbedres videre, kan du gå gjennom serien 'Playing with data structures in javascript' på jschap.com. Her er lenkene for køer - http://jschap.com/playing-data-structures-javascript-queues/