Stacks

Introduction
• Stack is an important data structure which stores its elements in
an ordered manner.

• Take an analogy of a pile of plates where one plate is placed on

top of the other. A plate can be removed only from the topmost
position. Hence, you can add and remove the plate only at/from
one position, that is, the topmost position.

Another plate
will be added The topmost
on top of this plate will be
plate removed first
 Stacks
• A stack is a linear data structure which uses the same principle,
i.e., the elements in a stack are added and removed only from
one end, which is called the top.

• Hence, a stack is called a LIFO (Last-In, First-Out) data structure as

the element that is inserted last is the first one to be taken out.

• Stacks can be implemented either using an array or a linked list.

 Array Representation of Stacks
• In computer’s memory stacks can be represented as a linear array.
• Every stack has a variable TOP associated with it.
• TOP is used to store the address of the topmost element of the
stack. It is this position from where the element will be added or
deleted.
• There is another variable MAX which will be used to store the
maximum number of elements that the stack can hold.
• If TOP = -1, then it indicates that the stack is empty and if TOP =
MAX -1, then the stack is full.
 Push Operation
• The push operation is used to insert an element in to 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 if this is the case then it means the stack is
full and no more insertions can further be done.
• If an attempt is made to insert a value in a stack that is already full,
an OVERFLOW message is printed.

A B C D E

0 1 2 3 TOP = 4 5 6 7 8 9

A B C D E F

0 1 2 3 4 TOP =5 6 7 8 9
 Pop Operation
• The pop operation is used to delete the topmost element from the
stack.
• However, before deleting the value, we must first check if TOP=-1,
because if this is the case then it means the stack is empty so no
more deletions can further be done.
• If an attempt is made to delete a value from a stack that is already
empty, an UNDERFLOW message is printed.
A B C D E

0 1 2 3 TOP = 4 5 6 7 8 9

A B C D

0 1 2 TOP = 3 4 5 6 7 8 9
 Peek/Peep Operation
• Peek is an operation that returns the value of the topmost
element of the stack without deleting it from the stack.
• However, the peep operation first checks if the stack is empty or
contains some elements.
• If TOP = -1, then an appropriate message is printed else the value
is returned.

A B C D E

0 1 2 3 TOP = 4 5 6 7 8 9

Here Peep operation will return E, as it is the value of the

topmost element of the stack.
 Algorithms for Push and Pop
Operations
Algorithm to PUSH an element in a stack

Step 1: IF TOP = MAX-1, then

PRINT “OVERFLOW”
Goto Step 4
[END OF IF]
Step 2: SET TOP = TOP + 1
Step 3: SET STACK[TOP] = VALUE
Step 4: END

Algorithm to POP an element from a stack

Step 1: IF TOP = -1, then

PRINT “UNDERFLOW”
Goto Step 4
[END OF IF]
Step 2: SET VAL = STACK[TOP]
Step 3: SET TOP = TOP - 1
Step 4: END
Algorithm for Peep Operation
Algorithm for Peep Operation

Step 1: IF TOP =-1, then

PRINT “STACK IS EMPTY”
Go TO Step 3
[END OF IF]
Step 2: RETURN STACK[TOP]
Step 3: END
struct stack{
int data[MAX];
int top;
}
void main()
{
struct stack s;
int value;
s.top = -1;
push(&s, 10);
--------------
value = pop(&s)
}
void push(struct stack *ps, int n)
{
if (ps->top == MAX-1)
{
printf(“Overflow”);
exit(1);
}
ps->top = ps->top + 1;
ps->data[ps->top] = n;
}
int pop(struct stack *ps)
{
int value;
if(ps->top == -1)
{ printf(“Underflow”); exit(1); }
value = ps->data[ps->top];
ps->top = ps->top -1;
return value;
}
 Linked Representation of Stacks
• In a linked stack, every node has two parts – one that stores data
and another that stores the address of the next node.

• The START pointer of the linked list is used as TOP.

• If TOP is NULL then it indicates that the stack is empty.

1 7 3 4 2 6 5 X

TOP
Push Operation on a Linked Stack
Algorithm to PUSH an element in a linked stack

Step 1: Allocate memory for the new node and name it as New_Node
Step 2: SET New_Node->DATA = VAL
Step 3: IF TOP = NULL, then
SET New_Node->NEXT = NULL
SET TOP = New_Node
ELSE
SET New_node->NEXT = TOP
SET TOP = New_Node
[END OF IF]
Step 4: END

1 7 3 4 2 6 5 X

TOP

9 1 7 3 4 2 6 5 X

TOP
Pop Operation on a Linked Stack
Algorithm to POP an element from a stack

Step 1: IF TOP = NULL, then

PRINT “UNDERFLOW”
Goto Step 5
[END OF IF]
Step 2: SET PTR = TOP
Step 3: SET TOP = TOP ->NEXT
Step 4: FREE PTR
Step 5: END

9 1 7 3 4 2 6 5 X

TOP

1 7 3 4 2 6 5 X

TOP
struct node {
int data;
struct node * next;
};
struct stack {
struct node *top;
};
int main(void) {
struct stack s; s.top=NULL;
int top_val;
push(&s,10);
---------
top_val = pop(&s);
}
void push(struct stack *ps, int n)
{
struct node *x;
x=(struct node *)malloc(sizeof(struct node))
if(x==NULL) {
printf(“Overflow”);
exit(1);
}
x->data = n;
x->next = ps->top;
ps->top = x;
}
int pop(struct stack *ps)
{
struct node *x; int value;
if(ps->top==NULL) {
printf(“Underflow”);
exit(1);
}
value = ps->top->data;
x=ps->top;
ps->top = ps->top->next;
free(x);
return value;
}
 Multiple Stacks
• When we implemented a stack using an array, we had seen that
the size of the array must be known in advance.
• If the stack is allocated less space, then frequent OVERFLOW
conditions will be encountered.
• In case, we allocate a large amount of space for the stack, it will
result in sheer wastage of memory. Thus, there lies a tradeoff
between the frequency of overflows and the space allocated.
• So a better solution to deal with this problem is to have multiple
stacks or to have more than one stack in the same array of
sufficient size.
0 1 2 3 4 ………………………………. n-4 n-3 n-2 n-1

Stack A Stack B
 Applications of Stacks
• Reversing a list

• Parentheses checker

• Conversion of an infix expression into a postfix expression

• Evaluation of a postfix expression

• Conversion of an infix expression into a prefix expression

• Evaluation of a postfix expression

• Recursion

• Tower of Hanoi