Data Structures UNIT - II (Stacks)
Unit-II: Stacks
and Queues
Stacks: The Stack: Definition, operations,
implementation using arrays, linked list and Stack applications: Infix to postfix expression conversion,
Evaluation of Postfix expressions, balancing the symbols.Queue: definition, operations, implementation using
arrays, linked list&it’sApplications.Circular
queue: definition&its operations, implementation, Dequeue: definition & its types, implementation.
Learning Material
Stack Definition:
·
Stack
is a linear data structure.
·
Stack can be defined as a collection of
homogeneous elements, where insertion and deletion operations takes place at
only one end called TOP.
·
The insertion operation is termed as PUSH
and deletion operation is termed as POP operation.
·
The
PUSH and POP operations are performed at TOP of the stack.
·
An
element in a stack is termed as ITEM.
·
The maximum number of elements that stack
can accommodate is termed as SIZE of the stack.
·
Stack Pointer ( SP ) always points to the
top element of the stack.
·
Stack
follows LIFO principle. i.e. Last In First Out i.e.
the element which is inserted last into the stack will be deleted first from
the stack.
Diagram of a stack
- Array
representation of a stack.
- Linked
List representation of a stack.
1. ARRAY
REPRESENTATION OF STACKS:
In the computer’s memory, stacks can be
represented as a linear array.
(First
we have to allocate memory for array. Starting from the first location of the
memory block, items of the stack can be stored in sequential fashion. )
Every
stack has a variable called TOP associated with it, which is used to store the
address of the topmost element of the stack. It is this position where the
element will be added to or deleted from. There is another variable called MAX,
which is used to store the maximum number of elements that the stack can hold.
If TOP = NULL, then it indicates that the stack is empty and if TOP = MAX–1,
then the stack is full. (You must be wondering why we have written MAX–1. It is
because array indices start from 0.)
The
stack in Fig. shows that TOP = 4, so insertions and deletions will be done at
this position. In the above stack, five more elements can still be stored.
OPERATIONS ON
STACK:
A stack supports three basic operations: push, pop, and peek. The push operation adds an element to the
top of the stack and
The
pop operation removes the element
from the top of the stack.
The
peek operation returns the value of
the topmost element of the stack.
Stack overflow
Trying to PUSH an item into full stack is known as
Stack overflow. Stack overflow condition is top = = SIZE - 1
Stack underflow
Trying to POP an item from empty stack is known as
Stack underflow. Stack underflow condition is top = = -1
1. PUSH OPERATION:
· The push operation is used to
insert an element into the stack. The new element is added at the topmost
position of the stack.
· However, before inserting the
value, we must first check if TOP=MAX–1, because if that is the case, then the
stack is full and no more insertions can be done. If an attempt is made to
insert a value in a stack that is already full, an OVERFLOW message is printed.
- To insert an element with
value 6, we first check if TOP=MAX–1. If the condition is false, then we
increment the value of TOP and store the new element at the position given
by stack[TOP]. Thus, the updated stack becomes as shown in Fig.
Algorithm To Insert/Push An Element In Stack:
Output: pushing new item
into stack at top whenever stack is not full.
Step
1: IF TOP = MAX-1
PRINT OVERFLOW
Goto Step 4
[END OF IF]
Step
2: SET TOP = TOP + 1
Step
3: SET STACK [TOP] = VALUE
Step
4: END
2. POP OPERATION:
· The pop operation is used to
delete the topmost element from the stack. However, before deleting the value,
we must first check if TOP=NULL because if that is the case, then it means the
stack is empty and no more deletions can be done. If an attempt is made to
delete a value from a stack that is already empty, an UNDERFLOW message is
printed.
Algorithm To Delete/Pop An Element From Stack:
Input: Stack with some
elements.
Output: item deleted at
top most end.
Step 1: IF TOP = NULL
PRINT UNDERFLOW
GOTO STEP 4
[END OF IF]
Step 2: SET VAL = STACK [TOP]
Step 3: SET TOP = TOP - 1
Step 4: END
3. PEEK OPERATION:
· Peek is an
operation that returns the value of the topmost element of the stack without
deleting it from the stack.
· However, the Peek operation first
checks if the stack is empty, i.e., if TOP = NULL, then an appropriate message
is printed, else the value is returned.
· Here, the Peek
operation will return 5, as it is the value of the topmost element of the stack
Algorithm To Peep
An Element of Stack:
Step 1: IF TOP = NULL
PRINT STACK IS EMPTY
Goto Step 3
Step 2: RETURN STACK [TOP]
Step 3: END
C Program to
implement stack using arrays
#include<stdio.h>
#include<stdlib.h>
#define SIZE 5
void push();
void pop();
void peep();
void display();
int stack[10],top=-1,ele;
int main()
{
int
ch;
printf("\n
1.push\n 2.pop\n 3.peep\n 4.display");
while(1)
{
printf("\nmenu");
printf("\nenter
ur choice");
scanf("%d",&ch);
switch(ch)
{
case
1:push();
break;
case
2:pop();
break;
case
3:peep();
break;
case
4:display();
break;
default:exit(1);
}
}
return 0;
}
void push()
{
if(top==SIZE-1)
{
printf("stack
is full");
}
else
{
top++;
printf("enter
a element");
scanf("%d",&ele);
stack[top]=ele;
}
}
void pop()
{
if(top==-1)
{
printf("stack
is empty");
}
else
{
ele=stack[top];
printf("\n
deleted item is %d",ele);
top--;
}
}
void peep()
{
if(top==-1)
{
printf("stack
is empty");
}
else
{
ele=stack[top];
printf("\n
top most element is %d",ele);
}
}
void display()
{
int i;
printf("
elements of stack are:\n");
if(top==-1)
{
printf("\n
stack is empty");
}
else
{
for(i=top;i>=0;i--)
{
printf("%d\n",stack[i]);
}
}
}
2. LINKED
LIST REPRESENTATION OF A STACK
·
The array representation of stack allows
only fixed size of stack. i.e. static memory allocation only.
·
To overcome the static memory allocation
problem, linked list representation of stack is preferred.
·
In linked list representation of stack,
each node has two parts. One is data field is for the item and link field
stores the address of the next node. The START pointer of the linked
list is used as TOP. All insertions and deletions are done at the node pointed
by TOP.
·
Empty
stack condition is
tos
= = NULL
·
Full condition is not applicable for
Linked List representation of stack. Because here memory is dynamically
allocated.
·
In linked List representation of stack,
top pointer always points to top most node only. i.e. first node in the list.
OPERATIONS ON A
LINKED STACK:
A linked stack supports all the three stack operations,
that is, push, pop, and peek. 1. PUSH OPERATION: · The push operation is used to insert an element into
the stack. The new element is added a topmost position of the stack.
ALGORITHM TO INSERT AN ELEMENT IN A LINKED STACK:
3. POP OPERATION:
·
The pop operation is used to delete the topmost element from a stack. However,
before deleting the value, we must first check if TOP=NULL, because if this is
the case, then it means that the stack is empty and no more deletions can be
done. If an attempt is made to delete a value from a stack that is already
empty, an UNDERFLOW message is printed.
·
In case TOP!=NULL, then we will delete the node pointed by TOP, and make TOP
point to the second element of the linked stack.
ALGORITHM TO DELETE AN ELEMENT FROM A LINKED LIST:
Step 1: IF TOP = NULL
PRINT
UNDERFLOW
Goto
Step 5
[END
OF IF]
Step 2: SET TEMP = TOP
Step 3: SET TOP = TOP -> NEXT
Step 4: FREE TEMP
Step 5: END
C
program to implement stacks using linked list:-
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct
node *next;
}*new,*top,*temp;
void push();
void pop();
void peep();
void
display();
int ele;
void main()
{
int ch;
printf("\n1.push\n 2.pop\n 3.peep\n 4.display");
while(1)
{
printf("\n
enter ur choice");
scanf("%d",&ch);
switch(ch)
{
case 1:push();
break;
case 2:pop();
break;
case 3:peep();
break;
case 4:display();
break;
default:exit(1);
}
}
}
void push()
{
new=(struct node *)malloc(sizeof(struct node));
printf("enter an element to be inserted");
scanf("%d",&ele);
new->next=NULL;
new->data=ele;
if(top==NULL)
{
top=new;
}
else
{
new->next=top;
top=new;
}
}
void pop()
{
if(top==NULL)
{
printf("stack is empty");
}
else
{
temp=top;
printf("deleted item from the stack is %d",top->data);
top=top->next;
temp->next=NULL;
free(temp);
}
}
void peep()
{
if(top==NULL)
printf("stack is empty");
else
{
printf("display top most element is %d",top->data);
}
}
void display()
{
printf("elements of the stack are");
if(top==NULL)
printf("stack is empty");
else
{
temp=top;
while(temp!=NULL)
{
printf("%d\n",temp->data);
temp=temp->next;
}
}
}
Arithmetic expressions or Algebraic
expressions:-
An expression is a
combination of operands and operators.
Eg. c= a + b
In the above
expression a, b, c are operands and +, = are called as operators.
We have 3
notations for the expressions.
i.
Infix
notation
ii.
Prefix
notation
iii.
Postfix
notation
Infix notation:
Here operator is present between two operands. eg. a + b
The format for Infix notation as follows
<operand> <operator> <operand>
Prefix notation:
Here operator is present before two operands. eg. + a b
The format for Prefix notation as follows
<operator> <operand> <operand>
Postfix notation:
Here operator is present after two operands. eg. a b +
The format for Postfix notation as follows
<operand> <operand> <operator>
- Infix
to postfix conversion
- Evaluation
of postfix expression
- Balancing
symbols or delimiter matching
1. Infix
to postfix conversion
conversion of infix expression to postfix expression,
we must follow the precedence (priority) of the operators.
Operator priority
( 0
+ - 1
* / % 2
^ or $ 3
To convert an
infix expression to postfix expression, we can use one stack.
Within the stack,
we place only operators and left parenthesis only. So stack used in conversion
of infix expression to postfix expression is called as operator stack.
Algorithm
Conversion of infix to postfix
Input: Infix expression.
Output: Postfix
expression.
1. Perform the
following steps while reading of infix expression is not over
a) if symbol is left
parenthesis then push symbol into stack.
b) if symbol is
operand then add symbol to post fix expression.
c) if symbol is
operator then check stack is empty or not.
i) if stack is empty
then push the operator into stack.
ii)
if
stack is not empty then check priority of the operators.
(I) if
priority of current operator > priority of operator present at top of stack
then push operator into stack.
(II)
else if priority of operator present at
top of stack >= priority of current operator then pop the operator present
at top of stack and add popped operator to postfix expression (go to step I)
d)
if symbol is right parenthesis then pop
every element form stack up corresponding left parenthesis and add the poped
elements to postfix expression.
2. After
completion of reading infix expression, if stack not empty then pop all the
items from stack and then add to post fix expression.
End conversion of
infix to postfix
C Program to
convert infix to postfix expression:-
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
void
push(char);
char
pop();
int
priority(char);
int
top=-1;
char
stack[20];
int
main()
{
char postfix[30],infix[30],ch;
int i,j=0;
printf("\n enter infix expression\n");
gets(infix);
for(i=0;infix[i]!='\0';i++)
{
ch=infix[i];
if(ch=='(')
push(ch);
else if(ch==')')
{
while(stack[top]!='('&&top!=-1)
{
postfix[j]=pop();
j++;
}
pop();
}
else if(isalpha(ch)||isdigit(ch))
{
postfix[j]=ch;
j++;
}
else
{
while(priority(ch)<=priority(stack[top])&&top!=-1)
{
postfix[j]=pop();
j++;
}
push(ch);
}
}
while(top!=-1)
{
postfix[j]=pop();
j++;
}
postfix[j]='\0';
printf("\n result is
%s",postfix);
return 0;
}
void
push(char x)
{
top++;
stack[top]=x;
}
char
pop()
{
return stack[top--];
}
int
priority(char ch)
{
if(ch=='(')
return 0;
else if(ch=='+'||ch=='-')
return 1;
else if(ch=='*'||ch=='/'||ch=='%')
return 2;
else if(ch=='^')
return 3;
}
2.Evaluation
of postfix expression
·
To
evaluate a postfix expression we use one stack.
·
For Evaluation of postfix expression, in
the stack we can store only operand. So stack used in Evaluation of postfix expression
is called as operand stack.
Algorithm
PostfixExpressionEvaluation
Input: Postfix expression
Output: Result of
Expression
1. Repeat the
following steps while reading the postfix expression.
a) if the read symbol
is operand, then push the symbol into stack.
b) if
the read symbol is operator then pop the top most two items of the stack and
apply the operator on them, and then push back the result to the stack.
2. Finally
stack has only one item, after completion of reading the postfix expression.
That item is the result of expression.
End
PostfixExpressionEvaluation
C Program to evaluate postfix expression:-
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<math.h>
int
stack[20];
char
postfix[20],ch;
void
push(int);
int
pop();
int
top=-1,res;
int
main()
{
int i,op1,op2;
printf("\n enter postfix expression\n");
gets(postfix);
for(i=0;postfix[i]!='\0';i++)
{
ch=postfix[i];
if(isdigit(ch))
push(ch-48);
else
{
op2=pop();
op1=pop();
switch(ch)
{
case'+':push(op1+op2);
break;
case'-':push(op1-op2);
break;
case'*':push(op1*op2);
break;
case'/':push(op1/op2);
break;
case'%':push(op1%op2);
break;
case'^':res=pow(op1,op2);
push(res);
break;
}
}
}
printf("\n the result of postfix
expression is %d",pop());
return 0;
}
void
push(int x)
{
top++;
stack[top]=x;
}
int
pop()
{
return stack[top--];
}
3.Balancing Symbols or
Delimiter matching :-
The objective of this application is to check the
symbols such as parenthesis ( ) , braces
{ }
, brackets [
] are matched or not.
Thus every left parenthesis, brace and bracket must
have its right counterpart.
Algorithm for
Balancing Symbols or Delimiter matching :-
- Make an empty
stack.
- Read an
expression from left to right.
- If the
reading character is opening symbol, then push it into stack.
- If the
reading character is closing symbol and if the stack is empty, then report
as unbalanced expression.
- If the
reading character is closing symbol and if the stack is not empty, then
pop the stack.
- If the symbol
popped is not the corresponding opening symbol, then report as unbalanced expression.
- After
processing the entire expression and if the stack is not empty then report
as unbalanced expression.
- After
processing the entire expression and if the stack is empty then report as
balanced expression.
C
program to implement balancing symbols or delimiter matching:-
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
void
push(char);
char pop();
char stack[20];
int top=-1;
main()
{
char expr[20],ch;
int i;
clrscr();
printf("\nEnter an
expression\n");
gets(expr);
for(i=0;expr[i]!='\0';i++)
{
ch=expr[i];
if(ch=='(' || ch=='{' ||
ch=='[')
push(ch);
else if(ch==')')
{
if(top==-1)
{
printf("\nUnbalanced
expression");
exit();
}
else if(
(ch=pop())!='(')
{
printf("\nUnbalanced
expression");
exit();
}
}
else if(ch=='}')
{
if(top==-1)
{
printf("\nUnbalanced
expression");
exit();
}
else if(
(ch=pop())!='{')
{
printf("\nUnbalanced
expression");
exit();
}
}
else if(ch==']')
{
if(top==-1)
{
printf("\nUnbalanced
expression");
exit();
}
else if(
(ch=pop())!='[')
{
printf("\nUnbalanced
expression");
exit();
}
}
}
if(top==-1)
printf("\nBalanced
expression");
getch();
}
void
push(char x)
{
top++;
stack[top]=x;
}
int
pop()
{
return stack[top--];
}
Comments
Post a Comment