Stack
In
Data Structure
1
☻A stack is an ordered list in which all insertions and deletions are
made at one end, called the top”. stacks are referred to as Last In
First Out (LIFO) lists. FILO: Refers to the first in, last out
Equivalent to LIFO
have some useful terminology associated with them:
Push(item): To add an element to the stack
Pop(): To remove an element from the stock
Peek(): Copy top stack Items to User but not delete from stack
isEmpty: Return true is stack empty else return false
isFull(): Return true is stack full else return false
2
3
Implementation
☻Stacks can be implemented both as
an array (contiguous list) and as a
Push()
linked list. with either type of implementation: i.e. the method{ of implementation is hidden
and can be changed without affecting the programs that ifuse them. is room
there
☻ We want a set of operations that {
put an item on the top of the
will work with either type of stack
implementation: i.e. the method of }
else
implementation is hidden and can {
give an error message
be changed without affecting the }
}
programs that use them. 4
Pop()
{
if stack not empty
{
return the value of the top item to user and
remove the top item from the stack
}
else
{
give an error message(Stack is Underflow)
}
}
5
Array Implementation of a stack
☻
Stack has at least the following operation:
Void push()
Push (): Implementation
{
int var[n];
if(top==UpperLimit)
cout<<“Stack is overflow”;
else
{
for(int i=0; i<=n-1; i++)
{
cin>>Var[i];
top=top+1;
Stack[top]=var[i];
}
}
}
Diplay top items : Void Display_top_Item()
Implementation {
if(top==-1)
cout<<“Stack is Empty/Underflow”;
else
cout<< Stack[top];
}
Void Display_All_In_forWard()
forward: Implementation
Display all items in {
if(top==-1)
cout<<“Stack is Empty/Underflow”;
else
{
for(int i=bottom; i<=top; i++)
{
cout<<Stack[i]<<endl;
}
}
}
Void pop()
Pop(): Implementation {
if(top==-1)
cout<<“Stack is Empty/Underflow”;
else
{
cout<<Stack[top]<<endl;
top=top-1;
}
}
Applications
of
Stacks
Evaluation of Algebraic Expressions
☻Re-expressing the Expression
In order to solve arithmetic expressions, computers
restructure them so that the results of each computation
are incorporated within the expression. Once
transformed, an expression can be solved in one step.
Types of Expression
The normal (or human) way of expressing mathematical expressions is
called infix form,
e.g. 4+5*5.
However, there are other ways of representing the same expression, either
by writing all operators before their operands or after them,
e.g.
455*+
+4*55
This method is called Polish Notation (because this method was
discovered by the Polish mathematician Jan Lukasiewicz).
When the operators are written before their
operands, it is called the prefix form
e.g. +4*55
When the operators come after their operands, it is
called postfix form (suffix form or reverse polish
notation)
e.g. 455*+
☻ The valuable aspect of RPN (Reverse Polish Notation or postfix)
Parentheses are unnecessary
Easy for a computer (compiler) to evaluate an arithmetic expression
Postfix (Reverse Polish Notation)
Postfix notation arises from the concept of post-order traversal of an
expression tree (see - this concept will be covered when we look at
trees).
For now, consider postfix notation as a way of redistributing operators in
an expression so that their operation is delayed until the correct time.
Purpose
Infix notation cannot be used to evaluate expressions
in high level languages.
To decide how to assess an expression, we must first
analyse it.
An approach that is frequently used is to transform an
infix notation into postfix notation before evaluating it.
Syntax
Operands are immediately sent to the output.
The stack is pushed using operators, including parentheses.
Determine whether the current operator is less than the stack top
operator, If the top operator is less than, place the current operator on
the stack.
Current operator is pushed onto the stack and the top operator is
popped if the top operator is bigger than (or equal to) the current.
Pop from the stack until we find a matching left parenthesis if we come
across a right parenthesis. Don't print parentheses.
Operator Priority in Order of Precedence:
1. parentheses
