Stacks and Queues are two basic data structures that have many practical applications in software development
What is a Stack
A stack is a collection of items that supports only two operations: the push operation and the pop operation. A stack is a LIFO (Last In First Out) data structure which means that the last item pushed into a stack must be the first item popped from the stack.
Usually, the push and pop operations of a typical stack data structure are constant time operations denoted by O(1) irrespective of the size of the stack.
There is no Stack object available in JavaScript out of the box but a stack can easily be represented by an Array object that only allows push and pop operations.
The push and pop operations of a JavaScript Array are both constant time operations [O(1)] which meets the requirement for a good stack implementation
class Stack {
constructor(items) {
this._items = items;
}
push(newItem) {
this._items.push(newItem);
}
pop() {
return this._items.pop();
}
size() {
return this._items.length;
}
}
const x = new Stack([1, 2, 3]); // stack: [1, 2, 3]
x.pop(); // stack: [1, 2]
x.push(100); // stack: [1, 2, 100]
There are many good use cases for the stack data structure. A simple example is reversing a string
const firstName = "King";
const nameStack = new Stack(firstName.split(""));
let reversedName = "";
for (let i = 0; i < firstName.length; i++) {
reversedName += nameStack.pop();
}
console.log(reversedName); // gniK
JavaScript also uses something called a call stack while executing scripts
More Applications of the Stack data structure
- Browser navigation
- Parsing and Processing Mathematical expressions
What is a Queue
A queue is a collection of items that supports only two operations: the add or enqueue operation and the remove or dequeue operation. Unlike a stack, a queue is a FIFO (First In First Out) data structure which means that the first item added to a queue must be the first item removed from the queue.
Similar to the stack, the add and remove operations of a queue are constant time operations.
There also no Queue object available in JavaScript out of the box but a stack can easily by represented by an Array object that only allows enqueue and dequeue operations
As mentioned earlier, the push operation on a JavaScript Array is a constant time operation which makes it ideal for implementing the enqueue operation for the queue. The shift operation on a JavaScript Array can be used to implement dequeue, however, the shift operation has a linear time complexity [O(n)] and can get slow if the queue grows big enough. A clever work-around is shown below
class Queue {
startPos = 0;
constructor(items) {
this._items = items;
}
enqueue(newItem) {
this._items.push(newItem);
}
dequeue() {
if (this.startPos < this._items.length)
return this._items[this.startPos++];
}
size() {
return this._items.length - this.startPos;
}
}
const x = new Queue([1, 2, 3]); // queue: [1, 2, 3]
x.enqueue(10); // queue: [1, 2, 3, 10]
x.dequeue(); // queue: [2, 3, 10]
x.size(); // 3
x.enqueue(1000); // queue: [2, 3, 10, 1000]
In the above Queue class, the dequeue implementation has a constant time complexity which meets the queue data structure requirement
The queue is widely applied in tackling several programming problems. A simple example for queues is checking for a palindrome
function palindrome(word) {
const wordQueue = new Queue(word.split(""));
for (let i = word.length - 1; i > 0; i--) {
if (word[i] !== wordQueue.dequeue()) return false;
}
return true;
}
palindrome("deed") // true
palindrome("King") // false
palindrome("level") // true
More Applications of the Queue data structure
- Storing a number of computer processes to be executed in order
- SMS messaging
Thanks π for making it to the end π¨βπ» and I really hope you found the content useful.
Top comments (3)
in above example for dequeue, value is not actually getting removed but the starting position changes. is there efficient way to remove the element also.
Unfortunately, there is no out-of-the-box solution in JS - that I know of - to remove an item from the beginning of an array in constant time.
Although the
items
property is not modified by dequeue, thestartPos
property is. So we can say that the queue always begins fromstartPos
yeah, hope so something will come up in future. But this does job pretty