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
