Comment implémentez-vous une pile et une file d'attente en JavaScript?

Question

Quelle est la meilleure façon de mettre en œuvre une Pile et une File d'attente en JavaScript?

Je suis à la recherche de faire de la shunting-yard algorithme et je vais avoir besoin de ces données-structures.

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

extrait de "9 javascript conseils, vous ne pouvez pas savoir"

Answer 2

Javascript a push et pop méthodes qui fonctionnent sur ordinaire tableau Javascript les objets.

Pour les files d'attente, regardez ici:

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

Les files d'attente peuvent être mises en œuvre dans JavaScript en utilisant le push et changement de méthodes ou d'annuler le déplacement et la pop les méthodes de l'objet array. Bien que c'est un moyen simple à mettre en œuvre les files d'attente, il est très inefficace pour de grandes files d'attente - parce que les méthodes fonctionner sur les tableaux, l'évolution et l' unshift méthodes de déplacer tous les éléments de le tableau à chaque fois qu'ils sont appelés.

Queue.js est un moyen simple et efficace de la file d'attente de la mise en œuvre de JavaScript dont la résorption de la fonction s'exécute en temps constant amorti. En conséquence, pour de grandes files d'attente, il peut être beaucoup plus importante que l'aide de tableaux.

Answer 3

Les tableaux de.

Pile:

var stack = [];

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

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

File d'attente:

var queue = [];

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

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

Answer 4

Si vous voulez faire vos propres structures de données, vous pouvez construire votre propre:

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

Et pour la file d'attente:

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 5

Ou d'autre, vous pouvez utiliser deux tableaux pour mettre en œuvre la file d'attente de la structure de données.

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

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

Si je pop les éléments de maintenant, alors la sortie sera 3,2,1. Mais nous voulons FIFO structure de sorte que vous pouvez effectuer les opérations suivantes.

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