Test Category

Test Blog Post

Starter template for writing out a blog post using MDX/JSX and Next.js.

Abdullah Muhammad

Published on May 17, 2026 • 5 min read• 1 views

Share:

Article Cover Image

Introduction

In a past article, we covered the three most basic data structures: stacks, queues, and linked lists.

Today, we will cover a little more detail on each of these data structures and explore their variations which can be useful for problem solving.

We will explore time complexities and look at the trade-offs associated with each data structure as it relates to searching, inserting, and deleting elements.

We will start with a review of the linked list data structure and build up from there. You can follow along by cloning this repository.

There are three directories we will be working with:

/demos/Demo69_Lists_Stacks_Queues_Variations/data_structures
/demos/Demo69_Lists_Stacks_Queues_Variations/leetcode_problems
/demos/Demo69_Lists_Stacks_Queues_Variations/recursive_data_structures

Linked Lists

Linked lists are similar to arrays except they are dynamic in size.

Depending on the programming language you use, arrays can be static in size and need to account for additional size (dynamic arrays) once the number of elements have reached the size limit.

Linked lists do not need to account for size because they are always dynamic.

We utilize a recursive data structure known as a LinkNode and connect these nodes with the help of references (a powerful concept related to objects and object oriented programming).

These "links" create what we call a "linked list".

The following code details an implementation of a recursive data type known as LinkNode (recursive_data_structures/LinkNode.ts):

GitHub GistTypeScript

// Recursive data structure
class LinkNode {
    next: LinkNode | null;
    item: number;

    // Initalizing the link node with its value
    constructor(value: number){
        this.item = value;
        this.next = null;
    }
}

export { LinkNode };

LinkNode recursive data structure

You can see that we have one forward pointing reference known as next and a value pertaining to a particular node.

In a singly linked list, we can only traverse forward in the list. There are no references to previous nodes.

When we explore doubly linked lists, we will see how to accomplish this.

The following code segment details an elegant implementation of the singly linked list using TypeScript (data_structures/LinkedLists/LinkedList.ts):

GitHub GistTypeScript

import { LinkNode } from '../../recursive_data_structures/LinkNode';

class LinkedList {
    head: LinkNode | null;

    constructor(){
        this.head = null;
    }

    // Append the node to the front of the linked list
    appendFirst(item: number): void {
        if (this.head === null) {
            this.head = new LinkNode(item);
        }
        else {
            // Create the new node and set its reference to the head of the list
            const newNode = new LinkNode(item);

            newNode.next = this.head;
            this.head = newNode; // Re-assign the head to become the new head node of the list
        }
    }

    // Append the node at the end of the linked list
    appendLast(item: number): void {
        if (this.head === null) {
            this.head = new LinkNode(item);
        }
        else {
            let traverseNode = this.head;

            // Start at the head of the list and traverse all the way to the end
            while (traverseNode.next !== null) {
                traverseNode = traverseNode.next;
            }

            let newNode = new LinkNode(item); // Create the new node
            traverseNode.next = newNode; // Set the reference of the last node in the list to this new node
        }
    }

    removeFirst(): number | null {
        // No head exists, return null, otherwise point the head to be the next item in the list
        // Capture and return the value before changing reference
        if (this.head === null) {
            return null;
        }
        else {
            let item = this.head.item;
            this.head = this.head.next;

            return item;
        }
    }

    removeLast(): number | null {
        if (this.head === null) {
            return null;
        }
        else {
            // Use two nodes to safely remove the last in the list
            let prevNode = this.head;
            let currNode = this.head.next;

            // If only one node exists, remove the first node, return its value
            if (currNode === null) {
                let item = prevNode.item;
                this.head = null;
                
                return item;
            }
            else {
                while (currNode.next !== null) {
                    prevNode = currNode;
                    currNode = currNode!.next;
                }
                
                let item = currNode.item; // Capture the value of the last node in the list
                prevNode.next = null; // Remove the last node in the list
                
                return item;
            }
        }
    }

    // Return the length of the linkedlist
    length(): number {
        let length = 0;

        // If the head of the list does not exist, return 0
        if (this.head === null) {
            return 0;
        }
        else {
            // Traverse through the nodes and start with the length of 1
            let traverseNode = this.head;
            length += 1;

            // Traverse through the linked list
            while (traverseNode.next !== null) {
                traverseNode = traverseNode.next;
                length += 1;
            }

            return length;
        }
    }

    // Check to see if the linked list is empty
    isEmpty(): boolean {
        return this.head === null;
    }
}

export { LinkedList };

Linked list TypeScript implementation

You can see that we have four primary operations: insertFirst, insertLast, deleteFirst, and deleteLast.

The time complexity is O(1) for all operations except removing and inserting the last item in the linked list.

Had we had an additional node that kept track of the end of the list, we could reduce the insertLast operation time complexity to O(1).

The deleteLast operation would still have a time complexity of O(n) because we would need to traverse the entire list to get to the second last node in the list.

As stated earlier, there is no way to traverse backwards in a singly linked list.

We will now explore variations of this data structure.

Exploring Linked List Variations

The first variation we will look at is the circular (singly) linked list.

This variation has an added benefit of ensuring there are no null values and that the last node in the list always points back to the first node using the next pointer reference.

This allows one to traverse a linked list to the end by checking to see if a node has a reference pointing back to the head. If so, we know we have reached the end of the linked list.

All operation time complexities in a circular (singly) linked list are the same as the singly linked list.

The following code segment details an implementation of the circular (singly) linked list (data_structures/LinkedLists/CircularLinkedList.ts):

GitHub GistTypeScript

import { LinkNode } from "../../recursive_data_structures/LinkNode";

class CircularLinkedList {
    head: LinkNode | null;

    constructor() {
        this.head = null;
    }

    appendFirst(item: number): void {
        // Initialize the head node
        // Point its next reference to itself
        if (this.head === null) {
            this.head = new LinkNode(item);
            this.head.next = this.head;
        }
        else {
            let tail = this.head;

            // Traverse to the next of the list, ensuring that we can safely change the reference
            while (tail.next !== this.head) {
                tail = tail.next;
            }

            // Create the new node
            let newNode = new LinkNode(item);
            
            // Set its reference to the old head
            // Point the old head to the new head of the list
            // Point the last node reference to this new head of the list
            newNode.next = this.head;
            this.head = newNode;
            tail.next = this.head;
        }
    }

    appendLast(item: number): void {
        if (this.head === null) {
            this.head = new LinkNode(item);
            this.head.next = this.head;
        }
        else {
            let tail = this.head;

            // Traverse to the end of the list
            // Create the new node
            // Point the last node reference to this new node
            // Point the next node reference of the new node to the head of the list
            while (tail!.next !== this.head) {
                tail = tail.next;
            }

            let newNode = new LinkNode(item);
            tail.next = newNode;
            newNode.next = this.head;
        }
    }

    removeFirst(): number | null {
        if (this.head === null) {
            return null;
        }
        else {
            if (this.head.next === this.head) {
                let item = this.head.item;
                this.head = null;

                return item;
            }
            else {
                let item = this.head.item; // Capture the value of the head of the list
                let tail = this.head;
    
                // Traverse to the end of the linked list
                while (tail.next !== this.head) {
                    tail = tail.next;
                }
    
                this.head = this.head.next; // Remove the reference to the head, point to the next node in the list
                tail.next = this.head; // Reference the tail back to the new head of the list
    
                return item;
            }
        }
    }

    removeLast(): number | null {
        if (this.head === null) {
            return null;
        }
        else {
            // Check to see if one node exists, if so, remove it
            if (this.head.next === this.head) {
                let item = this.head.item;
                this.head = null;

                return item;
            }
            else {
                // Use two nodes to effectively delete the last node in the list
                // Capture the value of the last node in the list
                // Change the reference of the second last node in the list to the head of the list
                let prevNode = this.head;
                let currNode = this.head.next;

                while (currNode!.next !== this.head) {
                    prevNode = currNode!;
                    currNode =  currNode!.next;
                }

                let item = currNode!.item;
                prevNode.next = this.head;

                return item;
            }
        }
    }
}

export { CircularLinkedList };

Circular (singly) linked list implementation in TypeScript

The implementation closely resembles that of the singly linked list.

However, there is a minor difference in that, we ensure the tail end of the list points back to the head of the list.

We now look at another data structure known as a doubly linked list.

Doubly Linked List

As the name implies, doubly linked lists consist of nodes with two references.

One reference points to the previous node in the list and another reference points to the next node in the list.

This allows one to traverse forward and backward in a list and it effectively reduces the run-time complexity of insertions and deletions to O(1).

We can keep track of the end of the list as well using a tail pointer and since this is not a doubly (circular) linked list, the previous pointer of the head node and the next pointer of the tail node will always be null.

To implement a doubly linked list, we first need to define a double link node recursive data structure (recursive_data_structures/DoubleLinkNode.ts):

GitHub GistTypeScript

// Recursive data structure
class DoubleLinkNode {
    head: DoubleLinkNode | null;
    tail: DoubleLinkNode | null;
    value: number;

    // Initializing the double link node
    constructor(value: number) {
        this.value = value;
        this.head = null;
        this.tail = null;
    }
}

export { DoubleLinkNode };

Double link node data structure consists of two nodes a head and a tail

As you can see, we make use of two nodes to keep track of the two references. One for the previous node in the list and another for the next node in the list.

The following code segment details an implementation of the doubly linked list in TypeScript (data_structures/LinkedLists/DoublyLinkedList.ts):

GitHub GistTypeScript

import { DoubleLinkNode } from "../../recursive_data_structures/DoubleLinkNode";  

// Doubly Linked list data structure uses two pointers for forwards and backwards traversals
// Head and Tail nodes keep track of the beginning and end of the Linked List
class DoublyLinkedList {
    head: DoubleLinkNode | null;
    tail: DoubleLinkNode | null;

    constructor() {
        this.head = null;
        this.tail = null;
    }

    // Append the item at the front of the doubly linked list
    appendFirst(item: number): void {
        if (this.head === null) {
            this.head = this.tail = new DoubleLinkNode(item);
        }
        else {
            let newNode = new DoubleLinkNode(item);
            
            newNode.next = this.head;
            this.head.prev = newNode;
            this.head = newNode;
        }
    }

    // Append node to the end of the Doubly Linked List
    appendLast(item: number): void {
        if (this.head === null) {
            this.head = this.tail = new DoubleLinkNode(item);
        }
        else {
            // Initialize a new node
            let newNode = new DoubleLinkNode(item);

            // Re-configure the tail node of the Doubly Linked List
            this.tail!.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
    }


    removeFirst(): number | null {
        if (this.head === null) {
            return null;
        }
        else {
            // If one node exists, remove it
            if (this.head.next === null) {
                let item = this.head.value;
                this.head = this.tail = null;

                return item;
            }
            else {
                // Capture the value of the head node
                // Point to the second node in the list
                // Remove the previous reference
                // Set the old head to the new head
                let item = this.head.value;
                let nextNode = this.head.next;

                nextNode.prev = null;
                this.head = nextNode;

                return item; 
            }
        }
    }

    removeLast(): number | null {
        if (this.head === null) {
            return null;
        }
        else {
            // If one node exists, remove it
            if (this.head.next === null) {
                let item = this.head.value;
                this.head = this.tail = null;
                
                return item;
            }
            else {
                // Capture the item from the last node
                // Capture the second last node at the end
                let item = this.tail!.value;
                let secondLastNode = this.tail!.prev;

                // Set the pointer of the second last node to null
                // Set the tail to be the new tail which is the second last node of the list
                secondLastNode!.next = null;
                this.tail = secondLastNode;

                return item;
            }

        }
    }
}

export { DoublyLinkedList };

Doubly linked list implementation in TypeScript

When we work with insertions and deletions at the front, we work with the head node. Likewise, when we work with insertions and deletions at the end, we work with the tail node.

We update the references of the previous and next nodes for every operation and as mentioned earlier, we effectively reduce the time complexity down to O(1).

Doubly (Circular) Linked List

Building on the circular linked list data structure and the doubly linked list data structure, we can have a doubly circular linked list.

Doubly circular linked lists follow a similar implementation to doubly linked lists except we need to perform additional operations to update the head/previous and tail/next references, respectively.

This requires a deep understanding of object references and how insertions and deletions work.

The head of the list uses its previous node reference to point back to the tail of the list and the tail uses its next node reference to point to the head of the list.

You get the same circular linked list data structure with an added benefit of traversing the list backwards.

The following code segment details an implementation of the doubly circular linked list in TypeScript (data_structures/LinkedLists/DoublyCircularLinkedList.ts):

GitHub GistTypeScript

import { DoubleLinkNode } from '../../recursive_data_structures/DoubleLinkNode';

// Implements a Doubly Linked List with a Circular architecture
class DoublyCircularLinkedList {
    head: DoubleLinkNode | null;
    tail: DoubleLinkNode | null;

    // Initialize the Doubly Circular Linked List
    constructor() {
        this.head = null;
        this.tail = null;
    }

    // Append node at the front of the list
    appendFirst(item: number): void {
        if (this.head === null) {
            this.head = this.tail = new DoubleLinkNode(item);
            this.head.next = this.head.prev = this.head;
        }
        else {
            // Create the new node and ensure its next reference points to the head
            let newNode = new DoubleLinkNode(item);
            newNode.next = this.head;

            // Ensure the old head previous reference points to the new head
            // Assign the old head to be the new head
            this.head.prev = newNode;
            this.head = newNode;

            // Set the previous reference of the new head to be the tail
            // Set the tail reference to point to the new head
            this.head.prev = this.tail;
            this.tail!.next = this.head;
        }
    }

    // Append node at the end of the list
    appendLast(item: number): void {
        if (this.head === null) {
            this.head = this.tail = new DoubleLinkNode(item);
            this.head.next = this.head.prev = this.head;
        }
        else {
            // Create the new node at the end of the list
            // Assign the old tail next reference to point to this new node
            // Assign the old tail to become the new tail
            // Set the tail next reference to head
            // Set the head previous reference to tail
            let newNode = new DoubleLinkNode(item);
            this.tail!.next = newNode;
            newNode.prev = this.tail;

            this.tail = newNode;

            this.tail.next = this.head;
            this.head.prev = this.tail;
        }
    }

    // Remove node from the start of the list
    removeFirst(): number | null {
        if (this.head === null) {
            return null;
        }
        else {
            // If only one node exists, remove it
            if (this.head === this.tail) {
                let item = this.head.value;
                this.head = this.tail = null;

                return item;
            }
            else {
                // Capture the value at the front of the list
                // Capture the second node in the list
                let item = this.head.value;
                let nextNode = this.head.next;

                // Set its previous reference to be the tail of the lits
                // Set the old head to become the new head
                // Set the next reference of the tail node to point to the head
                nextNode.prev = this.tail;
                this.head = nextNode;
                this.tail!.next = this.head;

                return item;
            }
        }
    }

    // Remove node from the end of the list
    removeLast(): number | null {
        if (this.head === null) {
            return null;
        }
        else {
            if (this.head === this.tail) {
                let item = this.head.value;
                this.head = this.tail = null;

                return item;
            }
            else {
                // Capture the item at the end of the list
                // Capture the second last item in the list
                // Set the next reference of the second last item to point to the head
                // Set the old tail to this new tail
                // Set the head previous reference to point to this new tail
                let item = this.tail!.value;
                let secondLastNode = this.tail!.prev!;

                secondLastNode.next = this.head;
                this.tail = secondLastNode;
                this.head!.prev = this.tail;

                return item;
            }
        }
    }
}

export { DoublyCircularLinkedList };

Doubly circular linked list implementation using TypeScript

An elegant and easy to follow solution if you have a solid understanding of node pointers and object references.

Use Case Scenarios

You might be wondering if it is worth learning the different variations of the linked list data structure. Each linked list variant offers its own advantages.

For instance, a doubly linked list is useful for navigating forward and backward between nodes.

A circular linked list is valuable for scheduling and automating repetitive tasks.

Once the list reaches the end of the cycle, it loops back to the beginning, making it ideal for scenarios where a process must repeat continuously.

Stacks, Queues, and More

We have explored stacks and queues in the past. Below, you will find implementations of the stack and queue data structures using the singly linked list we discussed earlier.

The following code segment details an implementation of the stack data structure (data_structures/Stack/Stack.ts):

GitHub GistTypeScript

import { LinkedList } from '../LinkedLists/LinkedList';

// Stack follows the LIFO principle
// Push, Pop are two of its primary operations
// Use the Linked List data structure to carefully craft the Stack data structure
class Stack {
    stackList: LinkedList

    // Initialize an empty stack and implement the LIFO principle using it
    constructor() {
        this.stackList = new LinkedList();
    }

    // Check for the element at the top of the stack and return the value
    peek(): number | null {
        if (this.stackList.length() === 0) {
            return null;
        }
        else {
            // Check for the head of the stack
            // Return its value
            let headItem = this.stackList.head
            return headItem!.item;
        }
    }

    // Append the item to the end of the list
    push(item: number): void {
        this.stackList.appendFirst(item);
    }

    // Remove and return the last element in the list
    pop(): number | null {
        return this.stackList.removeFirst();
    }

    // Length of the stack
    length(): number {
        return this.stackList.length();
    }

    // Check to see if the stack is empty
    isEmpty(): boolean {
        return this.stackList.isEmpty();
    }
}

export { Stack };

Stack implementation using TypeScript

We use the linked list data structure to implement the LIFO principle of the stack data structure.

The following code segment details an implementation for the queue data structure (data_structures/Queue/Queue.ts):

GitHub GistTypeScript

import { LinkedList } from "../LinkedLists/LinkedList";

// Queue follows the FIFO implementation
// Peek, Enqueue, and Dequeue are three of its primary operations
class Queue {
    queueList: LinkedList;

    constructor() {
        this.queueList = new LinkedList();
    }

    // Check the first item in the queue and return its value
    peek(): number | null {
        if (this.queueList.length() === 0) {
            return null;
        }
        else {
            // Return the item from the queue
            let queueHead = this.queueList.head
            return queueHead!.item;
        }
    }

    // Append the item at the back of the queue
    enqueue(item: number): void {
        this.queueList.appendLast(item);
    }

    // Remove the first item in the queue
    dequeue(): number | null {
        return this.queueList.removeFirst();
    }

    // Return the length of the queue
    length(): number {
        return this.queueList.length();
    }
}

export { Queue };

Queue implementation using TypeScript

Again, very similar to the stack implementation, but we enforce the FIFO principle here.

Now, we focus on variations of these data structures.

The first variation we will look at is a double-ended queue or deque for short.

Deque

This structure operates as a queue at both ends of the list.

We can add and remove at the front and likewise at the back.

The following code segment details an implementation of the double-ended queue data structure in TypeScript (data_structures/Queue/Deque.ts):

GitHub GistTypeScript

import { LinkedList } from '../LinkedLists/LinkedList';

// Double-Ended Queue that implements a Queue at both ends of a list
// We can append at the front and the back, remove at the front and the back
// FIFO at the front and FIFO at the back
class Deque {
    dequeList: LinkedList;

    // Initialize the double-ended queue
    constructor() {
        this.dequeList = new LinkedList();
    }

    // Peek at the front of the deque
    peekFront(): number | null {
        if (this.dequeList.length() === 0) {
            return null;
        }
        else {
            // Check the head of the list
            // Return the value of the item
            let headNode = this.dequeList.head;
            return headNode!.item;
        }
    }

    // Peek at the end of the deque
    peekLast(): number | null {
        if (this.dequeList.length() === 0) {
            return null;
        }
        else {
            let headItem = this.dequeList.head;

            // Traverse to the end of the Deque
            while (headItem!.next !== null) {
                headItem = headItem!.next;
            }

            return headItem!.item
        }
    }

    // Append item at the front of the deque
    frontEnqueue(item: number): void {
        this.dequeList.appendFirst(item); 
    }

    // Append item at the back of the deque
    backEnqueue(item: number): void {
        this.dequeList.appendLast(item);
    }

    // Remove item at the front of the deque
    frontDequeue(): number | null {
        return this.dequeList.removeFirst();
    }

    // Remove item from the back of the deque
    backDequeue(): number | null {
        return this.dequeList.removeLast();
    }

    // Return the length of the double-ended Queue
    length(): number {
        return this.dequeList.length();
    }   
}

export { Deque };

Deque implementation using TypeScript

As you can see, the implementation builds on the simple queue data structure we looked at.

With a deque, you have the ability to peek at elements at the front and at the back. Keep in mind, we implemented stacks and queues using singly linked lists.

Had we implemented them using doubly linked lists, we would efficiently reduce the time complexity of the peek operations down to O(1).

For simplicity, we implemented them using a singly linked list.

Nonetheless, this is an adequate, production-ready implementation of the deque data structure.

Steque

A variation of the stack and queue data structure is a hybrid data structure known as a steque.

It is a data structure that operates as a stack at the front and only allows for queue insertions (enqueue) at the back (no deletions).

The following code segment details an implementation of this data structure (data_structures/Stack/Steque.ts):

GitHub GistTypeScript

import { LinkedList } from '../LinkedLists/LinkedList';

// Steque implementation is a hybrid of Stack-Queue, implements LIFO principle at the front
// Supports Queue insertion at the back only (Enqueue)
// Implemented using a Singular Linked List
class Steque {
    stequeList: LinkedList

    constructor() {
        this.stequeList = new LinkedList();
    }

    // Implement LIFO with the push and pop methods at the front of the Steque
    // Add the item at the front
    push(item: number): void {
        this.stequeList.appendFirst(item);
    }

    // Remove the item at the front
    pop(): number | null {
        return this.stequeList.removeFirst();
    }

    // Enqueue at the end of the Steque
    enqueue(item: number): void {
        this.stequeList.appendLast(item);
    }

    // Peek at the front of the Steque
    peekFront(): number | null {
        if (this.stequeList.length() === 0) {
            return null;
        }
        else {
            let frontItem = this.stequeList.head;
            return frontItem!.item;
        }
    }

    // Peek at the back of the Steque
    peekBack(): number | null {
        if (this.stequeList.length() === 0) {
            return null;
        }
        else {
            let traverseNode = this.stequeList.head;

            // Traverse to the end of the Steque
            while (traverseNode!.next !== null) {
                traverseNode = traverseNode!.next;
            }

            // Return the last item in the Steque
            let backItem = traverseNode;
            return backItem!.item;
        }
    }
    
    // Return the length of the Steque
    length(): number {
        return this.stequeList.length();
    }
}

export { Steque };

Steque data structure implementation using TypeScript

If you understand how stacks and queues operate, your understanding of these variations becomes intuitive.

We use a singly linked list to implement a steque.

However, we could have also used a doubly linked list (like in the case of the deque data structure) to ensure O(1) time complexity for peeking at the front and at the back.

Aside from these variations, we can mix stacks and queues to implement each other.

We know that stacks follow the LIFO principle and queues follow the FIFO principle.

Using this knowledge, we can use a pair of stacks to implement a queue and vice versa.

Certain operations will be easy to implement, but others will be costly.

Two Stack Queue

A popular interview question you might encounter is implementing a queue using two stacks and vice versa.

The push operation is easy to implement, but the delete and peek operations are expensive.

We use two stacks with one operating as the primary data structure while the other is used as an assistant for the peek and delete operations.

The idea here is to implement a queue using two stacks and stack specific operations.

The following code segment shows how you can implement a queue using two stacks (data_structures/Queue/TwoStackQueue.ts):

GitHub GistTypeScript

import { Stack } from "../Stacks/Stack";

// Implementing a Queue using two Stacks
// FIFO principle implemented using two Stacks (LIFO)
class TwoStackQueue {
    stackOne: Stack | null;
    stackTwo: Stack | null;

    constructor() {
        this.stackOne = new Stack();
        this.stackTwo = new Stack();
    }

    // Populate stack one with the element
    // Enqueue operation will be the least costly
    enqueue(item: number): void {
        this.stackOne!.push(item);
    }

    // Dequeue operation will be expensive
    // Remove all the items from stack one, populate all the items into stack two
    // Popping the last element and capturing it in stack two, re-populating and emptying stack two back to stack one
    dequeue(): number | null {
        if (this.stackOne!.length() === 0) {
            return null;
        }
        else {
            // Remove all elements
            while (this.stackOne!.length() !== 0) {
                let element = this.stackOne!.pop();
                this.stackTwo?.push(element!);
            }

            // Capture the last element
            let lastElement = this.stackTwo!.pop();

            // Re-populate stack one, empty stack two
            while (this.stackTwo!.length() !== 0) {
                let element = this.stackTwo!.pop();
                this.stackOne!.push(element!);
            }

            return lastElement;
        }
    }

    // Locating the latest element in the Queue and returning it
    peek(): number | null {
        if (this.stackOne!.length() === 0) {
            return null;
        }
        else {
            // Remove all items from stack one and populate stack two
            while (this.stackOne!.length() !== 1) {
                let element = this.stackOne!.pop();
                this.stackTwo!.push(element!);
            }

            // Remove and capture the last element in the stack
            // Push the value onto the second stack
            // Re-populate stack one and return the last element
            let lastElement = this.stackOne!.pop();
            this.stackTwo!.push(lastElement!);

            while (this.stackTwo!.length() !== 0) {
                let element = this.stackTwo!.pop();
                this.stackOne!.push(element!);
            }

            return lastElement;
        }
    }

    // Return the length of stack one
    length(): number {
        return this.stackOne!.length();
    }

    // Check to see if stack one is empty
    isEmpty(): boolean {
        return this.stackOne!.length() === 0;
    }
}

export { TwoStackQueue };

Two stacks can be used to effectively implement a queue

As explained earlier, the enqueue operation is easy to implement.

The dequeue and peek operations are expensive because we need to pop all elements off the first stack, populate them into the second stack, and return the last element (which is the first in the queue).

After that, we have to empty the second stack and re-populate the first to maintain the stack order.

It does not matter if the operation is delete or peek, the last element of the first stack is of importance because we either capture and delete the item (dequeue) or capture it and return it in the case of peek.

Intuitively, this makes sense, but it requires a foundational understanding of how stacks and queues operate.

Two Queue Stack

We can likewise, implement a stack using two queues by strictly adhering to queue operations and following the FIFO principle.

The following code segment details how you can implement a stack using two queues (data_structures/Stack/TwoQueueStack.ts):

GitHub GistTypeScript

import { Queue } from '../Queues/Queue';

// Implement the FIFO principle using two Queues
// Support the operations of a Stack using two Queues
class TwoQueueStack {
    queueOne: Queue | null;
    queueTwo: Queue | null;

    constructor() {
        this.queueOne = new Queue();
        this.queueTwo = new Queue();
    }

    // Push item to the front of queue one
    push(item: number): void {
        this.queueOne!.enqueue(item);
    }

    // Remove the latest item from the queue using the second queue
    // Pop operation is expensive
    pop(): number | null {
        if (this.queueOne!.length() === 0) {
            return null;
        }
        else {
            // Remove all items except the last one
            // Dequeue the element from the first queue
            // Enqueue the element from the first queue into the second queue
            // Maintains the FIFO principle of the two Queues while implementing a LIFO Stack
            while (this.queueOne!.length() !== 1) {
                let element = this.queueOne!.dequeue();
                this.queueTwo!.enqueue(element!);
            }

            // Remove and capture the last element
            let lastElement = this.queueOne!.dequeue();

            // Now set the empty out all the items from the second queue back into the first queue to maintain FIFO
            while (this.queueTwo!.length() !== 0) {
                let element = this.queueTwo!.dequeue();
                this.queueOne!.enqueue(element!);
            }

            return lastElement;
        }
    }
    
    // Check the latest item in the Stack
    peek(): number | null {
        if (this.queueOne!.length() === 0) {
            return null;
        }
        else {
            // Enqueue all the elements from queue one, onto queue two
            while (this.queueOne!.length() !== 1) {
                let element = this.queueOne!.dequeue();
                this.queueTwo!.enqueue(element!);
            }

            // Capture the last element in the queue (or in this case, the top of the stack)
            let lastElement = this.queueOne!.dequeue();
            this.queueTwo!.enqueue(lastElement!); // We are not removing it so add it to queue two

            // Re-populate queue one and remove all items from queue two
            while (this.queueTwo!.length() !== 0) {
                let element = this.queueTwo!.dequeue();
                this.queueOne!.enqueue(element!);
            }

            return lastElement;
        }
    }

    // Return the length of queue one
    length(): number {
        return this.queueOne!.length();
    }

    // Check to see if queue one is empty
    isEmpty(): boolean {
        return this.queueOne!.length() === 0;
    }
}

export { TwoQueueStack };

Stacks can be effectively implemented using two queues

Once again, we see the push operation is easy to implement, but the peek and pop operations are expensive.

For both operations, we need to empty the first queue, populate the second queue, and remove the last element in the queue (capture and delete it in the case of delete or capture and return it in the case of peek).

Finally, we re-populate the first queue by emptying the second queue.

This is very similar to the implementation of the queue using two stacks with a slight variation in that, we use two queues and queue specific operations to implement a stack.

Each of these data structures is implemented using a singly linked list.

We could have utilized an array for implementing the stacks and queues, but we would need to consider adjusting the fixed space using a dynamic array.

Utilizing a linked list greatly reduces the complexity of having to deal with this situation.

Problem Solving

We will now explore three Leetcode problems which can be solved using data structures.

For simplicity, we will focus on problems that can be solved using the stack data structure.

Problem 1: Reversing a String

The most basic problem you can solve using stacks are string reversals.

"Is that even considered a problem?"

String reversals can be solved in one line. So, yeah, you would be right to assume that this is really not a problem.

In TypeScript, you can solve this problem with the help of string/array functions.

Suppose you have a string s, you can perform the following:

s.split('').reverse().join('')

When it comes to problem solving, you will be asked to use specific data structures and specific actions of that data structure to solve a particular problem.

So, in the spirit of that, the following code details how you would reverse a string using a stack and stack specific operations (leetcode_solutions/reverseString.ts):

GitHub GistTypeScript

// Use a stack and stack specific operations to solve this problem 
 function reverseString(s: string): string {
    let stack: string[] = []; // Initialize an empty array which will operate as a stack

    // Evaluate the base cases
    if (s === '') {
        return '';
    }
    else if (s.length === 1) {
        return s;
    }
    else {
        for (let i = 0; i < s.length; i++) {
            stack.push(s.charAt(i)); // Push each character (left to right) onto the stack
        }
        let reversedString = '';
        let character: string | undefined;

        // Pop all elements off the stack and push to the empty string and return it
        while ((character = stack.pop()) !== undefined) {
            reversedString += character;
        }

        return reversedString;
    }
 };

Reversing strings using a stack in TypeScript

Essentially, we push every character of the string (left to right) into an array which acts as a stack.

After that, we pop all the elements off the stack and concatenate each character to an empty string.

This effectively reverses the order in which we retrieve the characters (following the LIFO principle), hence reversing the string.

This is an example that illustrates a solid understanding of the push and pop operations of the stack data structure.

You can find the relevant Leetcode problem here.

Let us look at a more interesting problem.

Problem 2: Adjacent Removals

In this problem, we must ensure that no two consecutive characters (adjacent) are equal to each other. If they are, we must remove both.

If after removing the characters we get a resulting string that consists of another pair of adjacent characters, we must recursively continue the removal process until no adjacent characters are left in the string.

After that, we simply return the modified string.

If this problem sounds confusing, here is the Leetcode link to that problem.

So again, we can solve this problem using a stack. We proceed to push characters of the string (left to right) onto the stack.

As we do, we compare the incoming character to the latest one pushed onto the stack.

If they are equal to each other, we pop the latest character off the stack and continue with the next character conducting the same process.

The following code segment details a solution to this problem (leetcode_problems/removeAdjacents.ts):

GitHub GistTypeScript

function removeDuplicates(s: string): string {
    let stringStack = [];

    for (let i = 0; i < s.length; i++) {
        // Check if stack is empty
        if (stringStack.length === 0) {
            stringStack.push(s.charAt(i)); // Push character to end
        }
        else {
            // Compare new character to the latest pushed element to stack
            let characterElement = stringStack[stringStack.length - 1];

            // If incoming character is equal character element
            // Pop element
            if (characterElement === s.charAt(i)) {
                stringStack.pop();
            }
            else {
                // Push element to string stack
                stringStack.push(s.charAt(i));
            }
        }
    }

    // Join all the elements of the string array to formulate a string
    return stringStack.join(""); 
};

Removing adjacent characters in a string using a stack

Very simple and straight forward. The recursive removal process is also handled efficiently this way.

Problem 3: Valid Parenthesis

Finally, we will cover a popular problem associated with stacks and that is checking for valid parenthesis.

We must ensure that a string consists of valid opening and closing brackets. The Leetcode problem can be found in the link here.

Essentially, we can use a hash map to map opening and closing brackets. We will use the stack data structure to solve this problem.

We proceed by pushing ONLY the opening brackets of the string (left to right) onto the stack.

If we encounter a closing bracket, we immediately pop the latest element off the stack and compare the element to the closing bracket.

We check the pair by using the hash map we defined earlier. If the brackets match, we proceed and if not, we return false.

By the end of the string transversal, the stack must have zero elements in it because there can be no outstanding brackets left.

The following code segment details this thought process (leetcode_solutions/validParenthesis.ts):

GitHub GistTypeScript

function isValid(s: string): boolean {
    // traverse through the string using the stack data structure
    let bracketMap = new Map<string, string>();
    let bracketStack = [];

    bracketMap.set("(", ")");
    bracketMap.set("[", "]");
    bracketMap.set("{", "}");

    for (let i = 0; i < s.length; i++){
        if (bracketMap.has(s.charAt(i))) {
            bracketStack.push(s.charAt(i)); // Push the opening brace to stack
        }
        else {
            let element = bracketStack.pop(); // Run a comparison to the popped element
            if (bracketMap.get(element) !== s.charAt(i)) {
                return false; // If no match is found, return false
            }
            else {
                continue;
            }
        }
    }

    return bracketStack.length === 0 ? true : false; // Reach here, it is assumed to have worked
}

Check the validity of parenthesis using a stack

An elegant and efficient way to solve this problem using a stack.

Summary of Time Complexities

Phew! That was a lot we looked at in this article. There are many more variations out there, but these are the most popular ones.

Stacks and queues can be implemented using linked lists (as we saw) under the hood.

All operations in a stack, queue, and their variants have a time complexity of O(1).

The following table neatly summarizes the time complexities of the linked list data structures we looked at:

Table neatly detailing the time complexities of the Linked list variants

Please note, you can find this table in a README.md located at the root of this demo directory.

Conclusion

In this article, we looked at linked lists, stacks, queues, and explored their variants.

We looked at their use cases and time complexity trade-offs for searching, inserting, and deleting items.

We covered problem solving specifically related to Leetcode and used the stack data structure for solving string problems.

In the list below, you will find links to helpful resources related to linked lists, stacks, and queues.

You will also find links to the three Leetcode problems we covered as well as the GitHub repository used in this article:

I hope you found this article helpful and look forward to more in the future.

Thank you!

Abdullah Muhammad

Blogger. Software Engineer. Designer.

Subscribe to the newsletter

Get new articles, code samples, and project updates delivered straight to your inbox.