What is the best way to implement a Stack and a Queue in JavaScript?
I'm looking to do the shunting-yard algorithm and I'm going to need these data-structures.
This question is related to
javascript
data-structures
stack
queue
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]
/*------------------------------------------------------------------
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))
Javascript array shift() is slow especially when holding many elements. I know two ways to implement queue with amortized O(1) complexity.
First is by using circular buffer and table doubling. I have implemented this before. You can see my source code here https://github.com/kevyuu/rapid-queue
The second way is by using two stack. This is the code for queue with two 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;}
This is performance comparison using jsPerf
CircularQueue.shift() vs Array.shift()
http://jsperf.com/rapidqueue-shift-vs-array-shift
As you can see it is significantly faster with large dataset
Here is a fairly simple queue implementation with two aims:
The stack implementation shares the second aim only.
// 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; };
Regards,
In Javascript the implementation of stacks and queues is as follows:
Stack: A stack is a container of objects that are inserted and removed according to the last-in-first-out (LIFO) principle.
Queue: A queue is a container of objects (a linear collection) that are inserted and removed according to the first-in-first-out (FIFO) principle.
Unshift: Method adds one or more elements to the beginning of an array.
Shift: The method removes the first element from an array.
let stack = [];_x000D_
stack.push(1);//[1]_x000D_
stack.push(2);//[1,2]_x000D_
stack.push(3);//[1,2,3]_x000D_
_x000D_
console.log('It was inserted 1,2,3 in stack:', ...stack);_x000D_
_x000D_
stack.pop(); //[1,2]_x000D_
console.log('Item 3 was removed:', ...stack);_x000D_
_x000D_
stack.pop(); //[1]_x000D_
console.log('Item 2 was removed:', ...stack);_x000D_
_x000D_
_x000D_
let queue = [];_x000D_
queue.push(1);//[1]_x000D_
queue.push(2);//[1,2]_x000D_
queue.push(3);//[1,2,3]_x000D_
_x000D_
console.log('It was inserted 1,2,3 in queue:', ...queue);_x000D_
_x000D_
queue.shift();// [2,3]_x000D_
console.log('Item 1 was removed:', ...queue);_x000D_
_x000D_
queue.shift();// [3]_x000D_
console.log('Item 2 was removed:', ...queue);you can use WeakMaps for implementing private property in ES6 class and benefits of String propeties and methods in JavaScript language like below:
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
Or else you can use two arrays to implement queue data structure.
var temp_stack = new Array();
var stack = new Array();
temp_stack.push(1);
temp_stack.push(2);
temp_stack.push(3);
If I pop the elements now then the output will be 3,2,1. But we want FIFO structure so you can do the following.
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
Here is my Implementation of Stacks.
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());
If you wanted to make your own data structures, you could build your own:
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;
};
And for queue:
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;
};
Seems to me that the built in array is fine for a stack. If you want a Queue in TypeScript here is an implementation
/**
* A Typescript implementation of a queue.
*/
export default class Queue {
private queue = [];
private offset = 0;
constructor(array = []) {
// Init the queue using the contents of the array
for (const item of array) {
this.enqueue(item);
}
}
/**
* @returns {number} the length of the queue.
*/
public getLength(): number {
return (this.queue.length - this.offset);
}
/**
* @returns {boolean} true if the queue is empty, and false otherwise.
*/
public isEmpty(): boolean {
return (this.queue.length === 0);
}
/**
* Enqueues the specified item.
*
* @param item - the item to enqueue
*/
public enqueue(item) {
this.queue.push(item);
}
/**
* Dequeues an item and returns it. If the queue is empty, the value
* {@code null} is returned.
*
* @returns {any}
*/
public dequeue(): any {
// if the queue is empty, return immediately
if (this.queue.length === 0) {
return null;
}
// store the item at the front of the queue
const item = this.queue[this.offset];
// increment the offset and remove the free space if necessary
if (++this.offset * 2 >= this.queue.length) {
this.queue = this.queue.slice(this.offset);
this.offset = 0;
}
// return the dequeued item
return item;
};
/**
* Returns the item at the front of the queue (without dequeuing it).
* If the queue is empty then {@code null} is returned.
*
* @returns {any}
*/
public peek(): any {
return (this.queue.length > 0 ? this.queue[this.offset] : null);
}
}
And here is a Jest test for it
it('Queue', () => {
const queue = new Queue();
expect(queue.getLength()).toBe(0);
expect(queue.peek()).toBeNull();
expect(queue.dequeue()).toBeNull();
queue.enqueue(1);
expect(queue.getLength()).toBe(1);
queue.enqueue(2);
expect(queue.getLength()).toBe(2);
queue.enqueue(3);
expect(queue.getLength()).toBe(3);
expect(queue.peek()).toBe(1);
expect(queue.getLength()).toBe(3);
expect(queue.dequeue()).toBe(1);
expect(queue.getLength()).toBe(2);
expect(queue.peek()).toBe(2);
expect(queue.getLength()).toBe(2);
expect(queue.dequeue()).toBe(2);
expect(queue.getLength()).toBe(1);
expect(queue.peek()).toBe(3);
expect(queue.getLength()).toBe(1);
expect(queue.dequeue()).toBe(3);
expect(queue.getLength()).toBe(0);
expect(queue.peek()).toBeNull();
expect(queue.dequeue()).toBeNull();
});
Hope someone finds this useful,
Cheers,
Stu
If you understand stacks with push() and pop() functions, then queue is just to make one of these operations in the oposite sense. Oposite of push() is unshift() and oposite of pop() es shift(). Then:
//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
Javascript has push and pop methods, which operate on ordinary Javascript array objects.
For queues, look here:
http://safalra.com/web-design/javascript/queues/
Queues can be implemented in JavaScript using either the push and shift methods or unshift and pop methods of the array object. Although this is a simple way to implement queues, it is very inefficient for large queues — because of the methods operate on arrays, the shift and unshift methods move every element in the array each time they are called.
Queue.js is a simple and efficient queue implementation for JavaScript whose dequeue function runs in amortized constant time. As a result, for larger queues, it can be significantly faster than using arrays.
There are quite a few ways in which you can implement Stacks and Queues in Javascript. Most of the answers above are quite shallow implementations and I would try to implement something more readable (using new syntax features of es6) and robust.
Here's the stack implementation:
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;
}
}
And this is how you can use the 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
If you would like to see the detailed description about this implementation and how it can be further improved, you can read here : http://jschap.com/data-structures-in-javascript-stack/
Here's the code for queue implementation 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
}
}
Here's how you can use this implementation:
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
To go through the complete tutorial of how these data structures have been implemented and how can these further be improved, you may want to go through the 'Playing with data structures in javascript' series at jschap.com . Here's the links for queues - http://jschap.com/playing-data-structures-javascript-queues/
My implementation of Stack and Queue using Linked List
// Linked List_x000D_
function Node(data) {_x000D_
this.data = data;_x000D_
this.next = null;_x000D_
}_x000D_
_x000D_
// Stack implemented using LinkedList_x000D_
function Stack() {_x000D_
this.top = null;_x000D_
}_x000D_
_x000D_
Stack.prototype.push = function(data) {_x000D_
var newNode = new Node(data);_x000D_
_x000D_
newNode.next = this.top; //Special attention_x000D_
this.top = newNode;_x000D_
}_x000D_
_x000D_
Stack.prototype.pop = function() {_x000D_
if (this.top !== null) {_x000D_
var topItem = this.top.data;_x000D_
this.top = this.top.next;_x000D_
return topItem;_x000D_
}_x000D_
return null;_x000D_
}_x000D_
_x000D_
Stack.prototype.print = function() {_x000D_
var curr = this.top;_x000D_
while (curr) {_x000D_
console.log(curr.data);_x000D_
curr = curr.next;_x000D_
}_x000D_
}_x000D_
_x000D_
// var stack = new Stack();_x000D_
// stack.push(3);_x000D_
// stack.push(5);_x000D_
// stack.push(7);_x000D_
// stack.print();_x000D_
_x000D_
// Queue implemented using LinkedList_x000D_
function Queue() {_x000D_
this.head = null;_x000D_
this.tail = null;_x000D_
}_x000D_
_x000D_
Queue.prototype.enqueue = function(data) {_x000D_
var newNode = new Node(data);_x000D_
_x000D_
if (this.head === null) {_x000D_
this.head = newNode;_x000D_
this.tail = newNode;_x000D_
} else {_x000D_
this.tail.next = newNode;_x000D_
this.tail = newNode;_x000D_
}_x000D_
}_x000D_
_x000D_
Queue.prototype.dequeue = function() {_x000D_
var newNode;_x000D_
if (this.head !== null) {_x000D_
newNode = this.head.data;_x000D_
this.head = this.head.next;_x000D_
}_x000D_
return newNode;_x000D_
}_x000D_
_x000D_
Queue.prototype.print = function() {_x000D_
var curr = this.head;_x000D_
while (curr) {_x000D_
console.log(curr.data);_x000D_
curr = curr.next;_x000D_
}_x000D_
}_x000D_
_x000D_
var queue = new Queue();_x000D_
queue.enqueue(3);_x000D_
queue.enqueue(5);_x000D_
queue.enqueue(7);_x000D_
queue.print();_x000D_
queue.dequeue();_x000D_
queue.dequeue();_x000D_
queue.print();Construct a Queue using two Stacks.
O(1) for both enqueue and dequeue operations.
class Queue {
constructor() {
this.s1 = []; // in
this.s2 = []; // out
}
enqueue(val) {
this.s1.push(val);
}
dequeue() {
if (this.s2.length === 0) {
this._move();
}
return this.s2.pop(); // return undefined if empty
}
_move() {
while (this.s1.length) {
this.s2.push(this.s1.pop());
}
}
}
A little late answer but i think this answer should be here. Here is an implementation of Queue with O(1) enqueue and O(1) dequeue using the sparse Array powers.
Sparse Arrays in JS are mostly disregarded but they are in fact a gem and we should put their power in use at some critical tasks.
So here is a skeleton Queue implementation which extends the Array type and does it's things in O(1) all the way.
class Queue extends Array {
constructor(){
super()
Object.defineProperty(this,"head",{ value : 0
, writable : true
, enumerable : false
, configurable: false
});
}
enqueue(x) {
this.push(x);
return this;
}
dequeue() {
var first;
return this.head < this.length ? ( first = this[this.head]
, delete this[this.head++]
, first
)
: void 0; // perfect undefined
}
peek() {
return this[this.head];
}
}
var q = new Queue();
console.log(q.dequeue()); // doesn't break
console.log(q.enqueue(10)); // add 10
console.log(q.enqueue("DIO")); // add "DIO" (Last In Line cCc R.J.DIO reis cCc)
console.log(q); // display q
console.log(q.dequeue()); // lets get the first one in the line
console.log(q.dequeue()); // lets get DIO out from the line.as-console-wrapper {
max-height: 100% !important;
}So do we have a potential memory leak here? No i don't think so. JS sparse arrays are non contiguous. Accordingly deleted items shouln't be a part of the array's memory footprint. Let the GC do it's job for you. It's free of charge.
One potential problem is that, the length property grows indefinitely as you keep enqueueing items to the queue. However still one may implement an auto refreshing (condensing) mechanism to kick in once the length reaches to a certain value.
If you're looking for ES6 OOP implementation of Stack and Queue data-structure with some basic operations (based on linked lists) then it may look like this:
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);
}
}
And LinkedList implementation that is used for Stack and Queue in examples above may be found on GitHub here.
Arrays.
Stack:
var stack = [];
//put value on top of stack
stack.push(1);
//remove value from top of stack
var value = stack.pop();
Queue:
var queue = [];
//put value on end of queue
queue.push(1);
//Take first value from queue
var value = queue.shift();
Here is the linked list version of a queue that also includes the last node, as suggested by @perkins and as is most appropriate.
// 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;
};
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;
}
}
Create a pair of classes that provide the various methods that each of these data structures has (push, pop, peek, etc). Now implement the methods. If you're familiar with the concepts behind stack/queue, this should be pretty straightforward. You can implement the stack with an array, and a queue with a linked list, although there are certainly other ways to go about it. Javascript will make this easy, because it is weakly typed, so you don't even have to worry about generic types, which you'd have to do if you were implementing it in Java or C#.
You can use your own customize class based on the concept, here the code snippet which you can use to do the stuff
/*
* 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;
}
}
}
and to check this use your console and try these line one by one.
>> var st = new Stack();
>> st.push("BP");
>> st.push("NK");
>> st.getTop();
>> st.getCount();
>> st.displayAll();
>> st.pop();
>> st.displayAll();
>> st.getTop();
>> st.peek();
The stack implementation is trivial as explained in the other answers.
However, I didn't find any satisfactory answers in this thread for implementing a queue in javascript, so I made my own.
There are three types of solutions in this thread:
array.shift() on a large array is very inefficient.Delayed shift arrays are the most satisfactory solution in my mind, but they still store everything in one large contiguous array which can be problematic, and the application will stagger when the array is sliced.
I made an implementation using linked lists of small arrays (1000 elements max each). The arrays behave like delayed shift arrays, except they are never sliced: when every element in the array is removed, the array is simply discarded.
The package is on npm with basic FIFO functionality, I just pushed it recently. The code is split into two parts.
Here is the first part
/** 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;
}
And here is the main Queue class:
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;
}
Type annotations (: X) can easily be removed to obtain ES6 javascript code.
The regular Array structure in Javascript is a Stack (first in, last out) and can also be used as a Queue (first in, first out) depending on the calls you make.
Check this link to see how to make an Array act like a Queue:
Source: Stackoverflow.com