Stacks and Queue in Data Structure

Linear Data Structures – Stack & Queue
There are certain situations in computer science that one wants to
restrict insertions and deletions so that they can take place only at the
beginning or the end of the list, not in the middle. Two of such data
structures that are useful are:

Stack.
Queue.
Linear lists and arrays allow one to insert and delete elements at any
place in the list i.e., at the beginning, at the end or in the middle.


4.1. STACK:

A stack is a list of elements in which an element may be inserted or deleted only at one
end, called the top of the stack. Stacks are sometimes known as LIFO (last in, first out)
lists.

As the items can be added or removed only from the top i.e. the last item to be added
to a stack is the first item to be removed.

The two basic operations associated with stacks are:

Push: is the term used to insert an element into a stack.
Pop: is the term used to delete an element from a stack.



delete an element from the stack.

All insertions and deletions take place at the same end, so the last element added to
the stack will be the first element removed from the stack. When a stack is created, the
stack base remains fixed while the stack top changes as elements are added and
removed. The most accessible element is the top and the least accessible element is
the bottom of the stack.


4.1.1. Representation of Stack:

Let us consider a stack with 6 elements capacity. This is called as the size of the stack.
The number of elements to be added should not exceed the maximum size of the stack.
If we attempt to add new element beyond the maximum size, we will encounter a stack
overflow condition. Similarly, you cannot remove elements beyond the base of the
stack. If such is the case, we will reach a stack underflow condition.

When an element is added to a stack, the operation is performed by push(). Figure 4.1
shows the creation of a stack and addition of elements using push().

, 4 4 4 4

3 3 3 3
TOP
2 2 TOP 2 2

1 TOP 1 22 1 1

TOP 0 11 0 11 0 0
Empty
Stack 11

Figure 4.1. Push operations on stack

When an element is taken off from the stack, the operation is performed by pop().
Figure 4.2 shows a stack initially with three elements and shows the deletion of
elements using pop().


4 4 4 4

TOP 3 3 3 3
33
2 TOP 2 2 2
22 22
1 1 TOP 1 1
11 11 11 TOP
0 0 0 0
POP POP

Empty
Stack
Figure 4.2. Pop operations on stack



4.1.2. Source code for stack operations, using array:

# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
# define MAX 6
int stack[MAX];
int top = 0;
int menu()
{
int ch;
clrscr();
printf("\
printf("\n -----------**********------------------ \n");
printf("\n 1. Push ");
printf("\n 2. Pop ");
printf("\n 3. Display");
printf("\n 4. Quit ");
printf("\n Enter your choice: ");
scanf("%d", &ch);
return ch;
}
void display()
{
int i;
if(top == 0)
{
printf("\n\nStack empty..");

, return;
}
else
{
printf("\n\nElements in stack:");
for(i = 0; i < top; i++)
printf("\t%d", stack[i]);
}
}

void pop()
{
if(top == 0)
{
printf("\n\nStack Underflow..");
return;
}
else
printf("\n\npopped element is: %d ", stack[--top]);
}

void push()
{
int data;
if(top == MAX)
{
printf("\n\nStack Overflow..");
return;
}
else
{
printf("\n\nEnter data: ");
scanf("%d", &data);
stack[top] = data;
top = top + 1;
printf("\n\nData Pushed into the stack");
}
}

void main()
{
int ch;
do
{
ch = menu();
switch(ch)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;

case 4:
exit(0);
}
getch();
} while(1);
}

, 4.1.3. Linked List Implementation of Stack:

We can represent a stack as a linked list. In a stack push and pop operations are
performed at one end called top. We can perform similar operations at one end of list
using top pointer. The linked stack looks as shown in figure 4.3.

top
400
data next
40 X
400

30 400
300

20 300

start
100 10 200


Figure 4.3. Linked stack
representation


4.1.4. Source code for stack operations, using linked list:

# include <stdio.h>
# include <conio.h>
# include <stdlib.h>

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

void push();
void pop();
void display();
typedef struct stack node;
node *start=NULL;
node *top = NULL;

node* getnode()
{
node *temp;
temp=(node *) malloc( sizeof(node)) ;
printf("\n Enter data ");
scanf("%d", &temp -> data);
temp -> next = NULL;
return temp;
}
void push(node *newnode)
{
node *temp;
if( newnode == NULL )
{
printf("\n Stack Overflow..");
return;
}