Skip to main content

Stacks and Queues

Stacks and Queues are fundamental linear data structures that follow specific patterns for adding and removing elements.

Stacks​

A stack is a Last-In-First-Out (LIFO) data structure where elements are added and removed from the same end, called the "top" of the stack.

Structure​

class Stack {
	constructor() {
		this.items = [];
		this.length = 0;
	}
}

Visual Representation​

│       │
│   3   │ <- Top
│   2   │
│   1   │
└───────┘

Key Operations​

  1. push(element) - Add to top
  2. pop() - Remove from top
  3. peek() - View top element
  4. isEmpty() - Check if stack is empty
  5. size() - Get number of elements

Implementation​

class Stack {
	constructor() {
		this.items = [];
		this.length = 0;
	}

	push(element) {
		this.items.push(element);
		this.length++;
		return this;
	}

	pop() {
		if (this.isEmpty()) return null;
		this.length--;
		return this.items.pop();
	}

	peek() {
		if (this.isEmpty()) return null;
		return this.items[this.length - 1];
	}

	isEmpty() {
		return this.length === 0;
	}

	size() {
		return this.length;
	}

	clear() {
		this.items = [];
		this.length = 0;
	}
}

Common Use Cases for Stacks​

  1. Function Call Stack

    • Managing function calls in programming languages
    • Recursion tracking

  2. Undo/Redo Operations

    • Text editors
    • Image editing software

  3. Browser History

    • Back/Forward navigation
    • History tracking

  4. Expression Evaluation

    • Parsing arithmetic expressions
    • Bracket matching

Queues​

A queue is a First-In-First-Out (FIFO) data structure where elements are added at the rear and removed from the front.

Structure​

class Queue {
	constructor() {
		this.items = {};
		this.frontIndex = 0;
		this.backIndex = 0;
	}
}

Visual Representation​

Front                 Back
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
└───┴───┴───┴───┘

Key Operations​

  1. enqueue(element) - Add to back
  2. dequeue() - Remove from front
  3. front() - View front element
  4. isEmpty() - Check if queue is empty
  5. size() - Get number of elements

Implementation​

class Queue {
	constructor() {
		this.items = {};
		this.frontIndex = 0;
		this.backIndex = 0;
	}

	enqueue(element) {
		this.items[this.backIndex] = element;
		this.backIndex++;
		return this;
	}

	dequeue() {
		if (this.isEmpty()) return null;

		const item = this.items[this.frontIndex];
		delete this.items[this.frontIndex];
		this.frontIndex++;

		return item;
	}

	front() {
		if (this.isEmpty()) return null;
		return this.items[this.frontIndex];
	}

	isEmpty() {
		return this.frontIndex === this.backIndex;
	}

	size() {
		return this.backIndex - this.frontIndex;
	}

	clear() {
		this.items = {};
		this.frontIndex = 0;
		this.backIndex = 0;
	}
}

Time Complexities​

OperationStackQueue
InsertO(1)O(1)
DeleteO(1)O(1)
AccessO(1)O(1)
SearchO(n)O(n)

Common Use Cases for Queues​

  1. Task Scheduling

    • Print queue
    • Process scheduling
    • Task management

  2. Event Handling

    • Event loops
    • Message processing

  3. BFS Algorithm

    • Graph traversal
    • Tree level-order traversal

  4. Real-time Systems

    • Request processing
    • Buffer management

Variations​

Priority Queue​

A specialized queue where elements have priorities and are dequeued based on their priority.

class PriorityQueue {
	constructor() {
		this.values = [];
	}

	enqueue(element, priority) {
		this.values.push({ element, priority });
		this.sort();
	}

	dequeue() {
		return this.values.shift();
	}

	sort() {
		this.values.sort((a, b) => a.priority - b.priority);
	}
}

Circular Queue​

A fixed-size queue that wraps around to the beginning when it reaches the end.

class CircularQueue {
	constructor(capacity) {
		this.items = new Array(capacity);
		this.capacity = capacity;
		this.currentLength = 0;
		this.front = -1;
		this.rear = -1;
	}

	enqueue(element) {
		if (this.isFull()) return false;

		if (this.isEmpty()) {
			this.front = 0;
		}

		this.rear = (this.rear + 1) % this.capacity;
		this.items[this.rear] = element;
		this.currentLength++;
		return true;
	}

	dequeue() {
		if (this.isEmpty()) return null;

		const item = this.items[this.front];
		this.items[this.front] = null;
		this.front = (this.front + 1) % this.capacity;
		this.currentLength--;

		if (this.isEmpty()) {
			this.front = -1;
			this.rear = -1;
		}

		return item;
	}
}

Practice Problems​

  1. Implement a browser history using a stack
  2. Create a task scheduler using a queue
  3. Validate balanced parentheses using a stack
  4. Implement a printer queue
  5. Design a circular queue with fixed size

Additional Resources​