Comment mettre en place une Pile et une File d'attente en JavaScript?

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

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

Tableaux.

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

Ma mise en œuvre de Pile et File en utilisant Liste

JS:

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

Il existe quelques façons dont vous pouvez mettre en œuvre les Piles et les Files d'attente en Javascript. La plupart des réponses ci-dessus sont assez peu profonde implémentations et je voudrais essayer de mettre en place quelque chose de plus lisible (à l'aide de la nouvelle syntaxe caractéristiques de l'es6) et robuste.

Voici la pile de mise en œuvre:

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

Et c'est comment vous pouvez utiliser la pile :

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

Si vous souhaitez voir la description détaillée à propos de cette mise en œuvre et comment il peut encore être amélioré, vous pouvez lire ici : http://jschap.com/data-structures-in-javascript-stack/

Voici le code pour la file d'attente de la mise en œuvre dans l'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
}
}

Voici comment vous pouvez utiliser cette application:

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

De passer par le tutoriel complet de la façon dont ces structures de données ont été mises en œuvre et comment peuvent-ils encore être améliorée, vous pouvez aller à travers le "Jeu avec des structures de données en javascript' de la série à jschap.com . Voici les liens pour les files d'attente - http://jschap.com/playing-data-structures-javascript-queues/

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

Vous pouvez utiliser votre propre personnaliser classe basée sur le concept, voici l'extrait de code que vous pouvez utiliser pour faire les choses

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

et de vérifier ce faire, utilisez votre console et essayer ces ligne un par un.

>> var st = new Stack();
>> st.push("BP");
>> st.push("NK");
>> st.getTop();
>> st.getCount();
>> st.displayAll();
>> st.pop();
>> st.displayAll();
>> st.getTop();
>> st.peek();

Voici la liste liée version de une file d'attente, qui comprend également le dernier nœud, comme suggéré par @perkins et comme dans la plupart des cas.

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

La pile de la mise en œuvre est trivial comme expliqué dans les autres réponses.

Cependant, je n'ai pas trouvé de réponses satisfaisantes à ce fil de discussion pour la mise en œuvre d'une file d'attente en javascript, j'ai donc fait mon propre.

Il existe trois types de solutions dans ce fil:

• Tableaux - La pire des solutions, à l'aide de array.shift() sur un grand tableau est très inefficace
• Listes chaînées - Il est O(1), mais l'utilisation d'un objet pour chaque élément est un peu excessif, surtout si il ya beaucoup d'entre eux et ils sont de petite taille, comme le stockage des numéros de
• Retard de changement de tableaux - Elle consiste à associer un indice de la matrice. Lorsqu'un élément est retiré, l'indice va de l'avant. Lorsque l'indice atteint le milieu du tableau, le tableau est coupé en deux pour retirer le premier semestre.

Retardé maj tableaux sont la solution la plus satisfaisante dans mon esprit, mais ils continuent à stocker le tout dans un grand contiguë tableau qui peut être problématique, et l'application va s'échelonner lorsque le tableau est coupé en tranches.

J'ai fait une mise en œuvre à l'aide d'une des listes liées de petits tableaux (les éléments de 1000 max chacun). Les tableaux se comportent comme des retardés maj tableaux, sauf qu'ils ne sont jamais tranché: lors de chaque élément du tableau est supprimé, l'ensemble est tout simplement ignorée.

Le paquet est sur ngp avec basic FIFO fonctionnalité, j'ai juste poussé récemment. Le code est divisé en deux parties.

Voici la première partie

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

Et voici le principal Queue classe:

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

Annotations de Type (: X) peut facilement être enlevé pour obtenir ES6 code javascript.

Si vous êtes à la recherche pour ES6 de la programmation orientée objet la mise en œuvre de la Pile et File d'attente de la structure des données avec quelques opérations de base (basé sur les listes chaînées), alors il pourrait ressembler à ceci:

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

Et LinkedList de mise en œuvre qui est utilisé pour la Pile et File d'attente dans les exemples ci-dessus peuvent être trouvés sur GitHub ici.

Ce qui concerne,

En Javascript la mise en œuvre de piles et files d'attente est comme suit:

Pile: Une pile est un conteneur d'objets qui sont insérés et retirés selon le dernier entré, premier sorti (LIFO) principe.

• Push: Méthode ajoute un ou plusieurs éléments à la fin d'un tableau et renvoie la nouvelle longueur du tableau.
• Pop: Méthode supprime le dernier élément d'un tableau et renvoie cet élément.

File d'attente: Une file d'attente est un conteneur d'objets (un linéaire de la collection) qui sont insérés et retirés en fonction du premier entré, premier sorti (FIFO) principe.

• Unshift: Méthode ajoute un ou plusieurs éléments au début d'un tableau.

• Maj: Méthode supprime le premier élément d'un tableau.

JS:

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

Voici ma mise en Œuvre de Piles.

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

vous pouvez utiliser WeakMaps pour la mise en œuvre de la propriété privée dans l'ES6 classe et les avantages de la Chaîne de propriétés et de méthodes dans le langage JavaScript, comme ci-dessous:

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