Unit-2 chapter-1 STACKS AND ITS APPLICTIONS
UNIT-2
STACKS and QUEUES
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 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
Stack Operations:-
We can perform mainly
3operations on stack.
1.Push :- Inserting an element into the stack
2.Pop:- Deleting
an element from the stack
3.Peek:- Displaying top most element of the stack.
Representation of stack
There are two ways
of representation of a stack.
1. Array representation of a stack.
2. Linked List representation of a stack.
1.ARRAY REPRESENTATION OF STACKS
In the computer’s memory, stacks can be represented
as a linear array. 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 SIZE, 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 = SIZE–1, then the stack is full.
(You must be wondering
why we have written SIZE–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.
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=SIZE–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=SIZE–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
ALGORITHM TO INSERT AN ELEMENT IN STACK:
Input: element is new element to push into stack
Output: pushing
new element into stack at top whenever
stack is not full.
Step 1: if (top= = size-1)
PRINT OVERFLOW
Goto Step 4 [END
OF if]
Step 2: SET top =
top + +
Step 3: SET stack
[top] = element
Step 4: END
1.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=-1 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.
To delete the
topmost element, we first check if top=-1. If the condition is false, then we
decrement the value pointed by top. Thus, the updated stack becomes as shown in
Fig.
ALGORITHM TO DELETE AN ELEMENT FROM A STACK:
Algorithm Stack_POP( ):
Input: Stack with some elements.
Output: Element
deleted at top most end.
Step 1: if(top ==-1)
Print stack is empty not possible to pop
Step 2: else
element=stack[top]
top=top--
print deleted element
End Stack_POP
C Program to implement Stack using Arrays:
#include<stdio.h>
#include<stdlib.h>
void push();
void pop();
void peek();
void display();
# define size 5
int arr[size];
int top = -1;
int main()
{
int n;
printf("Stack
Menu:-\n\n1.Push\n2.Pop\n3.Peek\n4.Display\n5.Exit\n\n");
while(1)
{
printf("Enter your choice\t");
scanf("%d",&n);
switch(n)
{
case 1: push(); break;
case 2: pop(); break;
case 3: peek(); break;
case 4: display(); break;
case 5: exit(1);
default: printf("Please enter
a valid choice\n");
}
}
return 0;
}
void push()
{
if(top == size-1)
printf("Overflow Occured\n");
else
{
int n;
printf("Enter value:\t");
scanf("%d",&n);
top++;
arr[top] = n;
}
}
void pop()
{
if(top == -1)
printf("Underflow Occured\n");
else
{
printf("Element %d is
deleted\n",arr[top]);
top--;
}
}
void peek()
{
if(top == -1)
printf("Stack is Empty\n");
else
printf("Top element is %d\n",arr[top]);
}
void display()
{
if(top == -1)
printf("Empty stack - No elements to
display\n");
else
{
int i;
for(i = top;i>=0;i--)
printf("%d ",arr[i]);
printf("\n");
}
}
· To insert an element with value 9, we
first check if TOP=NULL. If this is the case, then we allocate memory for a new
node, store the value in its DATA part and NULL in its LINK part. The new node
will then be called TOP. However, if TOP!=NULL, then we insert the new node at
the beginning of the linked stack and name this new node as TOP
STEP 1: allot a memory for
NEW NODE and its named as temp
temp->link = NULL;
Step 2: if(top ==
NULL)
top = temp
Step 3: else
temp->link = top
top = temp;
Step 4:End
Stack Intial Condition:
Initial condition
of stack implemented using
arrays is top=-1
Stack Full condition
or overflow condition
Trying
to PUSH an item into full stack is known
Stack overflow.
Stack
overflow condition is top = = ARRAYSIZE - 1
Stack underflow or Empty condition
Trying to POP an item from empty stack is known
as Stack underflow. Stack underflow
condition is top = = -1
Algorithm Stack_PUSH(item)
Input: element is new element to push into stack
Output: pushing
new element into stack at top whenever
stack is not full.
If (top == ARRAYSIZE-1)
print(stack is full, not possible to perform push operation)
else
top=top++
read element
stack[top]=element
End Stack_PUSH
Algorithm Stack_POP( ):
Input: Stack with some elements.
Output: Element
deleted at top most end.
Step 1: if(top ==-1)
Print stack is empty not possible to pop
Step 2: else
a)
element=stack[top]
b) top=top--
print deleted item.
End Stack_POP
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 points to next node.
· Empty stack condition is
top = = 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.
C program to implement
Stacks using Linked List:-
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *link;
}*top = NULL;
void push();
void pop();
void peek();
void display();
int main()
{
int n;
printf("Stack
Menu:-\n\n1.Push\n2.Pop\n3.Peek\n4.Display\n5.Exit\n\n");
while(1)
{
printf("Enter your choice\t");
scanf("%d",&n);
switch(n)
{
case 1: push(); break;
case 2: pop(); break;
case 3: peek(); break;
case 4: display(); break;
case 5: exit(1);
default: printf("Please enter
a valid choice\n");
};
}
return 0;
}
void push()
{
int n;
struct node *temp;
temp = (struct node *)malloc(sizeof(struct node));
printf("Enter value\t");
scanf("%d",&n);
temp->data = n;
temp->link = NULL;
if(top == NULL)
top = temp;
else
{
temp->link = top;
top = temp;
}
}
void pop()
{
if(top == NULL)
printf("Underflow - No elements to
delete\n");
else
{
printf("Top element %d is
deleted\n",top->data);
top = top->link;
}
}
void peek()
{
if(top == NULL)
printf("Empty Stack\n");
else
printf("Top element =
%d\n",top->data);
}
void display()
{
if(top == NULL)
printf("No elements to display\n");
else
{
struct node *temp=top;
for (temp = top ; temp != NULL ; temp =
temp->link)
printf("%d ",temp->data);
printf("\n");
}
}
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 1> <operator> <operand 2>
Prefix notation: Here operator is present
before two operands.
eg. + a b
The format for Prefix notation
as follows <operator> <operand 1> <operand 2>
Postfix notation: Here operator is present after two operands
eg. a b +
The format for Postfix notation as follows
<operand
1> <operand 2>
<operator>
Applications of stacks:
1. Infix to postfix conversion
2.
Evaluation of postfix
expression
3.
Balancing symbols or delimiter matching
1.
Infix to postfix conversion:
While conversion of infix expression to postfix
expression, we must follow the precedence (priority) of the operators.
Operator priority
( 0
+
- 1
*
/ % 2
^ or $ (highest) 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.
Infix
Expression: A+
(B*C-(D/E^F)*G)*H, where ^ is an exponential operator
C Program
to convert Infix to Postfix
Expression:-
#include<stdio.h>
#include<ctype.h>
char stack[20];
int top = -1;
void push(char);
char pop();
int
precedence(char);
int main()
{
char infix[20],postfix[20];
int i,j=0;
printf("Enter an Infix
expression:-\t");
gets(infix);
for (i =0; infix[i] != '\0' ; i++)
{
if(isalnum(infix[i]))
{
postfix[j] =
infix[i];
j++;
}
else if(infix[i] == '(')
push(infix[i]);
else if(infix[i] == ')')
{
while(stack[top]
!= '(')
{
postfix[j]
= pop();
j++;
}
pop();
}
else
{
while((top!=-1&&stack[top]!='(')&&(precedence(stack[top])>=
precedence(infix[i])))
{
postfix[j]=pop();
j++;
}
push(infix[i]);
}
}
while(top != -1)
{
postfix[j] = pop();
j++;
}
postfix[j]='\0';
printf("PostFix Expression =
%s\n",postfix);
return 0;
}
void push(char c)
{
top++;
stack[top] = c;
}
char pop()
{
char c;
c = stack[top];
top--;
return c;
}
int
precedence(char c)
{
switch(c)
{
case '+':
case '-': return 1;
case '*':
case '/': return 2;
}
}
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 for Postfix Expression Evaluation:
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
Evaluate below postfix
expression 234+*6-
C Program to evaluate Postfix
Expression:-
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
int a[20];
int top = -1;
void push(int);
int pop();
int main()
{
char
stack[20];
int i,a,b;
printf("Enter
Postfix Expression\t");
gets(s);
for (i=0; stack[i]!='\0';
i++)
{
if(isdigit(stack[i]))
{
push(stack[i]-'0');
}
else
{
a
= pop();
b
= pop();
switch(stack[i])
{
case
'+': push(b+a); break;
case
'-': push(b-a); break;
case
'*': push(b*a); break;
case
'/': push(b/a); break;
case
'%': push(b%a); break;
default:
printf("Invalid expression\n");
exit(1);
}
}
}
int res =
pop();
if(top ==
-1)
printf("Result
= %d\n",res);
else
printf("Invalid
expression\n");
return 0;
}
void push(int n)
{
top++;
a[top] = n;
}
int pop()
{
int n;
n = a[top];
top--;
return n;
}
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 :-
1. Make an empty stack.
2. Read an expression from left to right.
3. If the reading character is opening symbol, then push it into stack.
4. If the reading character is closing symbol and if the stack is empty, then report
as unbalanced expression.
5. If the reading character is closing symbol and if the stack is not empty,
then pop the stack.
6. If the symbol popped
is not the corresponding
opening symbol, then report as unbalanced expression.
7. After
processing the entire expression and if the stack is not empty
then report as unbalanced expression.
8. 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>
char a[100];
int top = -1;
void push(char);
void pop();
int main()
{
int i,flag = 0;
char stack[100];
printf("Enter an
Equation\t");
gets(s);
for (i = 0 ; stack[i] !=
'\0' ;i++)
{
if(stack[i] == '(' ||
stack[i] == '{' || stack[i] == '[')
push(stack[i]);
if(stack[i]
== ')')
{
if(a[top]
== '(')
pop();
else
{
flag
= 1;
break;
}
}
if(stack[i]
== '}')
{
if(a[top]
== '{')
pop();
else
{
flag
= 1;
break;
}
}
if(stack[i]
== ']')
{
if(a[top]
== '[')
pop();
else
{
flag
= 1;
break;
}
}
}
if(top == -1 &&
flag == 0)
printf("Balanced\n");
else if(top != -1 ||
flag == 1)
printf("Un-Balanced\n");
}
void push(char c)
{
top++;
a[top] = c;
}
void pop()
{
top--;
}
Comments
Post a Comment