DSALLSTK - Editorial

editorial
1

Problem Link - Stack Implementation using Linked List

Problem Statement

Implement a queue using a linked list. The queue should support the following operations:

  1. enqueue(int value): Add an element to the rear of the queue.

  2. dequeue(): Remove an element from the front of the queue.

  3. getFront(): Get the front element of the queue without removing it.

  4. isEmpty(): Check if the queue is empty.

Approach

To implement the queue using a linked list:

  1. Enqueue Operation: Allocate a new node with the given value. If the queue is empty, update both front and rear to the new node. Otherwise, link the new node at the end and update the rear pointer.

  2. Dequeue Operation: Check if the queue is empty. If not, store the current front, move the front pointer to the next node, and delete the old front node. If the queue becomes empty, update rear to nullptr.

  3. Get Front Operation: Return the data of the front node if the queue is not empty.

  4. Is Empty Operation: Return true if front is nullptr.

Time Complexity

  • Enqueue: O(1) - Inserting at the rear takes constant time.

  • Dequeue: O(1) - Removing from the front takes constant time.

  • Get Front: O(1) - Accessing the front element takes constant time.

  • Is Empty: O(1) - Checking if the queue is empty takes constant time.

  • Display: O(n) - Traversing the queue takes linear time, where n is the number of elements in the queue.

Space Complexity

  • O(n) - The space complexity is linear, as we are using additional space for each node in the linked list, where n is the number of elements in the queue