Grokking Algorithm Complexity and Big-O
Ask Author
Back to course home

0% completed

Vote For New Content
Stack and Queue
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Stacks and Queues are fundamental data structures that allow insertion and deletion of elements in a specific order. A Stack follows a Last In, First Out (LIFO) order, where the last element added is the first to be removed. A Queue follows a First In, First Out (FIFO) order, where the first element added is the first to be removed.

Key Characteristics of Stack and Queue

Stack

Image
  • LIFO: Last element added is the first to be removed.
  • Common operations: push (add) and pop (remove).
  • Examples: Call stack in programming, undo mechanisms in text editors.

Queue

Image
  • FIFO: First element added is the first to be removed.
  • Common operations: enqueue (add) and dequeue (remove).
  • Examples: Task scheduling, handling requests in order, printer queue.

Basic Operations On Stack

Python3
Python3
. . . .

Time Complexity Analysis for Stack

Image
  • Push: O(1) – Adding an element involves updating the top pointer.
  • Pop: O(1) – Removing the top element only updates the pointer.
  • Peek: O(1) – Accessing the top element is immediate.
  • Search: O(n) – Linear search required.
  • Access by Index: O(n) – Traversal required.
  • is_empty: O(1) – Direct check.

Basic Operations on Queue

Python3
Python3
. . . .

Time Complexity Analysis for Queue

Image
  • Enqueue: O(1) – Adding an element at the end is straightforward.
  • Dequeue: O(1) – Removing the front element is constant time.
  • Front (Peek): O(1) – Accessing the front element without modification is immediate.
  • Search: O(n) – Linear search is required for finding an element.
  • Access by Index: O(n) – Traversal needed to reach the element.
  • is_empty: O(1) – Direct check.

Space Complexity for Stack and Queue

Both stacks and queues have a space complexity of O(n), where n is the number of elements in the structure. Each element occupies constant space, and the overall space usage grows linearly with the number of elements.

  • Space Complexity: O(n), as each element added to the stack or queue requires additional memory.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible