Stack
In computer science, a stack is a
last in, first out (LIFO) data structure. A stack can is characterized
by only two fundamental operations: push and pop. The push
operation adds an item to the top of the stack. The pop operation removes an
item from the top of the stack, and returns this value to the caller.
Stack using array
#include<iostream.h>
const int size = 5
class stack
{
int a[size]; //array a can store maximum 5
item of type int of the stack
int top; //top will point to the last item pushed onto
the stack
public:
stack( ) //constructor to create an empty stack,
top=-1 indicate that no item is
{top = -1 ;} //present in the array
void push(int item)
{
If(top==size-1)
cout<<”stack is full, given
item cannot be added”;
else
a[++top]=item; //increment
top by 1 then item at new position of the top in //the array a
}
int pop()
{
If (top==-1)
{
out<<”Stack is empty “;
return -1; //-1 indicates empty
stack
}
else
return a[top--];//return the item
present at the top of the stack then decrement top by 1
}
};
void main()
{
stack s1;
s1.push(3);
s1.push(5);
cout<<s1.pop()<<endl;
cout<<s1.pop()<<endl;
cout<<s1.pop();
}
Output is
5
3
Stack is empty -1
Linked list
In Computer Science, a linked
list (or more clearly, "singly-linked list") is a data structure
that consists of a sequence of nodes each of which contains data and a pointer
which points (i.e., a link) to the next node in the sequence.
Stack
implementation using linked list
#include<iostream.h>
struct node
{
int item; //data that will be stored in each node
node * next; //pointer which contains address
of another node
}; //node
is a self-referential structure which contains reference of another object type
node
class stack
{
node *top;
public:
stack() //constructor to create an empty stack by initializing
top with NULL
{ top=NULL; }
void push(int item);
int pop();
~stack();
};
void stack::push(int item) //to insert a new node at the top of the stack
{
node *t=new node; //dynamic memory allocation for
a new object of node type
if(t==NULL)
cout<<”Memory not
available, stack is full”;
else
{
t->item = item;
t->next = top; //newly created node will point to
the last inserted node or NULL if
//stack is empty
top=t; //top will point to the newly created node
}
}
int stack::pop() //to
delete the last inserted node(which is currently pointed by the top)
{
if(top==NULL)
{
cout<<”Stack is empty \n”;
return 0; // 0 indicating that stack is empty
}
else
{
node *t=top; //save the address of top in t
int r=top->item; //store item of the node currently
pointed by top
top=top->next; // move top from last node to the
second last node
delete t; //remove last node of the stack from memory
return r;
}
}
stack::~stack() //de-allocated
all undeleted nodes of the stack when stack goes out of scope
{
node *t;
while(top!=NULL)
{
t=top;
top=top->next;
delete t;
}
};
void main()
{
stack s1;
s1.push(3);
s1.push(5);
s1.push(7);
cout<<s1.pop()<<endl;
cout<<s1.pop()<<endl;
cout<<s1.pop()<<endl;
cout<<s1.pop()<<endl;
}
Output is
7
5
3
Stack is empty 0
Application of stacks in infix
expression to postfix expression conversion
Infix expression operand1 operator operand2 for example a+b
Postfix expression operand1 operand2 operator for example ab+
Prefix expression operator operand1 operand2 for example +ab
Some example of infix expression
and their corresponding postfix expression
Infix expression postfix expression
a*(b-c)/e abc-*e/
(a+b)*(c-d)/e ab+cd-*e/
(a+b*c)/(d-e)+f abc*+de-/f+
Algorithm to
convert infix expression to postfix expression using stack:-
Suppose x is an infix expression
and find postfix expression Y
1.
Push “(“ to the STACK, and add “)”
to the end of X.
2.
Scan X from left to right and REPEAT Steps 3 to 6 for each element of X
UNTIL the STACK is empty.
3.
If an operand is encountered, add it to Y.
4.
If a left parenthesis is encountered, push it on to STACK.
5.
If an operator is encountered then:
(a)
Repeatedly pop from STACK and add to Y each operator which has the same
precedence as or higher precedence than operator.
(b)
Add operator to STACK.
6.
If a right parenthesis is
encountered. Then:
(a)
Repeatedly pop from the STACK and add to Y each operator until a left
parenthesis is encountered.
(b)
Remove the left parenthesis.
7.
End
For example convert the infix expression (A+B)*(C-D)/E
into postfix expression showing stack status after every step.
Symbol scanned from infix
|
Stack status
|
Postfix expression
|
|
(
|
|
(
|
((
|
|
A
|
((
|
A
|
+
|
((+
|
A
|
B
|
((+
|
AB
|
)
|
(
|
AB+
|
*
|
(*
|
AB+
|
(
|
(*(
|
AB+
|
C
|
(*(
|
AB+C
|
-
|
(*(-
|
AB+C
|
D
|
(*(-
|
AB+CD
|
)
|
(*
|
AB+CD-
|
/
|
(/
|
AB+CD-*
|
E
|
(/
|
AB+CD-*E
|
)
|
|
AB+CD-*E/
|
Answer: Postfix expression of (A+B)*(C-D)/E is AB+CD-*E/
|
|
Evaluation of Postfix expression
using Stack
Algorithm to evaluate a postfix expression P.
/*Reading of expression takes place from left to
right*/
1.
Read the next element //First
element for the first time
2.
If element is an operator then push the element in the Stack
3.
If the element is an operator then
{
4.
Pop two operands from the stack //pop
one operator in case of unary operator
5.
Evaluate the expression formed by the two operands and the operator
6.
Push the result of the expression in the stack.
}
7.
If no-more-elements then
Pop
the result
Else
Go to step 1.
8.
End.
Example1: Evaluate the following postfix
expression showing stack status after every step
8, 2, +, 5, 3, -, *, 4 /
token scanned from
postfix expression
|
Stack status after processing
the scanned token
|
Operation performed
|
8
|
8
|
Push 8
|
2
|
8, 2
|
Push 2
|
+
|
10
|
Op2=pop() i.e 2
Op1=pop() i.e 8
Push(op1+op2) i.e. 8+2
|
5
|
10, 5
|
Push(5)
|
3
|
10, 5, 3
|
Push(3)
|
-
|
10, 2
|
Op2=pop() i.e. 3
Op1=pop() i.e. 5
Push(op1-op2) i.e. 5-3
|
*
|
20
|
Op2=pop() i.e. 2
Op1=pop() i.e. 10
Push(op1-op2) i.e. 10*2
|
4
|
20, 4
|
Push 4
|
/
|
5
|
Op2=pop() i.e. 4
Op1=pop() i.e. 20
Push(op1/op2) i.e. 20/4
|
NULL
|
Final result 5
|
Pop 5 and return 5
|
Example2:Evaluate the following Boolean
postfix expression showing stack status after every step
True, False, True,
AND, OR, False, NOT, AND
token scanned from
postfix expression
|
Stack status after processing
the scanned token
|
Operation performed
|
True
|
True
|
Push True
|
False
|
True, False
|
Push False
|
True
|
True, False, True
|
Push True
|
AND
|
True, False
|
Op2=pop() i.e. True
Op1=pop() i.e. False
Push(Op2 AND Op1) i.e. False
ANDTrue=False
|
OR
|
True
|
Op2=pop() i.e. False
Op1=pop() i.e. True
Push(Op2 OR Op1) i.e. True OR
False=True
|
False
|
True, False
|
Push False
|
NOT
|
True, True
|
Op1=pop() i.e. False
Push(NOT False) i.e. NOT
False=True
|
AND
|
True
|
Op2=pop() i.e. True
Op1=pop() i.e. True
Push(Op2 AND Op1) i.e. True AND
True=True
|
NULL
|
Final result True
|
Pop True and Return True
|
QUEUE
Queue is a linear data structure
which follows First in First out (FIFO) rule in which a new item is added at
the rear end and deletion of item is from the front end
of the queue. In a FIFO data structure, the first
element added to the queue will
be the first one to be removed. Linear Queue implementation using Array
#include<iostream.h>
const int size=5; //
size of queue
class queue
{ int
front , rear;
int a[size];
public:
queue() //Constructor to create an empty queue
{ front=0;
rear=0;
}
void addQ( ) // insertion in array queue
{ if(rear==size)
cout<<”queue is
full<<endl;
else
a[rear++]=item;
}
int delQ( ) // deletion from the array
queue
{ if(front==rear)
{
cout<<”queue is
empty”<<endl;
return 0;
}
else
return a[front++];
}
};
void main()
{
queue q1;
q1.addQ(3);
q1.addQ(5) ;
q1.addQ(7) ;
cout<<q1.delQ()<<endl
;
cout<<q1.delQ()<<endl
;
cout<<q1.delQ()<<endl;
cout<<q1.delQ()<<endl;
}
Output is
3
5
7
Queue is empty 0
Queue using linked list
#include<iostream.h>
struct node
{ int
item;
node *next;
};
class queue
{ node
*front, *rear;
public:
queue( ) // constructor to create empty
queue
{ front=NULL;
rear=NULL;
}
void addQ(int item);
int delQ();
};
void queue::addQ(int item)
{ node
* t=new node;
t->item=item;
t->next=NULL;
if (rear==NULL) //if the queue is empty
{ rear=t;
front=t; //rear and front both will point to the first node
}
else
{ rear->next=t;
rear=t;
}
}
int queue::delQ()
{ if(front==NULL)
cout<<”queue is
empty”<<return 0;
else
{ node
*t=front;
int r=t->item;
front=front->next; //move
front to the next node of the queue
if(front==NULL)
rear==NULL;
delete t;
return r;
}
}
void main()
{ queue
q1;
q1.addQ(3);
q1.addQ(5) ;
q1.addQ(7) ;
cout<<q1.delQ()<<endl
;
cout<<q1.delQ()<<endl
;
cout<<q1.delQ()<<endl;
cout<<q1.delQ()<<endl;
}
2,3 & 4 Marks
Practice Questions
1. Convert the following infix
expressions to postfix expressions using stack 2
(i)
A + (B * C) ^ D – (E / F – G)
(ii)
A * B / C * D ^ E * G / H
(iii)
((A*B)-((C_D)*E/F)*G
2. Evaluate the following postfix
expression E given below; show the contents of the stack during the evaluation
(i)
E= 5,9,+2,/,4,1,1,3,_,*,+ 2
(ii)
E= 80,35,20,-,25,5,+,-,*
(iii)
E= 30,5,2,^,12,6,/,+,-
(iv)
E=15, 3, 2, +, /, 7, + 2, *
3. An array A[40][10] is stored
in the memory along the column with each element occupying 4 bytes. Find out
the address of the location A[3][6] if the location A[30][10] is stored at the
address 9000. 3
4. Define functions in C++ to perform a PUSH and POP
operation in a dynamically allocated stack considering the following : 4
struct Node
{
int X,Y;
Node *Link;
};
class STACK
{
Node * Top;
public:
STACK( )
{ TOP=NULL;}
void PUSH( );
void POP( );
~STACK( );
};
5. Write a function in C++ to
perform a Add and Delete operation in a dynamically allocated Queue considering
the following: 4
struct node
{
int empno ;
char name[20] ;
float sal ;
Node *Link;
};
Link list 2
Link list 1
Link list 3