STACK
stack
➢ A stack is an ordered collection of items where the addition of
new items and the removal of existing items always take place at
the same end.
➢ This end is called as the Top of the stack
➢ The end opposite to top is known as the base
➢ Stack is a linear data structure which follows a particular order in
which the operations are performed. The order may be LIFO(last-
in first-out) or FILO( First In Last Out)
Representation of stacks
Representation using
of stacks array(conti..)
using array
• Stack can be represented using a one dimensional array
• The items into the stacks are stored in a sequential order from the first
location of the memory block
• A pointer TOP contains the location of the TOP element of the stack
• A variable MAXSTX contains the maximum number of element that
can be stored in the stack
Representation of stacks using array(conti..)
• If we attempt to add new element beyond the maximum size we will
encounter a stack overflow condition
• Similarly you cannot remove element beyond the base of the stack . If
such is the case . We will reach a stack underflow condition
• The condition TOP = MAXSTX indicates that the stack is full
• Top = NULL indicates that stack is empty
Or
• Top = -1 indicates that stack is empty
PUSH
TOP 7 1
TOP 6 19
TOP 5 15
TOP 4 18
TOP 3 2
TOP 2 7
TOP 1 12
TOP 0 10
TOP -1
STACK
POP
TOP 7 1
TOP 6 19
TOP 5 15
TOP 4 18
TOP 3 2
TOP 2 7
TOP 1 12
TOP 0 10
TOP -1
STACK
OBSERVATIONS
➢ TOP = -1 (means stack is empty)
➢ max-1 >TOP>-1 (stack is partially full)
➢ TOP = max-1 (stack is full)
TERMINOLOGY
❖Overflow: When the stack is full and we try to push an element it is
called Overflow
❖Underflow: When the stack is empty and we try to pop an element it is
called underflow
PUSH OPERATION
➢The process of adding one element or item to the stack is
represented by an operation called as the PUSH operation
➢The new element is added at the top most position of the stack
Push Algorithm
PUSH(STACK , TOP, SIZE, ITEM )
STACK is the array with N elements and TOP is the pointer to the top
element of the array. ITEM the element to be inserted.
Step 1: If TOP = MAX-1 then [check overflow]
print “ Stack is full ”
EXIT
[End if]
Step 2: TOP = TOP+1 [increment the TOP]
Step 3: STACK[TOP] = ITEM [Insert the item]
Step 4: return
#include<iostream.h> PUSH PROGRAM
#include<conio.h>
#include<process.h>
#define max 5
class stack
{
private:
int s[max],top,ele,i;
public:
stack()
{
top=-1;
}
void push() PUSH PROGRAM
{
if(top==(max-1))
{
cout<<“Stack overflow"<<endl;
}
else
{
cout<<“Enter the element to be inserted: "<<endl;
cin>>ele;
top=top+1;
s[top]=ele;
}
}
void display() PUSH PROGRAM
{
if(top==-1)
{
cout<<“Stack underflow"<<endl;
}
else
{
cout<<“The contents of the stack are "<<endl;
for(i=top;i>=0;i--)
cout<<s[i]<<endl;
}
}
}; // End of class
void main() PUSH PROGRAM
{
stack st;
int choice;
clrscr();
while(1)
{
cout<<endl<<" ------------------------------------------- "<<endl;
cout<<"1: Push"<<endl;
cout<<"2: Display"<<endl;
cout<<"3: Exit"<<endl;
cout<<“Enter your choice"<<endl;
cin>>choice;
switch(choice) PUSH PROGRAM
{
case 1: st.push();
break;
case 2: st.display();
break;
case 3: cout<<"thank you";
getch();
exit(0);
default: cout<<"invalid input!! try again"<<endl;
}
} // while loop
} // void main()
POP ALGORITHM
The process of deleting one element or item from the stack is
represented by an operation called as the POP operations
POP Algorithm
POP(STACK , TOP, ITEM)
STACK is the array with N elements. TOP is the pointer to the top
element of the array.
Step 1: if TOP = -1 or NULL then [check underflow]
print “ Stack is empty ”
EXIT
[End if]
Step 2: ITEM = STACK [TOP] [Copy the top element]
Step 3: TOP = TOP-1 [Decrement the top]
Step 4: return
#include<iostream.h> POP PROGRAM
#include<conio.h>
#include<process.h>
#define max 5
class stack
{
private:
int s[max],top,ele,i;
public:
stack()
{
top=-1;
}
void push() POP PROGRAM
{
if(top==(max-1))
{
cout<<“Stack overflow"<<endl;
}
else
{
cout<<“Enter the element to be inserted: "<<endl;
cin>>ele;
top=top+1;
s[top]=ele;
}
}
void pop() POP PROGRAM
{
if(top==-1)
{
cout<<“Stack underflow"<<endl;
}
else
{
ele=s[top];
cout<<“The popped element is: "<<ele<<endl;
top=top-1;
}
}
void display() POP PROGRAM
{
if(top==-1)
{
cout<<“Stack underflow"<<endl;
}
else
{
cout<<“The contents of the stack are "<<endl;
for(i=top;i>=0;i--)
cout<<s[i]<<endl;
}
}
};
void main() POP PROGRAM
{
stack st;
int choice;
clrscr();
while(1)
{
cout<<endl<<" ------------------------------------------- "<<endl;
cout<<"1: Push"<<endl;
cout<<"2: Pop"<<endl;
cout<<"3: Display"<<endl;
cout<<"4: Exit"<<endl;
cout<<“Enter your choice"<<endl;
cin>>choice;
switch(choice) POP PROGRAM
{
case 1: st.push();
break;
case 2: st.pop();
break;
case 3: st.display();
break;
case 4: cout<<"thank you";
getch();
exit(0);
default: cout<<"invalid input!! try again"<<endl;
}
}
}
Operations performed on stacks
➢ stack(): It creates a new stack that is empty and it needs no parameters
and returns an empty stack
➢ push(item): It Adds a new item to the top of the stack
➢ pop(): It removes the top item from the stack
➢ peek(): It Returns the top item from the stack but does not remove it
➢ isempty(): It test whether the stack is empty or not. it returns a Boolean
value
➢ size(): Returns the number of items in the stack and it returns an
integer value
Applications of stack
In a stack, only limited operations are performed because it is
restricted data structure. The elements are deleted from the stack in
the reverse order
The following are the Application of stack:
➢ Evaluation of Arithmetic Expression
➢ Reverse of data
➢ Processing Function calls
➢ Conversion of infix expression into prefix and postfix
➢ Conversion of decimal number into binary
➢ Backtracking
➢ Delimiter checking
➢ Memory Management
➢ Evaluation of Arithmetic Expression
(A+ B) * (C+D)
I II
➢ Reverse of data
You push a given word to stack - letter by letter - and then pop letters from
the stack.
P 3 POP
PUSH
M 2 M
O 1 O
C 0 C
STACK STACK
➢ Processing Function :
Main Function can only be finished after Function 1 and Function 1 can only
be finished after Function 2. As a result Main Function should begin first and
finished last . Which follows the last in first out behaviour
Main function() Function 1 () Function 2 () STACK
Function 1() Function 2()
Main() { {
{ …………… ……………
…………… …………… …………… Function 2();
…………… Function 2 (); return;
Fuction 1(); return; } Function 1();
……………. }
return; Main Function()
}
➢ Conversion of decimal number into binary
❖ Any decimal number can be converted to a binary number by continually
dividing it by two and pushing the residue(i.e. remainder) of each division
onto the stack until the result is 0.
❖ The binary counterpart of the provided decimal number is then obtained
by popping the entire stack
PUSHING
conversion : 14 / 2
ORDER
2 14 0 1 POP ORDER
2 7 1 1
2 3 1 1
2 1 1 0
0
STACK
➢ Backtracking: This is a process when you need to access the most
recent data element in a series of elements
❖ Undo/redo- mechanism in text editors; this operation is
accomplished by keeping all text changes in a stack
❖ Processing Function calls
❖ support for recursion
➢ Delimiter checking:
Compiler’s syntax check for matching braces is implemented by using
stack.
➢ Memory Managment:
Space for parameters and local variables is created internally using a
stack.
Arithmetic expression
➢ An expression is a combination of operands and operators that after
evaluation results in a single value.
➢ Operands consist of constants and variables.
➢ Operators consists of { +, - , * , / …….. etc., )
Expressions can be:
❖ Infix expression
❖ Post fix expression
❖ Prefix expression
Arithmetic expression ( conti…)
➢Infix expression: If an operator is in between two operands it is called infix
expression.
Example: a + b, where a and b are the operands and + is an operator.
➢ Postfix expression: If an operator follows the two operands it is called postfix
expression.
Example: ab +
➢ Prefix expression: If an operator precedes two operands, it is called prefix
expression.
Example: +ab
