Wie implementiert man einen Stapel und eine Warteschlange in JavaScript?

Question

Wie lassen sich ein Stapel und eine Warteschlange in JavaScript am besten implementieren?

Ich möchte den Shunting-Yard-Algorithmus anwenden und benötige diese Datenstrukturen.

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

entnommen aus " 9 JavaScript-Tipps, die Sie vielleicht nicht kennen "

Answer 2

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

Answer 3

Javascript hat Push- und Pop-Methoden, die auf gewöhnliche Javascript-Array-Objekte wirken.

Für Warteschlangen, siehe hier:

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

Warteschlangen können implementiert werden in JavaScript implementiert werden, indem entweder die Push- und shift-Methoden oder unshift- und pop Methoden des Array-Objekts implementiert werden. Obwohl ist dies eine einfache Methode zur Implementierung von Warteschlangen zu implementieren, ist es sehr ineffizient für große Warteschlangen - da die Methoden die auf Arrays operieren, die Verschiebung und unshift-Methoden jedes Element in der Array jedes Mal, wenn sie aufgerufen werden.

Queue.js ist eine einfache und effiziente Warteschlangen-Implementierung für JavaScript, deren Dequeue-Funktion in amortisierter konstanter Zeit abläuft. Daher kann sie bei größeren Warteschlangen deutlich schneller sein als die Verwendung von Arrays.

Answer 4

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

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

Answer 5

Hier ist meine Implementierung eines Stacks und einer Warteschlange unter Verwendung einer verknüpften 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();