CHAPTER 5
Stacks
A simple data structure, in which insertion and deletion occur at the same end, is termed (called)
a stack. It is a LIFO (Last In First Out) structure.
The operations of insertion and deletion are called PUSH and POP
Push - push (put) item onto stack
Pop - pop (get) item from stack
Push(8) Pop
Initial Stack
TOS=> 8 Pop()
TOS=> 4 {
TOS=>
4 4
if stack not empty {
1 1 1 return the value of the top item
3 3 3 remove the top item from the stack
6 6 6 }
else {
Our Purpose: give an error message
To develop a stack implementation that does not tie us to a particular data } type or to a particular
implementation. }
CreateStack()
Implementation: {
Stacks can be implemented both as an array (contiguous list)remove
and as existing
a linked items
list. We want
from theastack
set
of operations that will work with either type of implementation: i.e. the
initialise themethod
stack toofempty
implementation is hidden and can be changed without affecting} the programs that use them.
The Basic Operations:
Push()
{
if there is room {
put an item on the top of the stack
else
give an error message
}
}
Array Implementation of Stacks: The PUSH operation
Here, as you might have noticed, addition of an element is known as the PUSH operation. So, if
an array is given to you, which is supposed to act as a STACK, you know that it has to be a
STATIC Stack; meaning, data will overflow if you cross the upper limit of the array. So, keep
this in mind.
Algorithm:
Step-1: Increment the Stack TOP by 1. Check whether it is always less than the Upper Limit of
the stack. If it is less than the Upper Limit go to step-2 else report -"Stack Overflow"
Step-2: Put the new element at the position pointed by the TOP
Implementation:
static int stack[UPPERLIMIT];
int top= -1; /*stack is empty*/
..
..
main()
{
..
..
push(item);
..
..
}
push(int item)
{
top = top + 1;
if(top < UPPERLIMIT)
stack[top] = item; /*step-1 & 2*/
else
cout<<"Stack Overflow";
}
Note:- In array implementation, we have taken TOP = -1 to signify the empty stack, as this
simplifies the implementation.
Array Implementation of Stacks: The POP operation
POP is the synonym for delete when it comes to Stack. So, if you're taking an array as the stack,
remember that you'll return an error message, "Stack underflow", if an attempt is made to Pop an
item from an empty Stack. OK.
Algorithm
Step-1: If the Stack is empty then give the alert "Stack underflow" and quit; or else go to step-2
Step-2: a) Hold the value for the element pointed by the TOP
b) Put a NULL value instead
c) Decrement the TOP by 1
Implementation:
static int stack[UPPPERLIMIT];
int top=-1;
..
..
main()
{
..
..
poped_val = pop();
..
..
}
int pop()
{
int del_val = 0;
if(top == -1)
cout<<"Stack underflow"; /*step-1*/
else
{
del_val = stack[top]; /*step-2*/
stack[top] = NULL;
top = top -1;
}
return(del_val);
}
Note: - Step-2:(b) signifies that the respective element has been deleted.
Linked List Implementation of Stacks: The PUSH operation
It’s very similar to the insertion operation in a dynamic singly linked list. The only difference is
that here you'll add the new element only at the end of the list, which means addition can happen
only from the TOP. Since a dynamic list is used for the stack, the Stack is also dynamic, means it
has no prior upper limit set. So, we don't have to check for the Overflow condition at all!
In Step [1] we create the new element to be pushed to the Stack.
In Step [2] the TOP most element is made to point to our newly created element.
In Step [3] the TOP is moved and made to point to the last element in the stack, which is our
newly added element.
Algorithm
Step-1: If the Stack is empty go to step-2 or else go to step-3
Step-2: Create the new element and make your "stack" and "top" pointers point to it and quit.
Step-3: Create the new element and make the last (top most) element of the stack to point to it
Step-4: Make that new element your TOP most element by making the "top" pointer point to it.
Implementation:
struct node{
int item;
struct node *next;
}
struct node *stack = NULL; /*stack is initially empty*/
struct node *top = stack;
main()
{
..
..
push(item);
..
}
push(int item)
{
if(stack == NULL) /*step-1*/
{
newnode = new node /*step-2*/
newnode -> item = item;
newnode -> next = NULL;
stack = newnode;
top = stack;
}
else
{
newnode = new node; /*step-3*/
newnode -> item = item;
newnode -> next = NULL;
top ->next = newnode;
top = newnode; /*step-4*/
}
}
4.4. Linked List Implementation of Stacks: The POP Operation
This is again very similar to the deletion operation in any Linked List, but you can only delete
from the end of the list and only one at a time; and that makes it a stack. Here, we'll have a list
pointer, "target", which will be pointing to the last but one element in the List (stack). Every time
we POP, the TOP most element will be deleted and "target" will be made as the TOP most
element.
In step[1] we got the "target" pointing to the last but one node.
In step[2] we freed the TOP most element.
In step[3] we made the "target" node as our TOP most element.
Supposing you have only one element left in the Stack, then we
won't make use of "target" rather we'll take help of our
"bottom" pointer. See how...
Algorithm:
Step-1: If the Stack is empty then give an alert message "Stack Underflow" and quit; or else
proceed
Step-2: If there is only one element left go to step-3 or else step-4
Step-3: Free that element and make the "stack", "top" and "bottom" pointers point to NULL and
quit
Step-4: Make "target" point to just one element before the TOP; free the TOP most element;
make "target" as your TOP most element
Implementation:
struct node
{
int nodeval;
struct node *next;
}
struct node *stack = NULL; /*stack is initially empty*/
struct node *top = stack;
main()
{
int newvalue, delval;
..
push(newvalue);
..
delval = pop(); /*POP returns the deleted value from the stack*/
}
int pop( )
{
int pop_val = 0;
struct node *target = stack;
if(stack == NULL) /*step-1*/
cout<<"Stack Underflow";
else
{
if(top == bottom) /*step-2*/
{
pop_val = top -> nodeval; /*step-3*/
delete top;
stack = NULL;
top = bottom = stack;
}
else /*step-4*/
{
while(target->next != top) target = target ->next;
pop_val = top->nodeval;
delete top;
top = target;
target ->next = NULL;
}
}
return(pop_val);