Come si implementa uno stack e una coda in JavaScript?

Question

Qual è il modo migliore per implementare uno stack e una coda in JavaScript?

Sto cercando di eseguire l'algoritmo dello shunting-yard e avrò bisogno di queste strutture dati.

Answer 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 

tratto da "9 javascript tips you may not know"

Answer 2

Array.

Stack:

var stack = []; 

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

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

coda:

var queue = []; 

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

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

Answer 3

La struttura Array regolare JavaScript è una pila (first in, last out) e può essere utilizzato anche come una coda (primo, prima uscita) a seconda delle chiamate effettuate.

Controllare questo link per vedere come fare un atto array come una coda:

Queues

Answer 4

Javascript deve spingere e metodi pop, che operano su normali oggetti array Javascript.

Per le code, guarda qui:

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

Le code possono essere implementate in JavaScript utilizzando la spinta e metodi di spostamento o di non innesto e pop metodi dell'oggetto array. Sebbene questo è un modo semplice per implementare code, è molto inefficiente per grandi code - perché i metodi operano su array, lo spostamento e metodi non innesto muovono ogni elemento matrice ogni volta che vengono chiamati.

Queue.js è un'implementazione di coda semplice ed efficiente per JavaScript la cui funzione di dequeue viene eseguita in tempo costante ammortizzato. Di conseguenza, per le code più grandi può essere notevolmente più veloce rispetto all'utilizzo di matrici.

Answer 5

Creare una coppia di classi che forniscono i vari metodi che ciascuna di queste strutture di dati ha (push, pop, peek, ecc.). Ora implementa i metodi. Se hai familiarità con i concetti alla base dello stack/coda, questo dovrebbe essere piuttosto semplice. Puoi implementare lo stack con un array e una coda con un elenco collegato, sebbene ci siano sicuramente altri modi per farlo. Javascript lo renderà facile, perché è debolmente digitato, quindi non devi nemmeno preoccuparti dei tipi generici, che dovresti fare se lo stavi implementando in Java o C#.

Answer 6

Oppure è possibile utilizzare due array per implementare la struttura dei dati della coda.

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

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

Se ho pop gli elementi ora, allora l'uscita sarà 3,2,1. Ma vogliamo la struttura FIFO in modo che tu possa fare quanto segue.

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 

Answer 7

È possibile utilizzare la propria classe di personalizzare basato sul concetto, ecco il frammento di codice che è possibile utilizzare per fare le cose

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

e controllare questo utilizzare la console e provare questi linea uno da uno.

>> var st = new Stack(); 

>> st.push("BP"); 

>> st.push("NK"); 

>> st.getTop(); 

>> st.getCount(); 

>> st.displayAll(); 

>> st.pop(); 

>> st.displayAll(); 

>> st.getTop(); 

>> st.peek(); 

Answer 8

No Array (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; 
    } 

} 

Answer 9

Se si capisce pile con push() e le funzioni pop(), quindi coda è solo per fare una di queste operazioni in senso opposta. Oposite di push() è unshift() e oposite di pop() es shift(). Poi:

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

Answer 10

Se si voleva fare le proprie strutture di dati, è possibile costruire il proprio:

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

E per la coda:

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

Answer 11

Javascript spostamento array() è lento soprattutto quando si tengono molti elementi. Conosco due modi per implementare la coda con la complessità O (1) ammortizzata.

Per prima cosa viene utilizzato il buffer circolare e il raddoppio della tabella. Ho implementato questo prima. Puoi vedere il mio codice sorgente qui https://github.com/kevyuu/rapid-queue

Il secondo modo è utilizzare due stack. Questo è il codice per la coda con due stack

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

Questo è il confronto delle prestazioni utilizzando jsPerf

CircularQueue.shift() vs Array.shift()

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

Come si può vedere è significativamente più veloce con dataset grande

Answer 12

La mia implementazione di Stack e coda utilizzando lista concatenata

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

Answer 13

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

Answer 14

Ecco un'implementazione di coda abbastanza semplice con due obiettivi:

• differenza Array.shift(), sai che questo metodo di dequeue richiede tempo costante (O (1)).
• Per migliorare la velocità, questo approccio utilizza molte meno allocazioni rispetto all'approccio elenco collegato.

L'implementazione dello stack condivide solo il secondo scopo.

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

Answer 15

ecco la versione lista collegata di una coda che comprende anche l'ultimo nodo, come suggerito da @perkins e come è più appropriato.

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

Answer 16

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] 

Answer 17

Ci sono alcuni modi in cui è possibile implementare pile e code in Javascript. La maggior parte delle risposte sopra riportate sono implementazioni piuttosto superficiali e vorrei provare a implementare qualcosa di più leggibile (usando le nuove funzionalità di sintassi di es6) e robusto.

Ecco l'implementazione dello stack:

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

e in questo modo è possibile utilizzare lo stack:

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 

Se volete vedere la descrizione dettagliata di questa implementazione e come può essere ulteriormente migliorato, puoi leggere qui: http://jschap.com/data-structures-in-javascript-stack/

Ecco il codice per l'implementazione della coda 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 
    } 
} 

Ecco come è possibile utilizzare questa implementazione:

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 

di passare attraverso il tutorial completo di come queste strutture di dati sono state attuate e come possono essere ulteriormente migliorati, si consiglia di passare attraverso il 'Giocare con strutture di dati in serie javascript' su jschap.com. Ecco i link per le code - http://jschap.com/playing-data-structures-javascript-queues/

Answer 18

Ecco la mia implementazione di stack.

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