Stack's & Queue's

Data Structures



UNIT-II
Stacks
• A stack is an ordered collection of items into which new item may be inserted and from
which items may be deleted at one end, called the top of the stack.
• The most important attribute of a stack is the last element inserted into the stack is the
first deleted element. So, stack is sometimes called a Last-In-First-Out (LIFO) list.
• When an item is added to a stack, it is called pushed into a stack and when an item is
removed from the stack, it is called pop from the stack.
• Given a stack S and an item i, the operation push(S, i) means add the item i to the top of
the stack S. the operation i = pop(S) means remove the element at the top of stack S and
assign its value to i.




Array representation of stack:
A stack is declared as a structure containing two objects
1. An array to hold the elements of the stack.
2. Stack pointer is an integer (top) to indicate the position of the current stack top within
the array.
The declaration of the stack is
struct stack
{
int top;
int items[20];
};
struct stack s;
Initially take s.top = -1.




K SRINIVAS DEPT OF IT SRKREC 1

,Data Structures




Stack operations:
Empty Stack:
The empty stack contains no elements. Therefore top=-1.
The procedure is
int empty ( struct stack *s)
{
if (s→top = = -1)
return 1;
else
return 0;
}


Pop operation:
The pop operation performs the following three actions.
1. If the stack is empty, print a warning message and halt the execution.
2. Remove the top element from the stack.
3. Return this element to the calling function.
The procedure is
int pop ( struct stack *s)
{
int a;
if (s→top = = -1)
return -1;
else
{
a = s→items[s→top];
s→top--;
return a;
}
}

Push operation:
The push operation is used to insert an element into the stack. The new element is added at the
topmost position of the stack. However, before inserting the value, we must first check if TOP =
MAX – 1, because in this case the stack is full and no more insertions can be done. If an attempt
is made to insert a value in a stack that is already full, an OVERFLOW message is printed.


The procedure is
void push(struct stack *s, int a)
{

K SRINIVAS DEPT OF IT SRKREC 2

,Data Structures


if(s→top = = MAX-1)
printf(“\nStack is OVERFLOW\n”);
else
{
s→top++;
s→items[s→top] = a;
}
}

Peek operation:
Peek is an operation that return the value of the topmost element of the stack without deleting it
from the stack.
The procedure is
int peek(struct stack *s)
{
int a;
if (s→top = = -1)
return -1;
else

{
a = s→items[s→top];
return a;
}
}


Program stack operations using array
/*stack operations using arrays*/
#define max 10
#include<stdio.h>
struct stack
{
int top;
int items[max];
};
void push(struct stack *, int a);
int pop(struct stack *);
int empty(struct stack *);
int peek(struct stack *);
void display(struct stack *);
main()
{

K SRINIVAS DEPT OF IT SRKREC 3

, Data Structures


int choice,x;
struct stack s;
s.top=-1;
while(1)
{
printf("\n\n***************************\n\n");
printf("\t\tMENU\n");
printf("\n***************************\n");
printf("1.push\n2.pop\n3.empty\n4.peek\n5.display\n6.exit\n");
printf("Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:printf("\nEnter the element:");
scanf("%d",&x);
push(&s,x);
break;
case 2: x=pop(&s);
if(x==-1)
printf("\nstack is underflow");
else
printf("\ndeleted element is %d",x);
break;
case 3: x=empty(&s);
if(x==1)
printf("\nstack is empty");
else
printf("\nstack is not empty");
break;
case 4: x=peek(&s);
if(x==-1)
printf("\nStack is empty");
else
printf("\nTop of stack element:%d",x);
break;
case 5: printf("\nElements are\n");
display(&s);
break;
case 6: exit(0);
}
}
}


K SRINIVAS DEPT OF IT SRKREC 4