Do you need a previous node pointer to implement a Queue?

Question

I am looking for some clarification / confirmation here.

To my understanding, a Stack can be implemented with a Singly Linked List because all stack operations are performed on the top (head) of the stack. In other words, every stack node only needs a pointer to the next node.

However, in a Queue, we need to perform operations at both the front and the back of the queue (ie. enqueue() and dequeue()). Does that mean, that a proper Queue implementation must be built on a Doubly Linked List (ie. a Linked List where each node has both a next and previous pointer)?

Thanks!

Already answered, but the operations at both the front and back are limited to push_front() and pop_back(). There could also be peek operations, such as peek_back(), and while peek_front() is possible, it would be unusual. — rcgldr

Vo Quoc Thang Vo Quoc Thang · Accepted Answer · 2021-02-11T16:00:43

For Queue, you can implement with Singly Linked List by using 2 pointers: one for the head and one for the tail. So, No need to use Doubly Linked List.
This is the implementation I took from GeeksForGeeks:

#include <bits/stdc++.h> 
using namespace std; 
  
struct QNode { 
    int data; 
    QNode* next; 
    QNode(int d) 
    { 
        data = d; 
        next = NULL; 
    } 
}; 
  
struct Queue { 
    QNode *front, *rear; 
    Queue() 
    { 
        front = rear = NULL; 
    } 
  
    void enQueue(int x) 
    { 
  
        // Create a new LL node 
        QNode* temp = new QNode(x); 
  
        // If queue is empty, then 
        // new node is front and rear both 
        if (rear == NULL) { 
            front = rear = temp; 
            return; 
        } 
  
        // Add the new node at 
        // the end of queue and change rear 
        rear->next = temp; 
        rear = temp; 
    } 
  
    // Function to remove 
    // a key from given queue q 
    void deQueue() 
    { 
        // If queue is empty, return NULL. 
        if (front == NULL) 
            return; 
  
        // Store previous front and 
        // move front one node ahead 
        QNode* temp = front; 
        front = front->next; 
  
        // If front becomes NULL, then 
        // change rear also as NULL 
        if (front == NULL) 
            rear = NULL; 
  
        delete (temp); 
    } 
}; 
  
// Driven Program 
int main() 
{ 
  
    Queue q; 
    q.enQueue(10); 
    q.enQueue(20); 
    q.deQueue(); 
    q.deQueue(); 
    q.enQueue(30); 
    q.enQueue(40); 
    q.enQueue(50); 
    q.deQueue(); 
    cout << "Queue Front : " << (q.front)->data << endl; 
    cout << "Queue Rear : " << (q.rear)->data; 
} 
// This code is contributed by rathbhupendra

Do you need a previous node pointer to implement a Queue?

2 Answers