| Stack | Queue |
| A Linear List Which allows insertion or deletion of an element at one end only is called as Stack | A Linear List Which allows insertion atone end and deletion at another end is called as Queue |
| Since insertion and deletion of an element are performed at one end of the stack, the elements can only be removed in the opposite order of insertion. | Since insertion and deletion of an element are performed at opposite end of the queue, the elements can only be removed in the same order of insertion. |
| Stack is called as Last In First Out (LIFO) List. | Queue is called as First In First Out (FIFO) List. |
| The most and least accessible elements are called as TOP and BOTTOM of the stack | Insertion of element is performed at FRONT end and deletion is performed from REAR end |
| Example of stack is arranging plates in one above one. | Example is ordinary queue in provisional store. |
| Insertion operation is referred as PUSH and deletion operation is referred as POP | Insertion operation is referred as ENQUEUE and deletion operation is referred as DQUEUE |
| Function calling in any languages uses Stack | Task Scheduling by Operating System uses queue |
Queue can be implemented in two ways :
The basic operations that can be performed on queue are :
Step 1: IF REAR = MAX-1 Write OVERFLOW Goto step 4 [END OF IF] Step 2: IF FRONT=-1 and REAR=-1 SET FRONT = REAR = 0 ELSE SET REAR = REAR+1 [END OF IF] Step 3: SET QUEUE[REAR] = NUM Step 4: EXIT
In this algorithm to insert an element in a queue.
Step 1: IF FRONT = -1 OR FRONT > REAR Write UNDERFLOW ELSE SET VAL = QUEUE[FRONT] SET FRONT = FRONT+1 [END OF IF] Step 2: EXIT
In this algorithm to delete an element from a queue.
Write a program to implement a linear queue.
#include<stdio.h>
#include<conio.h>
#define MAX 10 // Changing this value will change length of array
int queue[MAX];
int front = -1, rear = -1;
void insert(void);
int delete_element(void);
int peek(void);
void display(void);
int main()
{
int option, val;
do
{
printf(“\n\n ***** MAIN MENU *****”);
printf(“\n 1. Insert an element”);
printf(“\n 2. Delete an element”);
printf(“\n 3. Peek”);
printf(“\n 4. Display the queue”);
printf(“\n 5. EXIT”);
printf(“\n Enter your option : “);
scanf(“%d”, &option);
switch(option)
{
case 1:
insert();
break;
case 2:
val = delete_element();
if (val != -1)
printf(“\n The number deleted is : %d”, val);
break;
case 3:
val = peek();
if (val != -1)
printf(“\n The first value in queue is : %d”, val);
break;
case 4:
display();
break;
}
}
while(option != 5);
getch();
return 0;
}
void insert()
{
int num;
printf(“\n Enter the number to be inserted in the queue : “);
scanf(“%d”, &num);
if(rear == MAX-1)
printf(“\n OVERFLOW”);
else if(front == -1 && rear == -1)
front = rear = 0;
else
rear++;
queue[rear] = num;
}
int delete_element()
{
int val;
if(front == -1 || front>rear)
{
printf(“\n UNDERFLOW”);
return -1;
}
else
{
val = queue[front];
front++; if(front > rear)
front = rear = -1;
return val;
}
}
int peek()
{
if(front==-1 || front>rear)
{
printf(“\n QUEUE IS EMPTY”);
return -1;
}
else
{
return queue[front];
}
}
void display()
{
int i;
printf(“\n”);
if(front == -1 || front > rear)
printf(“\n QUEUE IS EMPTY”);
else
{
for(i = front;i <= rear;i++)
printf(“\t %d”, queue[i]);
}
}
Output ***** MAIN MENU *****"
1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 1
Enter the number to be inserted in the queue : 50