Stacks and Queues Explained
September 7, 202512 min read
Stack: A linear data structure following LIFO (Last In First Out) principle. The last element added is the first one to be removed.
Queue: A linear data structure following FIFO (First In First Out) principle. The first element added is the first one to be removed.
Visual Representation
Operations Complexity
Stack Implementation
1. Array-based Stack
class ArrayStack {
constructor(capacity = 10) {
this.items = new Array(capacity);
this.capacity = capacity;
this.top = -1;
}
// O(1) - Push element
push(element) {
if (this.isFull()) {
throw new Error("Stack Overflow");
}
this.items[++this.top] = element;
}
// O(1) - Pop element
pop() {
if (this.isEmpty()) {
throw new Error("Stack Underflow");
}
const element = this.items[this.top];
this.top--;
return element;
}
// O(1) - Peek top element
peek() {
if (this.isEmpty()) return null;
return this.items[this.top];
}
// O(1) - Check if empty
isEmpty() {
return this.top === -1;
}
// O(1) - Check if full
isFull() {
return this.top === this.capacity - 1;
}
// O(1) - Get size
size() {
return this.top + 1;
}
}
2. Linked List-based Stack
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedStack {
constructor() {
this.top = null;
this.size = 0;
}
// O(1) - Push element
push(element) {
const node = new Node(element);
node.next = this.top;
this.top = node;
this.size++;
}
// O(1) - Pop element
pop() {
if (this.isEmpty()) {
throw new Error("Stack Underflow");
}
const element = this.top.data;
this.top = this.top.next;
this.size--;
return element;
}
// O(1) - Peek top element
peek() {
if (this.isEmpty()) return null;
return this.top.data;
}
// O(1) - Check if empty
isEmpty() {
return this.top === null;
}
// O(1) - Get size
getSize() {
return this.size;
}
}
3. Dynamic Array Stack
class DynamicStack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element); // O(1) amortized
}
pop() {
if (this.isEmpty()) {
throw new Error("Stack Underflow");
}
return this.items.pop(); // O(1)
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
}
Queue Implementation
1. Array-based Queue (Circular)
class CircularQueue {
constructor(capacity = 10) {
this.items = new Array(capacity);
this.capacity = capacity;
this.front = -1;
this.rear = -1;
this.size = 0;
}
// O(1) - Add element to rear
enqueue(element) {
if (this.isFull()) {
throw new Error("Queue Overflow");
}
if (this.isEmpty()) {
this.front = 0;
}
this.rear = (this.rear + 1) % this.capacity;
this.items[this.rear] = element;
this.size++;
}
// O(1) - Remove element from front
dequeue() {
if (this.isEmpty()) {
throw new Error("Queue Underflow");
}
const element = this.items[this.front];
if (this.front === this.rear) {
// Queue has only one element
this.front = -1;
this.rear = -1;
} else {
this.front = (this.front + 1) % this.capacity;
}
this.size--;
return element;
}
// O(1) - Get front element
getFront() {
if (this.isEmpty()) return null;
return this.items[this.front];
}
// O(1) - Get rear element
getRear() {
if (this.isEmpty()) return null;
return this.items[this.rear];
}
isEmpty() {
return this.size === 0;
}
isFull() {
return this.size === this.capacity;
}
}
2. Linked List-based Queue
class LinkedQueue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
// O(1) - Add element to rear
enqueue(element) {
const node = new Node(element);
if (this.isEmpty()) {
this.front = node;
this.rear = node;
} else {
this.rear.next = node;
this.rear = node;
}
this.size++;
}
// O(1) - Remove element from front
dequeue() {
if (this.isEmpty()) {
throw new Error("Queue Underflow");
}
const element = this.front.data;
this.front = this.front.next;
if (!this.front) {
this.rear = null;
}
this.size--;
return element;
}
getFront() {
return this.front ? this.front.data : null;
}
getRear() {
return this.rear ? this.rear.data : null;
}
isEmpty() {
return this.front === null;
}
}
Special Queue Types
Deque (Double-Ended Queue)
class Deque {
constructor() {
this.items = [];
}
// O(1) - Add to front
addFront(element) {
this.items.unshift(element);
}
// O(1) - Add to rear
addRear(element) {
this.items.push(element);
}
// O(1) - Remove from front
removeFront() {
if (this.isEmpty()) return null;
return this.items.shift();
}
// O(1) - Remove from rear
removeRear() {
if (this.isEmpty()) return null;
return this.items.pop();
}
getFront() {
return this.items[0];
}
getRear() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
}
Stack Applications
1. Balanced Parentheses
function isBalanced(str) {
const stack = [];
const pairs = {
'(': ')',
'{': '}',
'[': ']'
};
for (let char of str) {
if (char in pairs) {
stack.push(char);
} else if (Object.values(pairs).includes(char)) {
if (stack.length === 0) return false;
const last = stack.pop();
if (pairs[last] !== char) return false;
}
}
return stack.length === 0;
}
2. Expression Evaluation
function infixToPostfix(expression) {
const precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3};
const stack = [];
let postfix = '';
for (let char of expression) {
if (/[a-zA-Z0-9]/.test(char)) {
postfix += char;
} else if (char === '(') {
stack.push(char);
} else if (char === ')') {
while (stack.length && stack[stack.length - 1] !== '(') {
postfix += stack.pop();
}
stack.pop(); // Remove '('
} else if (char in precedence) {
while (stack.length &&
precedence[stack[stack.length - 1]] >= precedence[char]) {
postfix += stack.pop();
}
stack.push(char);
}
}
while (stack.length) {
postfix += stack.pop();
}
return postfix;
}
function evaluatePostfix(postfix) {
const stack = [];
for (let char of postfix) {
if (/\d/.test(char)) {
stack.push(parseInt(char));
} else {
const b = stack.pop();
const a = stack.pop();
switch(char) {
case '+': stack.push(a + b); break;
case '-': stack.push(a - b); break;
case '*': stack.push(a * b); break;
case '/': stack.push(Math.floor(a / b)); break;
}
}
}
return stack[0];
}
3. Function Call Stack
Queue Applications
1. BFS (Breadth-First Search)
function bfs(graph, start) {
const visited = new Set();
const queue = [start];
const result = [];
visited.add(start);
while (queue.length > 0) {
const node = queue.shift();
result.push(node);
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
return result;
}
2. Level Order Traversal
function levelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
currentLevel.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(currentLevel);
}
return result;
}
Monotonic Stack/Queue
// Next Greater Element
function nextGreaterElement(arr) {
const n = arr.length;
const result = new Array(n).fill(-1);
const stack = [];
for (let i = 0; i < n; i++) {
while (stack.length && arr[stack[stack.length - 1]] < arr[i]) {
const idx = stack.pop();
result[idx] = arr[i];
}
stack.push(i);
}
return result;
}
// Sliding Window Maximum using Deque
function maxSlidingWindow(nums, k) {
const deque = [];
const result = [];
for (let i = 0; i < nums.length; i++) {
// Remove elements outside window
while (deque.length && deque[0] <= i - k) {
deque.shift();
}
// Maintain decreasing order
while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
deque.pop();
}
deque.push(i);
if (i >= k - 1) {
result.push(nums[deque[0]]);
}
}
return result;
}
Priority Queue
class PriorityQueue {
constructor(compareFn = (a, b) => a < b) {
this.heap = [];
this.compare = compareFn;
}
enqueue(element, priority) {
const node = { element, priority };
this.heap.push(node);
this.bubbleUp(this.heap.length - 1);
}
dequeue() {
if (this.isEmpty()) return null;
const min = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this.bubbleDown(0);
}
return min.element;
}
bubbleUp(index) {
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.compare(this.heap[index].priority,
this.heap[parentIndex].priority)) {
[this.heap[index], this.heap[parentIndex]] =
[this.heap[parentIndex], this.heap[index]];
index = parentIndex;
} else {
break;
}
}
}
bubbleDown(index) {
while (true) {
let minIndex = index;
const leftChild = 2 * index + 1;
const rightChild = 2 * index + 2;
if (leftChild < this.heap.length &&
this.compare(this.heap[leftChild].priority,
this.heap[minIndex].priority)) {
minIndex = leftChild;
}
if (rightChild < this.heap.length &&
this.compare(this.heap[rightChild].priority,
this.heap[minIndex].priority)) {
minIndex = rightChild;
}
if (minIndex !== index) {
[this.heap[index], this.heap[minIndex]] =
[this.heap[minIndex], this.heap[index]];
index = minIndex;
} else {
break;
}
}
}
isEmpty() {
return this.heap.length === 0;
}
}
Real-World Applications
Implementation Comparison
Common Interview Problems
Stack Problems
Queue Problems
Advanced Patterns
1. Stack with Min/Max in O(1)
class MinStack {
constructor() {
this.stack = [];
this.minStack = [];
}
push(val) {
this.stack.push(val);
if (this.minStack.length === 0 ||
val <= this.minStack[this.minStack.length - 1]) {
this.minStack.push(val);
}
}
pop() {
const val = this.stack.pop();
if (val === this.minStack[this.minStack.length - 1]) {
this.minStack.pop();
}
return val;
}
top() {
return this.stack[this.stack.length - 1];
}
getMin() {
return this.minStack[this.minStack.length - 1];
}
}
2. Queue using Two Stacks
class QueueUsingStacks {
constructor() {
this.stack1 = []; // For enqueue
this.stack2 = []; // For dequeue
}
enqueue(x) {
this.stack1.push(x);
}
dequeue() {
if (this.stack2.length === 0) {
while (this.stack1.length > 0) {
this.stack2.push(this.stack1.pop());
}
}
if (this.stack2.length === 0) {
throw new Error("Queue is empty");
}
return this.stack2.pop();
}
peek() {
if (this.stack2.length === 0) {
while (this.stack1.length > 0) {
this.stack2.push(this.stack1.pop());
}
}
return this.stack2[this.stack2.length - 1];
}
}
3. Circular Buffer
class CircularBuffer {
constructor(capacity) {
this.buffer = new Array(capacity);
this.capacity = capacity;
this.writePos = 0;
this.readPos = 0;
this.size = 0;
}
write(data) {
if (this.size === this.capacity) {
// Overwrite oldest data
this.readPos = (this.readPos + 1) % this.capacity;
} else {
this.size++;
}
this.buffer[this.writePos] = data;
this.writePos = (this.writePos + 1) % this.capacity;
}
read() {
if (this.size === 0) return null;
const data = this.buffer[this.readPos];
this.readPos = (this.readPos + 1) % this.capacity;
this.size--;
return data;
}
isFull() {
return this.size === this.capacity;
}
isEmpty() {
return this.size === 0;
}
}