DSA - Queues

I have been learning about Queues and solving problems on them since past 3 days. And here is what I have learnt considering this to be a notes to myself to refer later.

We know that Queues work based on the principle of FIFO — First In First Out, where the element that enters the queue first is dequeued or removed first. Or we could also say it is based on the principle of LILO — Last In Last Out, where the element that enters the queue last is dequeued or removed last.

Let’s see the possible operations of a basic single ended Queue:

1. Enqueue -----> operation to add to the rear end of the queue
2. Dequeue -----> operation to remove from the front of the queue
3. isEmpty ------> operation to check whether the queue is empty
4. top/front -----> operation to get the top or front element of the queue
5. size -----> operation to get the size of the queue

Queues can be implemented using the following data structures:

1. Arrays
2. Linked Lists
3. Stacks

Let’s look at their implementation:

1. Arrays

We consider front and rear positions where front points to the front position of the queue and rear points to the end position of the queue.

To implement it using arrays, when we enqueue, we just add the element to the end of the queue and just increment the rear position. When we dequeue the element -> we just increment the front position of the queue.

Here for dequeue, we don’t remove the elements from the front position of the queue as it would take O(n) time complexity to move all the elements to the left once the element from the front is removed.

So, only the front position is incremented as the dequeue is called which indicates the element removed from the front of the queue.

Let’s look at the code or pseudocode:

class Queue {
    private var queue: [Int] = []
    private var front: Int = -1
    private var rear: Int = -1
    private var size: Int = 0

    init() {
        self.queue = []
        self.front = -1
        self.rear = -1
        self.size = 0
    }

    func enqueue(_ data: Int) {
        self.queue.append(data)
        rear += 1
        size += 1
    }

    func dequeue() -> Int {
        front += 1
        size -= 1
        return self.queue[front+1]
    }

    func getSize() -> Int {
        return size
    }

    func getFront() -> Int {
        return self.queue[front+1]
    }

}

So, the following is the complexity for all operations:

Time Complexity : O(1) Space Complexity : O(n)

2. Linked Lists

Let’s look at the implementation of a queue using Linked Lists.

Here, we consider a head pointer which points to the front of the queue and a current or rear pointer which points to the end of the queue. To be in sync, let’s consider the end pointer to be rear.

For enqueue, we add using the rear pointer and for dequeue, we remove using the front pointer.

We initially will consider a dummy pointer for the head and keep adding the nodes based on incoming data.

Let’s see at the code implementation for the same:

class Queue {
    private var head: Node?
    private var rear: Node?
    private var size: Int

    init() {
        // Dummy Node where head and rear would initially point to
        self.head = Node(0)
        self.rear = self.head
        self.size = 0
    }

    func enqueue(_ data : Int) {
        self.rear?.next = Node(data)
        self.rear = self.rear?.next
        size += 1
    }

    // Considering dequeue will be called, only when size > 0 
    func dequeue() -> Int? {
        if let node = self.head?.next {
            self.head?.next = node.next
            node.next = nil 
            size -= 1
            return node.val
        }
        return nil
    }

    func getFront() -> Int? {
        if let node = self.head?.next {
             return node.val
        }
        return nil
    }

    func getSize() -> Int {
        return size
    }
}

class Node {
    var val: Int 
    var next: Node?

    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

The following is the complexity for all operations:

Time Complexity : O(1) Space Complexity : O(n)

3. Stacks

Let’s look at the implementation of a queue using stacks.

It isn’t possible to implement a queue using a single stack as stack is based on the principle of LIFO while queue is based on the principle of FIFO.

So, we will consider 2 stacks one for enqueue operation and another stack for dequeue operation.

How it works is that for any kind of enqueue operation, we just add the element to the enqueueStack. While for dequeue, we just check if the dequeueStack is not empty, then we dequeue the element, otherwise when the dequeueStack is empty, we just pop the elements from enqueueStack and push them to dequeueStack until enqueueStack is all emptied and then dequeue is done for dequeueStack.

Let’s look at the code implementation:

class Queue {
    private var enqueueStack: [Int] = []
    private var dequeueStack: [Int] = []
    private var size: Int = 0

    init() {
        enqueueStack = []
        dequeueStack = []
        size = 0
    }

    func enqueue(_ data: Int) {
        enqueueStack.append(data)
        size += 1
    }

    // Considering dequeue will be called, only when size > 0
    func dequeue() -> Int {
        if dequeueStack.count > 0 {
            size -= 1
            return dequeueStack.popLast()
        } else {
            while let lastElem = enqueueStack.last {
                dequeueStack.append(enqueueStack.popLast())
            }
             size -= 1
            return dequeueStack.popLast()
        }
    }

    func getSize() -> Int {
        return size
    }

    func getFront() -> Int {
        if dequeueStack.count > 0 {
            return dequeueStack.last
        } else {
            while let lastElem = enqueueStack.last {
                dequeueStack.append(enqueueStack.popLast())
            }
            return dequeueStack.last
        }
    }
 }

Let’s look at the complexity for all operations:

Space Complexity : O(n)

Time Complexity: Enqueue -> O(1) Dequeue If dequeueStack.count > 0, Time Complexity is O(1) If dequeueStack.count == 0,

For 1 pop operation, we transfer all the elements from enqueueStack to dequeueStack -> pop and push for all elements and then 1 pop from dequeueStack.

Total operations = 2n + 1 =======> for 1 pop operation Total Operations = 1 ======> for n-1 pop operations ====> as all elements are transferred from enqueueStack to dequeueStack

In total, there will be (2n + 1)1 + (1)n-1

=====> (2n + 1+ n - 1) =====> (3n)

Total Operations -> (3n) for ‘n’ pop operations -> O(n) complexity Now, for 1 operations, it will be O(1) complexity

Time Complexity for Dequeue -> O(1)

Double Ended Queue (Deque)

Let’s look at the double ended queue and types of operations we can do on it.

A double ended queue is a queue where we can enqueue/dequeue from front/rear.

The following are the possible operations of Deque:

1. EnqueueFromRear
2. EnqueueFromFront
3. DequeueFromFront
4. DequeueFromRear
5. getSize
6. getFront
7. getRear

We can implement it using either Arrays, LinkedLists or Queues. For now, will be implementing it using LinkedLists.

Let’s look at the code implementation for the same:

class Deque {
    private var head: Node?
    private var rear: Node?
    private var size = 0

    init() {
        // Pointing head and rear initially to a dummy node
        self.head = Node(0)
        self.rear = self.head
        size = 0
    } 

    func enqueueFromRear(_ data: Int) {
        let newNode = Node(data)
        self.rear?.next = newNode
        newNode.previous = self.rear
        self.rear = self.rear?.next
        size += 1
    }

    func enqueueFromFront(_ data: Int) {
        let newNode = Node(data)
        if let node = self.head?.next {
            self.head?.next = newNode
            newNode.next = node
            newNode.previous = self.head
            node.previous = newNode
        } else {
            self.head?.next = newNode
            newNode.previous = self.head
        }
        size += 1
    }

    func dequeueFromRear() -> Int? {
        if self.head !=== self.rear {
            let current = self.rear
            self.rear = current?.previous
            self.rear?.next = current?.next
            current?.previous = nil
            size -= 1
            return current?.val            
        }
        return nil
    }

    func dequeueFromFront() -> Int? {
        if let node = self.head?.next {
            self.head?.next = node.next

            if let nextNode = node.next {
                nextNode.previous = self.head
            }

            node.next = nil
            node.previous = nil

            size -= 1

            return node.val
        }

        return nil
    }

    func getFront() -> Int? {
        if let node = self.head?.next {
            return node.val
        }
        return nil
    }

    func getRear() -> Int? {
        if let node = self.rear,
        self.head !== self.rear {
            return node.val
        }
        return nil
    }

    func getSize() -> Int {
        return size 
    }
}

class Node {
    var val: Int 
    var next: Node?
    var previous: Node?

    init() {
        self.val = val
        self.next = nil
        self.previous = nil
    }
}

The following is the time complexity for all operations:

Time Complexity : O(1) Space Complexity : O(n)

Will be updating the real world examples of Queues in the same page once I have a grip on them.

For now, these are all I have learnt for theory on Queues and the problems I have practiced are based on the application of whatever has been listed above.

Looking forward to learn more about the production use cases and updating the same here.

Divya