Data Structures and Algorithms - Old Questions
3. Explain the implementation of stack and queue with example.
Stack
A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of the stack. The deletion and insertion in a stack is done from top of the stack.
It is a linear data structure which store data temporarily to perform PUSH and POP operation in LIFO (Last-In-First-Out) sequence.
Fig::A stack containing items or elements
Implementation of stack using array
#include<stdio.h>
#include<conio.h>
#define SIZE 10
void push(int);
void pop();
void display();
int stack[SIZE], top = -1;
void main()
{
int value, choice;
clrscr();
while(1){
printf("\\n\\n***** MENU *****\\n");
printf("1. Push\\n2. Pop\\n3. Display\\n4. Exit");
printf("\\nEnter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d",&value);
push(value);
break;
case 2: pop();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\\nWrong selection!!! Try again!!!");
}
}
}
void push(int value){
if(top == SIZE-1)
printf("\\nStack is Full!!! Insertion is not possible!!!");
else{
top++;
stack[top] = value;
printf("\\nInsertion success!!!");
}
}
void pop(){
if(top == -1)
printf("\\nStack is Empty!!! Deletion is not possible!!!");
else{
printf("\\nDeleted : %d", stack[top]);
top--;
}
}
void display(){
if(top == -1)
printf("\\nStack is Empty!!!");
else{
int i;
printf("\\nStack elements are:\\n");
for(i=top; i>=0; i--)
printf("%d\\n",stack[i]);
}
}
E.g.
Queue
A Queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (the rear of the queue).
Queue follows First-In-First-Out (FIFO) methodology, i.e. the first element inserted into the queue is the first element to be removed.
Implementation of Queue using array
#include<stdio.h>
#include<conio.h>
#define SIZE 10
void enQueue(int);
void deQueue();
void display();
int queue[SIZE], front = -1, rear = -1;
void main()
{
int value, choice;
clrscr();
while(1){
printf("\\n\\n***** MENU *****\\n");
printf("1. Insertion\\n2. Deletion\\n3. Display\\n4. Exit");
printf("\\nEnter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d",&value);
enQueue(value);
break;
case 2: deQueue();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\\nWrong selection!!! Try again!!!");
}
}
}
void enQueue(int value){
if(rear == SIZE-1)
printf("\\nQueue is Full!!! Insertion is not possible!!!");
else{
if(front == -1)
front = 0;
rear++;
queue[rear] = value;
printf("\\nInsertion success!!!");
}
}
void deQueue(){
if(front == rear)
printf("\\nQueue is Empty!!! Deletion is not possible!!!");
else{
printf("\\nDeleted : %d", queue[front]);
front++;
if(front == rear)
front = rear = -1;
}
}
void display(){
if(rear == -1)
printf("\\nQueue is Empty!!!");
else{
int i;
printf("\\nQueue elements are:\\n");
for(i=front; i<=rear; i++)
printf("%d\\t",queue[i]);
}
}
E.g.
