Scribd
Upload
153 views2 pages

Queue Using Linked List

The document discusses and compares array-based and linked list-based implementations of a queue data structure. For arrays, it notes that resizing the array is an O(n) operation when the array fills. For linked lists, it explains that using both a front and rear pointer allows enqueue and dequeue operations to occur in O(1) time rather than O(n) by avoiding traversing the entire list each time. Sample C++ code for a linked list queue implementation is also provided.

Uploaded by

Hassan Zia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
153 views2 pages

Queue Using Linked List

The document discusses and compares array-based and linked list-based implementations of a queue data structure. For arrays, it notes that resizing the array is an O(n) operation when the array fills. For linked lists, it explains that using both a front and rear pointer allows enqueue and dequeue operations to occur in O(1) time rather than O(n) by avoiding traversing the entire list each time. Sample C++ code for a linked list queue implementation is also provided.

Uploaded by

Hassan Zia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

Array Implementation:

what if array gets filled?


1) Sorry Queue is full, no more en queuing.
2) Create a new larger array and copy data from the original array.
the time taken in this copy operation will be proportional to the
the number of elements in the array
or in other words we can say that the timpe complexity will be
O(n)

What if we have already defined a large enough array to meet all the memory
requirements of our queue?
But what if queue is not utilizing the array completely?
Result: Memory Blockage or wastage.
Unused Memory.

Linked List Implementation:


Non-Contiguous memory allocation

Requirements:
One end must be front (to dequeue)
One end must be rear (to enqueue)
Each "enqueue" and "dequeue" operation must take a constant time "O(1)"
Problem:
whatever side we pick as front or rear one of the
operations "enqueue" or "dequeue" would cost us "O(n)"
as we keep record of only "head" node in linked list and
thus to move to tail (whether to insert or to
remove) we would have to assign the last node to some
pointer variable let say "temp" but still we would
have to start from "head" and then continuously
incrementing the "temp" until we reach the last node which
then we would assign temp to, and this whole process would
involve number of nodes in the list, making time
completely "O(n)"
Solution:
To avoid that traversal what we can do is simply assign
another pointer variable, let say "rear" to the tail
of the list. Thus we, now, would have the record of both
head as "front" and tail as "rear" and now each
operation would cost only "O(1)".
HOW:
We would have to simply modify/update the front and
rear pointer variables after an enqueue or dequeue
operation. This design would not depend upon the no.
of nodes in the list.

/*
=========CODE========
*/
/*Queue - Linked List implementation*/
#include<iostream>
using namespace std;
typedef struct Node {
int data;
Node* next;
};
// Two glboal variables to store address of front and rear nodes.
Node* front = NULL;
Node* rear = NULL;
// To Enqueue an integer
void Enqueue(int x) {
Node* n_node;
n_node = new Node;
n_node->data =x;
n_node->next = NULL;
if(front == NULL && rear == NULL){
front = rear = n_node;
return;
}
rear->next = n_node;
rear = n_node;
}

// To Dequeue an integer.
void Dequeue() {
Node* temp = front;
if(front == NULL) {
cout<<"Queue is Empty\n";
return;
}
if(front == rear) {
front = rear = NULL;
}
else {
front = front->next;
}
delete temp;
}

int Front() {
if(front == NULL) {
cout<<"Queue is Empty\n";
return;
}
return front->data;
}

void Display() {
Node* temp = front;
while(temp != NULL) {
cout<<temp->data<<"/n";
temp = temp->next;
}
cout<<"\n";
}

int main(){
/* Drive code to test the implementation. */
// Printing elements in Queue after each Enqueue or Dequeue
Enqueue(2); Display();
Enqueue(4); Display();
Enqueue(6); Display();
Dequeue(); Display();
Enqueue(8); Display();
}

You might also like