Stacks
A stack is a linear data structure in which data can be added or removed from one end only. These structures are useful when one has to restrict the random use of data.
PUSH : TO ADD AN ELEMENT IN THE STACK
POP : REMOVING AN ELEMENT FROM THE STACK
|
Stack is a Last In First Out data structure and is implemented using linked lists or arrays as per the requirement of the user. It can be assumed like a pile of files kept one over another in a box and only the new files can be kept on the top while if one has to remove the file then the top most file needs to be removed. Stacks are
sometimes also called as push down lists. Therefore, the element added first in the stack would be the last one to be removed while the value added in the last would be the first one to be removed. Due to this reason stacks are called LIFO structure.
Features of Stacks :-
- PUSH and POP are the terms used specifically for stacks.
- The process of adding a value/ element in the stack is called push operation while removing an element/ value from a stack is called pop operation. Consider a stack of books as shown :
Similarly if we consider a stack of numbers then following examples shows pushing a value 200 onto a stack
Pushing value 200------Ã
|
200
|
ß Top of the stack
|
300
| ||
500
| ||
100
|
- A stack data structure can be implemented using array or linked list depending the requirement.
- As insertion and deletion is done from top only therefore only one element may be inserted or deleted at a time and the complete list of elements need not be traversed.
- Stack Underflow is a situation when stack is empty and we try to remove an element from the stack.
- In case the array holding stack elements is full and we try to insert an element then such a situation is called stack overflow. Theoretically stack never overflows as there is not restriction to its size but practically the size of stack is limited by the size of array. In case of linked list, the size of stack is controlled by the size of memory available.
Implementation of Stack using an Array
Since -1 is not a valid array index value threfore, it may be used to indicate blank stack.
Top is initialized with a value -1 when stack is implemented using arrays.
Pushing (Addition) of an element onto the stack increments the value of variable top by 1.
Top=top+1;
Popping an element from the stack decrements the value of top by 1.
Top=top-1;
Following example illustrates the implementation of stack using arrays. A class ‘stack’ is declared with following members :
Top - top keeps a track of the topmost element of the stack.
Val[10] – this array can store upto 10 elements in the stack.
push() – this function adds a new element at the top of the stack
pop() – this function removes the topmost value from the stack
traverse() – this function displays the contents of the stack.
#include<iostream.h>
class stack
{
int top, val[10];
public :
stack()
{ top=-1; //val=0;
}
void push()
{
if(top<9)
{ cout<<"\n enter the value to be pushed : ";
cin>>val[++top]; }
else
cout<<" stack overflow ";
}
void pop()
{
if(top==-1)
cout<<"\n value popped is : "<<val[top--];
else
cout<<"\n stack is empty ";
}
void traverse()
{
for(int i=top;i>=0;i--)
cout<<endl<<val[i];
}
};
void main()
{
stack s;
char ch='y';
int m=0;
while (ch=='y')
{
cout<<"\n Enter your choice :";
cout<<"\n 1.Push \n 2. Pop \n 3.Traverse 4. Exit ";
cin>>m;
switch(m)
{
case 1 : s.push();
break;
case 2 : s.pop();
break;
case 3 : s.traverse();
break;
case 4 : cout<<"\n Exiting....";
break;
default : cout<<"\n Wrong choice :";
}
cout<<"\n Want to continue ??? ";
cin>>ch;
}
cout<<"\n Bye Bye ";
getch();
}
Applications of stacks:
Evaluation of Expressions in stacks
We have been learning to write arithmetic expression by having operator in the middle of the operands.
Jan Lukasiewicz, a Polish mathematician developed two notations of writing an arithmetic expression: Polish Notation (Prefix notation ) and Reverse Polish Notation (Post Fix Notation).
Arithmetic expressions may be written in three notations :-
- Infix notation : the operator is being written within the operands .
eg : expression to find sum of two numbers X and Y is : X+Y
- Prefix notation : the operator is written before the set of operands. This notation is8i also known as Polish Notation.
eg. expression to find sum of two numbers X and Y is : + XY
- Postfix Notation : the operator is followed by set of operands. Also called as reverse Polish notation.
Eg. Expression to find sum of two numbers is written as X,Y,+
The expressions having more than one operators are broken into smaller expressions based on the operator precedence and then every smaller unit is converted into postfix notation. Let us understand it more clearly using an example.
Infix
|
Postfix
| |
A + B
|
A B +
| |
A* B
|
A B *
| |
A* B + C
|
((A*B) + C)Ã (A B * ) + C
|
A B * C +
|
Now we will learn conversion of Infix expression to postfix
A simple way of converting an infix notation to a postfix notation is parenthesizing the expression. With the help of parenthesis a complex expression can be easily converted into many sub-expressions. Each sub-expression involving only two operands
Algorithm to convert infix expression into postfix expression :
Assume F as an arithmetic expression in infix notation. POSTFIX is the stack to hold the expression in postfix form. OPR is the stack to hold the operators.
1. Start
2. Push “(“ into stack and add “)” to the end of expression F.
3. Read the first element of the expression from first position ( from left).
4. If the element is an operand, push the element into the stack POSTFIX.
5. If element found is a left parenthesis is , push it into the stack OPR.
6. If it is an operator , then
a. If this operator has lower or same precedence than the element at the top of stack OPR, pop out the contents the stack OPR repeatedly and push it onto the stack POSTFX.
b. If the operator has higher precedence than the element at the top of stack OPR , simply push the element to the stack OPR.
7. If a right parenthesis is found, then
a. Pop operators from stack OPR till a left parenthesis is popped.
b. Remove the left parenthesis.
8. If stack OPR is not empty then go to step 3
9. Exit
Let us understand this algorithm with the help of an example. Consider the following expression F
F= (A + B) *C – D /E F
Symbol
|
Stack OPR
|
POSTFIX Expression
|
(
| ||
(
|
((
| |
A
|
((
|
A
|
+
|
((+
|
A
|
B
|
((+
|
AB
|
)
|
(
|
AB+
|
*
|
(*
|
AB+
|
C
|
(*
|
AB+C
|
-
|
(-
|
AB+C*
|
(
|
(-
|
AB+C*
|
D
|
(-
|
AB+C*D
|
/
|
(-/
|
AB+C*D
|
E
|
(-/
|
AB+C*DE
|
(-/
|
AB+C*DE
| |
F
|
(-/
|
AB+C*DEF
|
)
|
AB+C*DEF/-
|
Example1:
A + B /C +D * (E+ F)/G - H
Symbol
|
Stack OPR
|
POSTFIX Expression
|
(
| ||
A
|
(
|
A
|
+
|
(+
|
A
|
B
|
(+
|
AB
|
/
|
(+/
|
AB
|
C
|
(+/
|
ABC
|
+
|
(++
|
ABC/
|
D
|
(++
|
ABC/D
|
*
|
(++*
|
ABC/D
|
(
|
(++*(
|
ABC/D
|
E
|
(++*(
|
ABC/DE
|
+
|
(++*(+
|
ABC/DE
|
F
|
(++*(+
|
ABC/DEF
|
)
|
(++*
|
ABC/DEF+
|
/
|
(++*(
|
AB+C*DEF/-
|
)
|
AB+C*DEF/-
|
Evaluation of a postfix expression
As we have learnt to convert an infix notation into postfix notation, we will now learn to evaluate a postfix expression
Algorithm
- Start
- Declare a stack STK for storing the operands.
- Scan the expression from left to right and repeat steps 3 to 5 for each element of the expression until end is reached.
- If the element is an operand OPTR, put it onto the stack STK,
- If it is an operator
- Pop out two values from stack, if the top most value popped is N and the next top value is M then evaluate it as M OPTR N.
- Push the result back onto the Stack STK.
- Display the top element of the STK as the answer.
Consider the following expression in postfix form
2,3,4,*,2,4,+,-,+
Put the bracket
Expression
|
Operation
|
Stack
|
2
|
Push
|
2
|
3
|
Push
|
2,3
|
4
|
Push
|
2,3,4
|
*
|
Pop 4 and 3
3*4=12
Push 12
|
2,12
|
2
|
Push
|
2,12,3
|
4
|
Push
|
2,12,2,4
|
+
|
Pop 4 and 2
2+4=6
Push 6
|
2,12,6
|
-
|
Pop 8 and 12
12-6=6
Push 6
|
2,6
|
+
|
Pop 6 and 2
2+6=6
Push 6
|
6
|
Pop the only value 6 in the stack as the answer.
| ||
No comments:
Post a Comment