Implementing Stack, Queue, and Deque Data Structures

Posted on Jun 1, 2025 in Computer Engineering in Computer Engineering

This document provides implementations of three fundamental data structures: Stack, Queue, and Deque. Each data structure is presented with code examples in both Python and C++, demonstrating their core functionalities using linked lists.

Stack Data Structure (LIFO)

A Stack is a Last-In, First-Out (LIFO) data structure. Elements are added and removed from the same end, often referred to as the “top” of the stack.

Python Stack Implementation

The Python implementation uses a simple Node class to build a linked list-based stack.

# Python Node Class for Linked List
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

    def __str__(self):
        return str(self.data)

# Python Stack Class
class Stack:
    def __init__(self):
        self.head = None

    def push(self, data): # Adds a new element to the top
        new = Node(data)
        if self.isEmpty():
            self.head = new
        else:
            new.next = self.head
            self.head = new

    def pop(self): # Returns and removes the top element
        if not self.isEmpty():
            value_to_remove = self.head.data
            self.head = self.head.next
            return value_to_remove
        else:
            print('Stack is empty!') # Consider raising an exception in production code

    def top(self): # Returns the top element's value (PEEK)
        if not self.isEmpty():
            return self.head.data

    def isEmpty(self):
        return self.head is None

    def __str__(self):
        result = '[ '
        current = self.head
        while current is not None:
            result += current.__str__() + " "
            current = current.next
        result += ']'
        return result

C++ Stack Implementation

The C++ implementation uses templates for generic types and manages memory manually.

// C++ Node Class for Linked List
template <typename T>
class Node {
public:
    T value;
    Node* next;

    Node(T val) : value(val), next(nullptr) {}

    // Overload stream insertion operator for Node
    friend std::ostream& operator<<(std::ostream& output, const Node& n) {
        output << n.value;
        return output;
    }
};

// C++ Stack Class
template <typename T>
class Stack {
private:
    Node<T>* head;

public:
    Stack() : head(nullptr) {} // Constructor

    ~Stack() { // Destructor to free memory
        Node<T>* current = head;
        while (current != nullptr) {
            Node<T>* next_node = current->next;
            delete current;
            current = next_node;
        }
        head = nullptr; // Ensure head is null after destruction
    }

    void push(T value) { // Adds a new element to the top
        Node<T>* new_node = new Node<T>(value);
        if (isEmpty()) {
            head = new_node;
        } else {
            new_node->next = head;
            head = new_node;
        }
    }

    T pop() { // Returns and removes the top element
        if (!isEmpty()) {
            Node<T>* node_to_delete = head;
            T value_to_return = node_to_delete->value;
            head = head->next;
            delete node_to_delete;
            return value_to_return;
        }
        // For non-pointer types, returning NULL might be problematic.
        // Consider throwing an exception or using std::optional<T> in modern C++.
        return (T) NULL;
    }

    T top() { // Returns the top element's value (PEEK)
        if (!isEmpty()) {
            return head->value;
        }
        return (T) NULL;
    }

    bool isEmpty() {
        return head == nullptr;
    }

    // Overload stream insertion operator for Stack
    friend std::ostream& operator<<(std::ostream& output, const Stack<T>& s) {
        output << "[";
        if (s.head != nullptr) {
            Node<T>* current = s.head;
            while (current != nullptr) {
                output << (*current);
                if (current->next != nullptr) output << ",";
                current = current->next;
            }
        }
        output << "]";
        return output;
    }
};

Queue Data Structure (FIFO)

A Queue is a First-In, First-Out (FIFO) data structure. Elements are added to one end (the “tail” or “back”) and removed from the other end (the “head” or “front”).

Python Queue Implementation

The Python implementation uses a simple Node class and maintains both head and tail pointers.

# Python Node Class for Linked List
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

    def __str__(self):
        return str(self.data)

# Python Queue Class
class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def push(self, data): # Adds a new element to the back (tail)
        new = Node(data)
        if self.isEmpty():
            self.head = new
            self.tail = new
        else:
            self.tail.next = new
            self.tail = new

    def pop(self): # Returns and removes the front element
        if not self.isEmpty():
            value_to_remove = self.head.data
            self.head = self.head.next
            if self.head is None: # If the last element was removed
                self.tail = None
            return value_to_remove
        else:
            print('Queue is empty!') # Consider raising an exception in production code

    def top(self): # Returns the front element's value (PEEK)
        if not self.isEmpty():
            return self.head.data

    def isEmpty(self):
        return self.head is None and self.tail is None

    def __str__(self):
        result = '[ '
        current = self.head
        while current is not None:
            result += current.__str__() + " "
            current = current.next
        result += ']'
        return result

C++ Queue Implementation

The C++ implementation uses templates and manages memory for a linked list-based queue.

// C++ Node Class for Linked List
template <typename T>
class Node {
public:
    T value;
    Node* next;

    Node(T val) : value(val), next(nullptr) {}

    friend std::ostream& operator<<(std::ostream& output, const Node& n) {
        output << n.value;
        return output;
    }
};

// C++ Queue Class
template <typename T>
class Queue {
private:
    Node<T>* head;
    Node<T>* tail;

public:
    Queue() : head(nullptr), tail(nullptr) {} // Constructor

    ~Queue() { // Destructor to free memory
        Node<T>* current = head;
        while (current != nullptr) {
            Node<T>* next_node = current->next;
            delete current;
            current = next_node;
        }
        head = nullptr;
        tail = nullptr;
    }

    void push(T value) { // Adds a new element to the back (tail)
        Node<T>* new_node = new Node<T>(value);
        if (isEmpty()) {
            head = new_node;
            tail = new_node;
        } else {
            tail->next = new_node;
            tail = new_node;
        }
    }

    T pop() { // Returns and removes the front element
        if (!isEmpty()) {
            Node<T>* node_to_delete = head;
            T value_to_return = node_to_delete->value;
            head = head->next;
            if (head == nullptr) { // If the last element was removed
                tail = nullptr;
            }
            delete node_to_delete;
            return value_to_return;
        } else {
            return (T) NULL;
        }
    }

    T top() { // Returns the front element's value (PEEK)
        if (!isEmpty()) {
            return head->value;
        }
        return (T) NULL;
    }

    bool isEmpty() {
        return head == nullptr; // If head is null, tail must also be null for an empty queue
    }

    friend std::ostream& operator<<(std::ostream& output, const Queue<T>& s) {
        output << "[";
        if (s.head != nullptr) {
            Node<T>* current = s.head;
            while (current != nullptr) {
                output << (*current);
                if (current->next != nullptr) output << ",";
                current = current->next;
            }
        }
        output << "]";
        return output;
    }
};

Deque Data Structure (Double-Ended Queue)

A Deque (Double-Ended Queue) is a data structure that allows elements to be added or removed from both the front and the back.

Python Deque Implementation

The Python implementation uses a Node class with both next and prev pointers for a doubly linked list.

# Python Node Class for Doubly Linked List
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

    def __str__(self):
        return str(self.data)

# Python Deque Class
class Deque:
    def __init__(self):
        self.head = None
        self.tail = None

    def push_front(self, data): # Adds a new element to the front
        new = Node(data)
        if self.isEmpty():
            self.head = new
            self.tail = new
        else:
            new.next = self.head
            self.head.prev = new
            self.head = new

    def push_back(self, data): # Adds a new element to the back (tail)
        new = Node(data)
        if self.isEmpty():
            self.head = new
            self.tail = new
        else:
            self.tail.next = new
            new.prev = self.tail
            self.tail = new

    def pop_front(self): # Returns and removes the front element
        if not self.isEmpty():
            value_to_remove = self.head.data
            self.head = self.head.next
            if self.head is None:
                self.tail = None
            else:
                self.head.prev = None
            return value_to_remove
        else:
            print('Deque is empty!') # Consider raising an exception in production code

    def pop_back(self): # Returns and removes the back element
        if not self.isEmpty():
            value_to_remove = self.tail.data
            self.tail = self.tail.prev
            if self.tail is None:
                self.head = None
            else:
                self.tail.next = None
            return value_to_remove
        else:
            print('Deque is empty!') # Consider raising an exception in production code

    def front(self): # Returns the front element's value (PEEK)
        if not self.isEmpty():
            return self.head.data

    def back(self): # Returns the back element's value (PEEK)
        if not self.isEmpty():
            return self.tail.data

    def isEmpty(self):
        return self.head is None and self.tail is None

    def __str__(self):
        result = '[ '
        current = self.head
        while current is not None:
            result += current.__str__() + " "
            current = current.next
        result += ']'
        return result

C++ Deque Implementation

The C++ implementation uses templates and manages memory for a doubly linked list-based deque.

// C++ Node Class for Doubly Linked List
template <typename T>
class Node {
public:
    T value;
    Node* next;
    Node* prev;

    Node(T val) : value(val), next(nullptr), prev(nullptr) {}

    friend std::ostream& operator<<(std::ostream& output, const Node& n) {
        output << n.value;
        return output;
    }
};

// C++ Deque Class
template <typename T>
class Deque {
private:
    Node<T>* head;
    Node<T>* tail;

public:
    Deque() : head(nullptr), tail(nullptr) {} // Constructor

    ~Deque() { // Destructor to free memory
        Node<T>* current = head;
        while (current != nullptr) {
            Node<T>* next_node = current->next;
            delete current;
            current = next_node;
        }
        head = nullptr;
        tail = nullptr;
    }

    void push_front(T value) { // Adds a new element to the front
        Node<T>* new_node = new Node<T>(value);
        if (isEmpty()) {
            head = new_node;
            tail = new_node;
        } else {
            new_node->next = head;
            head->prev = new_node;
            head = new_node;
        }
    }

    void push_back(T value) { // Adds a new element to the back (tail)
        Node<T>* new_node = new Node<T>(value);
        if (isEmpty()) {
            head = new_node;
            tail = new_node;
        } else {
            tail->next = new_node;
            new_node->prev = tail;
            tail = new_node;
        }
    }

    T pop_front() { // Returns and removes the front element
        if (!isEmpty()) {
            Node<T>* node_to_delete = head;
            T value_to_return = node_to_delete->value;

            head = head->next;
            if (head == nullptr) {
                tail = nullptr;
            } else {
                head->prev = nullptr;
            }
            delete node_to_delete;
            return value_to_return;
        } else {
            return (T) NULL;
        }
    }

    T pop_back() { // Returns and removes the back element
        if (!isEmpty()) {
            Node<T>* node_to_delete = tail;
            T value_to_return = node_to_delete->value;

            tail = tail->prev;
            if (tail == nullptr) {
                head = nullptr;
            }
            delete node_to_delete;
            return value_to_return;
        } else {
            return (T) NULL;
        }
    }

    T front() { // Returns the front element's value (PEEK)
        if (!isEmpty()) {
            return head->value;
        }
        return (T) NULL;
    }

    T back() { // Returns the back element's value (PEEK)
        if (!isEmpty()) {
            return tail->value;
        }
        return (T) NULL;
    }

    bool isEmpty() {
        return head == nullptr && tail == nullptr;
    }

    friend std::ostream& operator<<(std::ostream& output, const Deque<T>& s) {
        output << "[";
        if (s.head != nullptr) {
            Node<T>* current = s.head;
            while (current != nullptr) {
                output << (*current);
                if (current->next != nullptr) output << ",";
                current = current->next;
            }
        }
        output << "]";
        return output;
    }
};