Queue Implementation using Linked List in C++
#include<iostream.h>
#include<conio.h>
struct node
{
int data;
struct node *link;
};
class queue
{
struct node *front,*rear,*ptr;
public:
queue(){
rear=NULL;
front=NULL;
}
void enqueue(int);
void dqueue();
void display();
};
void queue::enqueue(int data)
{
ptr=new node;
if(rear==NULL)
{ front=ptr;
}
else
{
rear->link=ptr;
ptr->link=NULL;
}
rear=ptr;
rear->data=data;
cout<<"\n>>";
}
void queue::dqueue()
{
int item;
if(front==NULL)
cout<<"\nQueue is empty:\n";
else
{
item=front->data;
if(front==rear)
{
front=NULL;
rear=NULL;
}
else
{
ptr=front;
front=front->link;
delete ptr;
}
cout<<"deleted elmnt : "<<item;
}
}
void queue::display()
{
ptr=front;
if(front==NULL)
cout<<"\nQueue is empty";
else
{
cout<<"\nElements in queue are: ";
while(ptr!=NULL)
{
cout<<ptr->data<<"|";
ptr=ptr->link;
}
}
}
void main()
{
queue q;
int ch,data;
clrscr();
cout<<"\n........MENU..........\n";
cout<<"1 . enqueue\n";
cout<<"2 . dqueue\n";
cout<<"3 . display\n";
cout<<"4 . exit\n";
while(1)
{
cout<<"\n Enter your choice: ";
cin>>ch;
switch(ch)
{
case 1:
cout<<"\n Enter the element: ";
cin>>data;
q.enqueue(data);break;
case 2:
q.dqueue();break;
case 3:
q.display();break;
case 4:
ch=5;break;
default:
cout<<"\nInvalid selection\n";break;
}
if(ch==5)
break;
}
getch();
}
What are queues in C plus plus?
A queue in any language is a
singly-linked list structure that permits new data to be inserted only
at the end of a list while existing data can only be extracted from the
beginning of the list. Queues are also known as a first in, first out
(FIFO) structure. Unlike a standard singly-linked list, the list
maintains a pointer to the last node as well as the first, in order to
insert new data and extract existing data in constant time.
Variations on the queue include the priority queue which permit data to be weighted, such that data with the greatest priority is promoted to the front of the queue, behind any existing data with the same or higher priority, using an insertion sort technique. Insertion is therefore achieved in linear time rather than constant time, however extraction is always in constant time.
Variations on the queue include the priority queue which permit data to be weighted, such that data with the greatest priority is promoted to the front of the queue, behind any existing data with the same or higher priority, using an insertion sort technique. Insertion is therefore achieved in linear time rather than constant time, however extraction is always in constant time.
Linked Lists
The linked list is used in many libraries/applications and for a good reason. The following are advantages it has over other containers, indirectly from the reference page on cplusplus.com:
- Efficient insertion and erasure of elements anywhere in the container (constant time).
- Iterating over the elements in forward order (linear time).
- Efficient moving elements and block of elements within the container or even between different containers (constant time).
The following only applies to a doubly linked list which I will explain later on:
- Iterating over the elements in forward or reverse order (linear time).
Something the reference doesn't explain is how it's implemented. Why would you *want* to know about that? For me, simply curiosity. For others, perhaps they may create their own type of linked list container. Either way, it's knowledge that *someone* will eventually use hopefully.
Design
The linked list is generally pictured as a list of linear nodes that are tethered together somehow. In C/++, you generally have a structure which contains data and a pointer to the next structure container which contains data and a pointer to the next structure container... and so on. The linked list's main advantage is that it doesn't contain data in a contiguous way and rather, a flexible way. This allows for fast insertion and better overall iteration. The linked list is often even used as the basis for other containers (such as queue or stack containers).There are several variations of the linked-list. Actually, the term "linked list" doesn't really refer to the implementation (thus, an abstract term), just the nature of how the data of the container is held (linked via references). The most common implementation of the linked list is probably the doubly linked list. The doubly linked list is a list that contains nodes that contains references to the previous *and* next link in the list. This allows for fast node erasure, faster fetching of end nodes, and more flexible iteration.
At the cost of flexibility of the doubly-linked list, it generally costs more memory to use. In large lists, consider the idea of a node being twice the size as normal. This can affect the application quite a bit. In the case that you have no reason to iterate backwards, the doubly-linked list can be considered inefficient, simply by design. std::list is a doubly linked list. As a result, if I ever come about the need for a singly-linked list, I implement my own. A singly-linked list can only iterate forward simply because the node it holds only holds a reference to the next node in the list and not the previous but comes with the merit of one less reference.
Another type of linked-list that's not used quite as often is the circular linked-list. All this is a singly/doubly-linked list where the end node iterates forward to the beginning node (and possibly vice versa). There aren't many uses for this as it generally has problems with iterating through the list but take, for instance, a list that iterates through the nodes until a given signal is received. Also, it's really a technique used with linked lists... not always in implementation although special list implementations can handle circular linked lists better than others.
In embedded systems, the use of linked lists can be expensive. The holding of each reference can be so heavy that it's undesirable to use a linked-list with nodes that only hold one location of data. Instead, they generally used what's called unrolled linked lists. In an unrolled linked list, the node holds a reference to the next and previous, like normal, but each node holds arrays of data. When you iterate through each node, you iterate through the data in the array linearly, then move on to the next node. This way we can have three or four nodes of data in one while reducing the amount of nodes altogether (therefor saving memory). However, this generally uses contiguous memory to hold nodes so it becomes difficult to move nodes that are in the array.
