Stacks & Queues

Links To Code:

// Stacks & Queues - Greg Hogg DSA Course Materials Lecture 5

#include <iostream>
#include <stack>
#include <deque>

int main() {
    // Stacks - Last in First Out (LIFO)

    std::stack<int> stk;
    std::cout << "Initial Stack: empty" << std::endl;

    // Append to top of stack - O(1)
    stk.push(5);
    stk.push(4);
    stk.push(3);
    std::cout << "Stack after pushing elements: [5, 4, 3]" << std::endl;

    // Pop from stack - O(1)
    int x = stk.top();
    stk.pop();
    std::cout << "Popped element: " << x << std::endl;
    std::cout << "Stack after popping: [5, 4]" << std::endl;

    // Ask what's on the top of stack - O(1)
    std::cout << "Top element of stack: " << stk.top() << std::endl;

    // Ask if something is in the stack - O(1)
    if (!stk.empty()) {
        std::cout << "Stack is not empty" << std::endl;
    }

    // Queues - First in First out (FIFO)

    std::deque<int> q;
    std::cout << "Initial Queue: empty" << std::endl;

    // Enqueue - Add element to the right - O(1)
    q.push_back(5);
    q.push_back(6);
    q.push_back(7);
    std::cout << "Queue after enqueuing elements: [5, 6, 7]" << std::endl;

    // Dequeue (pop left) - Remove element from the left - O(1)
    q.pop_front();
    std::cout << "Queue after dequeueing: [6, 7]" << std::endl;

    // Peek from left side - O(1)
    std::cout << "Front element of queue: " << q.front() << std::endl;

    // Peek from right side - O(1)
    std::cout << "Rear element of queue: " << q.back() << std::endl;

    return 0;
}

// Stacks & Queues - Greg Hogg DSA Course Materials Lecture 5

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        // Stacks - Last in First Out (Lifo)

        Stack<Integer> stk = new Stack<>();
        System.out.println("Initial Stack: " + stk); // Output: []

        // Append to top of stack - O(1)
        stk.push(5);
        stk.push(4);
        stk.push(3);
        System.out.println("Stack after pushing elements: " + stk); // Output: [5, 4, 3]

        // Pop from stack - O(1)
        int x = stk.pop();
        System.out.println("Popped element: " + x); // Output: 3
        System.out.println("Stack after popping: " + stk); // Output: [5, 4]

        // Ask what's on the top of stack - O(1)
        System.out.println("Top element of stack: " + stk.peek()); // Output: 4

        // Ask if something is in the stack - O(1)
        if (!stk.isEmpty()) {
            System.out.println("Stack is not empty"); // Output: true
        }

        // Queues - First in First out (Fifo)

        Deque<Integer> q = new LinkedList<>();
        System.out.println("Initial Queue: " + q); // Output: []

        // Enqueue - Add element to the right - O(1)
        q.add(5);
        q.add(6);
        q.add(7);
        System.out.println("Queue after enqueuing elements: " + q); // Output: [5, 6, 7]

        // Dequeue (pop left) - Remove element from the left - O(1)
        q.removeFirst();
        System.out.println("Queue after dequeueing: " + q); // Output: [6, 7]

        // Peek from left side - O(1)
        System.out.println("Front element of queue: " + q.peekFirst()); // Output: 6

        // Peek from right side - O(1)
        System.out.println("Rear element of queue: " + q.peekLast()); // Output: 7
    }
}

// Stacks & Queues - Greg Hogg DSA Course Materials Lecture 5

// Stacks - Last in First Out (LIFO)
let stack = [];
console.log("Initial Stack: ", stack); // Output: []

// Append to top of stack - O(1)
stack.push(5);
stack.push(4);
stack.push(3);
console.log("Stack after pushing elements: ", stack); // Output: [5, 4, 3]

// Pop from stack - O(1)
let x = stack.pop();
console.log("Popped element: ", x); // Output: 3
console.log("Stack after popping: ", stack); // Output: [5, 4]

// Ask what's on the top of stack - O(1)
console.log("Top element of stack: ", stack[stack.length - 1]); // Output: 4

// Check if stack is not empty - O(1)
if (stack.length > 0) {
    console.log("Stack is not empty"); // Output: true
}

// Queues - First in First out (FIFO)
let queue = [];
console.log("Initial Queue: ", queue); // Output: []

// Enqueue - Add element to the right - O(1)
queue.push(5);
queue.push(6);
queue.push(7);
console.log("Queue after enqueuing elements: ", queue); // Output: [5, 6, 7]

// Dequeue (pop left) - Remove element from the left - O(1)
queue.shift();
console.log("Queue after dequeueing: ", queue); // Output: [6, 7]

// Peek from front - O(1)
console.log("Front element of queue: ", queue[0]); // Output: 6

// Peek from rear - O(1)
console.log("Rear element of queue: ", queue[queue.length - 1]); // Output: 7

Summary

Stacks follow a Last-In-First-Out (LIFO) order and are ideal for backtracking, expression parsing, and undo operations. Queues follow a First-In-First-Out (FIFO) order and are used in scheduling, level-order traversal, and buffering. Understanding these structures lays the groundwork for managing order-dependent workflows and stream processing in algorithms.

Stacks & Queues

Stacks and queues are fundamental linear data structures that manage the order in which elements are processed. Their simple behavior makes them incredibly useful for modeling real-world processes.

Stacks (LIFO)

A stack processes elements in a Last-In-First-Out manner. The most recently added item is the first to be removed. This behavior is useful in recursive algorithms, function call tracking, and problems like balancing parentheses or reversing data.

Queues (FIFO)

A queue processes elements in a First-In-First-Out order, like a line at a store. Queues are great for handling asynchronous tasks, traversing graphs (BFS), and managing resources in order of request.

Common Operations

Push / Enqueue: Add an element to the structure.
Pop / Dequeue: Remove the most recent (stack) or earliest (queue) element.
Peek: Inspect the element at the front or top without removing it.

Conclusion

Though simple, stacks and queues underpin many powerful algorithms and systems. Knowing when and how to use them effectively will streamline your problem-solving toolkit.

Stacks and Queues in Python - Data Structures and Algorithms (DSA)

In this lesson, we explore two fundamental data structures in DSA (Data Structures and Algorithms): Stacks and Queues. Understanding these structures is essential for efficient algorithm design, especially when solving problems involving order-sensitive data processing.

Stacks: LIFO Data Structure

A Stack follows the LIFO (Last In, First Out) principle. The most recently added item is the first to be removed. This behavior is similar to stacking books or plates: the last item placed is the first one you take off.

Common Stack Operations

Append (Push): Adds an element to the top of the stack.
Pop: Removes and returns the top element of the stack.
Peek: Returns the top element without removing it.
Is Empty: Checks whether the stack is empty.

Stack Implementation in Python

Stacks in Python are commonly implemented using dynamic arrays, specifically Python’s built-in list type. This is because append() and pop() from the end of a list both run in constant time, or O(1) time complexity.

Alternatively, linked lists can be used to implement stacks, especially when frequent insertions and deletions are involved.

Time Complexity of Stack Operations

Append (Push): O(1)
Pop: O(1)
Peek: O(1)
Is Empty: O(1)

Queues: FIFO Data Structure

A Queue operates on the FIFO (First In, First Out) principle. The first element added is the first one removed. This is similar to a line of people waiting their turn — the person at the front goes first.

Common Queue Operations

Enqueue: Adds an element to the end of the queue.
Dequeue: Removes and returns the front element.
Peek: Returns the front element without removing it.
Is Empty: Checks if the queue is empty.

Queue Implementation in Python

Using a dynamic array like Python’s list for queues is inefficient for dequeue() operations, since removing the first element requires shifting all other elements, leading to O(n) time complexity.

Instead, Python’s collections.deque (double-ended queue) is preferred for queue implementation. It provides O(1) time complexity for both enqueue and dequeue operations.

Alternatively, a singly or doubly linked list can also be used to achieve efficient O(1) queue operations.

Time Complexity of Queue Operations (using deque)

Enqueue: O(1)
Dequeue: O(1)
Peek: O(1)
Is Empty: O(1)

Comparison: Stack vs Queue

Feature	Stack	Queue
Order	LIFO (Last In, First Out)	FIFO (First In, First Out)
Main Operations	Push, Pop, Peek, Is Empty	Enqueue, Dequeue, Peek, Is Empty
Python Implementation	List (Dynamic Array)	collections.deque or Linked List
Average Time Complexity	O(1)	O(1)

Versatility and Use Cases

Both Stacks and Queues can store elements of any data type, such as integers, strings, or custom objects.

Common applications of Stacks include:

Function call stacks
Undo operations in text editors
Expression evaluation and parsing

Typical uses for Queues include:

Task scheduling
Breadth-first search (BFS) in graphs
Print job management

Conclusion

Understanding the implementation and time complexity of Stacks and Queues is foundational in computer science. With Python, developers have simple yet powerful tools like list and collections.deque to build these structures efficiently. Whether working on algorithms, system design, or real-world applications, mastering these data structures is key.

Get Personalized Lessons at AlgoMap Bootcamp 💡