Heading

Queue is an ordered linear data structure in which insertions are done at one end and deletions at the other end. In a queue, the element which is inserted first is deleted first. The queue is also called First In First Out (FIFO) or Last In Last Out list. A queue has two pointers front and rear. Insertion is done at the rear end, and deletion is done at the front end.

Enqueue
Inserting an element at the rear end of the queue is called Enqueue operation.
Algorithm
Procedure Enqueue
if rear == N:
Queue Full (Overflow)
else:
rear = rear + 1
Queue[rear] = data
end Procedure
Explanation:
1.Check if the queue is full
2.If the Queue is full, then it indicates overflow condition. So, a new element cannot be inserted into the queue
3.If the Queue is not full, then increment rear pointer by 1 and insert the data into the queue.
Dequeue
Removing an element from the front end of the queue is called dequeue operation.
Algorithm
Procedure Dequeue
if front == -1:
Queue Empty (Underflow)
else:
front = front + 1
end Procedure
Explanation
1.Check if the queue is empty (front==-1)
2.If the Queue is Empty, then generate an underflow error.
3.If the Queue is not Empty, then increment the front pointer by 1.

Time Complexity of Queue Operations
Enqueue :
In a linear queue, the enqueue operation takes O(1) time. Because, during the enqueue operation, the rear pointer is incremented and the element in inserted. It does not involve any shifting or traversal of elements.
Dequeue :
In a linear queue, the dequeue operation takes O(1) time. Because, the dequeue operation does not involve any shifting operations.
Peek :
The peek operation returns the element pointer by the front pointer without removing it. Hence, the time complexity of the peek operation is O(1)

A priority queue is a queue in which each element in the queue has a priority associated with it. The element with the highest priority is dequeued first and that with the least priority is dequeued at last. An element with higher priority will be removed from the queue before all the other elements which have lower priority than that element. If two elements have the same priority, the element which entered the queue first will be served first.
Example:
Consider the elements with the highest value has the highest priority.
Following are the elements to be inserted into the queue:
10 5 2 7 40 16
In the above example, 40 has the highest priority and hence it will be dequeued first. 2 has the lowest priority.

Queues can be implemented using two stacks (s1 and s2). There are two methods of implementing a queue using a stack. They are:
a.Making ENQUEUE operation costly
ENQUEUE
If the stack s1 is not empty, move all the elements from s1 to s2. Then, push the new element into s1. Finally, push all the elements from s2 to s1.
DEQUEUE
Pop an element from s1.
b.Making DEQUEUE operation costly
ENQUEUE
Push an element into s1.
DEQUEUE
If both s1 and s2 are empty, dequeue operation cannot be done. If both s1 and s2 are not empty, then push all the elements from s1 to s2. Then, pop the top element from s2. Now, again move all the elements in s2 to s1 (this can be done by just inter-changing the names of the stacks).

The C implementation of the second method is given below:
C Code
#include <stdio.h>
#include <stdlib.h>

struct sNode {
int data;
struct sNode* next;
};
void push(struct sNode** top_ref, int new_data);
int pop(struct sNode** top_ref);

struct queue {
struct sNode* stack1;
struct sNode* stack2;
};

void enQueue(struct queue* q, int x)
{
push(&q->stack1, x);
}

int deQueue(struct queue* q)
{
int x;

//If both stacks are empty then error
if (q->stack1 == NULL && q->stack2 == NULL) {
printf("Q is empty");
getchar();
exit(0);
}

// Move elements from stack1 to stack 2 only if
stack2 is empty
if (q->stack2 == NULL) {
while (q->stack1 != NULL) {
x = pop(&q->stack1);
push(&q->stack2, x);
}
}

x = pop(&q->stack2);
return x;
}

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
/* allocate node */
struct sNode* new_node = (struct sNode*)malloc(sizeof(struct sNode));
if (new_node == NULL) {
printf("Stack overflow \n");
getchar();
exit(0);
}

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*top_ref);

/* move the head to point to the new node */
(*top_ref) = new_node;
}

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
int res;
struct sNode* top;

/*If stack is empty then error */
if (*top_ref == NULL) {
printf("Stack underflow \n");
getchar();
exit(0);
}
else {
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}

int main()
{
struct queue* q = (struct queue*)malloc(sizeof(struct queue));
q->stack1 = NULL;
q->stack2 = NULL;
enQueue(q, 1);
enQueue(q, 2);
enQueue(q, 3);
printf("%d ", deQueue(q));
printf("%d ", deQueue(q));
printf("%d ", deQueue(q));

return 0;
}

Stacks can be implemented using two queues (Q1 and Q2) in two different ways:
Making PUSH operation costly
PUSH
Ensure that a new item which is inserted is always inserted at the front end of the queue. For this, if Q1 is not empty, then move all the elements from Q1 to Q2. Now, insert the new element into Q1. Finally, move all the elements from Q1 to Q2
POP
Pop operation can be performed just by removing the front element in Q1.

C Code
#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node * next;
};

struct queue
{
struct node *rear;
struct node *front;
};

void initial(struct queue *);
void qadd(struct queue *,int);
int qdel(struct queue *);
void dis(struct queue *);
void push(int);
void pop();

struct queue q1,q2;
int main()
{
initial(&q1);
initial(&q2);
push(5);
push(6);
push(7);
pop();
printf("\nelements now are:\n");
display(&q1);

return 0;
}

void initial(struct queue *q)
{
q->front=NULL;
q->rear=NULL;
}

void qadd(struct queue *q,int n)
{
struct node *tmp;
tmp=(struct node *)malloc(sizeof(struct node));

tmp->data=n;
tmp->next=NULL;

if(q->front==NULL)
{
q->rear=tmp;
q->front=tmp;
return;
}

q->rear->next=tmp;
q->rear=tmp;
}

int qdel(struct queue *q)
{
struct node *tmp;
int itm;
if(q->front==NULL)
{
printf("\nqueue is empty");
return NULL;
}

//itm=q->front->data;
tmp=q->front;
itm=tmp->data;
q->front=tmp->next;
free(tmp);
return itm;

}

void display(struct queue *q)
{
struct node *tmp;
tmp=q->front;
while((tmp)!=NULL)
{
printf("\n%d",(tmp->data));
tmp=tmp->next;
}
printf("\n");
}


void push(int val)
{
struct queue tmp;
int j;
qadd(&q2,val);

while(((&q1)->front)!=NULL)
{
j=qdel(&q1);
qadd(&q2,j);
}


tmp=q1; //swap q1 and q2
q1=q2;
q2=tmp;

printf("\nelements after pushing are:\n");
display(&q1);

}

void pop()
{
printf("\n element deleted is %d",qdel(&q1));
}
Making POP operation costly
PUSH
Insert the new element at the rear of Q1.
POP
Move all the elements in Q1 to Q2 except the last element. Now, remove the last element in Q1. Then, move all the elements in Q2 to Q1.
This method can be implemented in C language in the same way as that of the before method.

A circular queue is similar to that of a normal queue, but the last position is connected back to the first position. This forms a circle, hence called circular queue.

In a normal queue, after some elements are dequeued, those positions cannot be used again. They go unused. To overcome this problem, the concept of circular queue was introduced.
To insert an element into the queue, rear is not just incremented, but (rear+1)%N operation is performed (N is the size of the queue)
Similarly, to dequeue an element from the queue, the (front-1)%N operation is performed, so that the front pointer points to the next element to be deleted.