Stacks and queues

stack
 A stack is the
ordered list in
which all insertion
and deletion will 60 top
be done at the
50
single end.
40
 Typical example of
stack is stack of 30
plates 20
10
Primitive stack operations
 To create a stack
 To insert one element
 To delete one element
 To check which element is onto top
 To check whether the stack empty
or not.
 Stack using array
 #include<stdio.h>
 #include<conio.h>
 #include<stdlib.h>
 #define size 5

 struct stack
 {
 int s[size];
 int top;
 }st;


Stack using array
int stfull()
 {

 if(st.top>=size-1)

 return 1;

 else

 return 0;

 }
 void push(int item)
 {
 st.top++;
 st.s[st.top]=item;
 }
 int stempty()
 {
 if(st.top==-1)
 return 1;
 else
 return 0;
 }
 int pop()
 {
 int item;
 item=st.s[st.top];
 st.top--;
 return(item);
 }
 void display()
 {
 int i;
 if(stempty())
 printf("\n Stack is empty!!");
 else
 {
 for(i=st.top;i>=0;i--)
 printf("\n%d",st.s[i]);
 }
 }
 void main(void)
 {
 int item,choice;
 char ans;
 st.top=-1;
 clrscr();
 printf("\n\t\t Implementation of stack");
 do
 {
 printf("\n Main menu");
 printf("\n1.Push\n2.Pop\n3.Display\n4.Exit");
 printf("\nEnter your choice: ");
 scanf("%d",&choice);
 switch(choice)
 {
 case 1:printf("\nEnter the item to be
pushed: ");
 scanf("%d",&item);
 if(stfull())
 printf("\nStack is full!");
 else
 push(item);
 break;
 case 2:if(stempty())
 printf("\nEmpty Stack!
Underflow!!");
 else
 {
 item=pop();
 printf("\nThe popped element
is: %d",item);
 }
 break;
 case 3:display();
 break;
 case 4: exit(0);
 }
 printf("\nDo you want to continue?");
 ans=getche();
 }
 while(ans=='Y'||ans=='y');
 getch();
 }
STACK USING LINK LIST
 #include<stdio.h>
 #include<conio.h>
 #include<stdlib.h>
 #include<alloc.h>
 typedef struct stack{ int data;
 struct
stack*next;}node;
 void main()
 {
 node*top;
 int val,item,choice;
 char ans,ch;
 void push(int ,node**);
 void display(node**);
 int pop(node**);
 int sempty(node*);
 clrscr();
 top=NULL;
 printf("\nstack using linklist");
 do
 {
 printf("\n1.push\n2.pop\n3.display\n4.exit");
 printf("\nenter ur choice");
 scanf("%d",&choice);
 switch(choice)
 {
 case 1:printf("\nenter the data");
 scanf("%d",&val);
 push(val,&top);
 break;
 case 2:if (sempty(top))
 printf("\nstack is empty");
 else
 {
 item=pop(&top);
 printf("\npopped elementis%d",item);
 }
 break;
 case 3:display(&top);
 break;
 case 4:printf("do u want 2 quit");
 ch=getche();
 if(ch=='y')
 exit(0);
 else
 break;
 default:printf("\nwrong choice");
 }
 printf("\ndo u want2 continue");
 ans=getche();

 }
 while(ans=='y');
 getch();
 }
 void push(int item,node**top)
 {
 node*New;
 node*get_node(int);
 New=get_node(item);
 New->next=*top;
 *top=New;
 }
 node*get_node(int item)
 {
 node*temp;
 temp=(node*)malloc(sizeof(node));
 if(temp==NULL)
 printf("\n memory is not allocated");
 temp->data=item;
 temp->next=NULL;
 return temp;
 }
 int sempty(node*temp)
 {
 if(temp==NULL)
 return 1;
 else
 return 0;
 }
 int pop(node**top)
 {
 int item;
 node*temp;
 item=(*top) ->data;
 temp=(*top);
 *top=(*top) ->next;
 free(temp);
 return (item);
 }
 void display(node**head)
 {
 node*temp;
 temp=*head;
 if(sempty(temp))
 printf("\nstack is empty");
 else
 {
 while(temp!=NULL)
 {
 printf("%d",temp->data);
 temp=temp->next;
 }
 }
 getch();
 }
Application of stack
 Various application of the stack
 Expression conversion
 Expression evaluation
 Parsing well formed parenthesis
 Decimal to binary conversion
 Reversing a string
 Storing function call
Concept of infix prefix and postfix
expression

 Expression is the combination of the

operand and operator operand are
numaric value and operator are of
two type
 Unary + and –
 Binary +,-,*,/ and exponential in
general
 Three types of expression
Concept of infix prefix and postfix
expression
 Infix expression (operand1 operator
operand2)
 A+B
 (a+b)*(c-d)
 (a+b/e)*(d+f)
 Postfix
Expression(operand1operand2opewrator)
 ab+
 ab+cd-*
 ab+e/df+*
Prefix Expression
 Prefix=operatoroperand1operand2
 +ab
 *+ab-cd
 */+abe+df
Conversion of infix to postfix
expression

 Algorithm
 Read the infix expression for left to right
one character at a time
 Initially push $ onto the stack for $in
stack set priority as -1 if input symbol
read is( then push it on to the stack
 If the input symbol read is an opersnd
then place it in postfix expression
 If the input symbol read is operator
 a)Check if priority of operator in stack is greater
than the priority of incoming operator then pop
the operator from the stack and place itin the
postfix expression.repeat step 4 a) till we get the
opertator from the stack which has greater
priority then incoming operator.
 b)otherwise push the operator being read onto
the stack
 C) if we read input operator as the ) then pop the
operator until we not get (

 Final pop all th content until stack becomes

empty append them to postfix expression.
 The priorities of different operator
when they are in stack will be
called as the instack priorities and
priorities of different operator when
then are from input will be called as
incoming priorities
operator Instack Incoming
priorities priorities
+or- 2 1
*or/ 4 3
^ for any 5 6
exponential
( 0 9
Operand 8 7
) na 0
Program for Evaluation of postfix
expression
 Algorithm
 Read the post fix expression from left to
right
 If input symbol as operand push it onto
the stack
 If operator is read pop two operand and
perform arithmatic operation
 Push the result onto the stack
 Repeat steps 1-4 until postfix expression
not over,
program
 #include<stdio.h>
 #include<conio.h>
 #include<ctype.h>
 #define size 80

 struct stack
 {
double s[size];
 int top;
 }st;
 void main()
 {
 char exp[size];
 int len;
 Double result;
 Double post();
 clrscr();
 printf("\nEnter a postfix expression :
");

 scanf(“%s”, &exp);
 len=strlen(exp);
 exp[len]=‘$’;
 result=post[exp];
 Printf(“\n the value of the
expression is%f”,result);
 getch();
 }
 double post(char exp[])
 { char ch, *type;
 Double result ,val,op1,op2;
Void push (double);
Double pop();
 int i;
 St.top=-1;
 i=0;
 Ch=exp[i];
 While(ch!=‘$’)
 {

 if(ch>=‘0’&& ch<=‘9’)
 type=“operand”;
 elseIf(ch==‘+’||ch==‘-’||ch==‘*’||ch==‘/’||
ch==‘^’)
 type=“operator”;
 If (strcmp(type,”operand”)==0)
 {val=ch-48;
 Push(val);
 }
 Else if(strcmp(type,”operator”)==0)
 {
 op2=pop();
 op1=pop();

 switch(ch)
 {
 case '+': result=op1+op2;
 break;
 case '-:result=op1-op2;
 break;

 case '*':result=op1*op2;
 break;
 case
'/':result=op1/op2;break;

 case‘^':result=pow(op1,op2);
break
 }
 Push(result);
 }
 i++;
 Ch=exp[i];
 }
 Result=pop();
 Return result;
 }
 Void push(double val)
 {
 If (st.top>=size-1)
 Printf(“\n stack full”);
 St.top++;
 St.s[st.top]=val;
 }
 Double pop()
 {
 Double val;
 If(st.top==-1)
 Printf(“\n stack is empty”);
 Val=st.s[st.top];
 St.top--;
 Return val;
 }
queues
 The queue is defined as the
ordered collection of elements that
has two ends front and rear from
the front end one can remove the
element and from the rear end one
can delet the element.
 Ex people waiting for ticket counter.
Operation on queue
 The queue is called as FIFO,
 Operations like
 Queue overflow
 Insertion of the element into the
queue
 Queue underflow
 Deletion of the element
 Display of the queue
Operation on queue
 Before performing the insert operation we check the
queue overflow

10 20 30 40 50 60

Front
end
Rear end

 Before performing the deletion we check the queue

is underflow
queue using array
 #include<stdio.h>
 #include<stdlib.h>
 #include<conio.h>
 #define size 5
 struct Queue
 {
 int que[size];
 int front,rear;
 }Q;
 Int Qfull()
 {
 if(Q.rear>=size-1)
 return 1;
 else
 return 0;
 }
 int insert(int item)
 {
 if(Q.front==-1)
 Q.front++;
 Q.que[++Q.rear]=item;
 return Q.rear;
 }
 int Qempty()
 {
 if((Q.front==-1)||(Q.front>Q.rear))
 return 1;
 else
 return 0;
 }
 int delet()
 {
 int item;
 item=Q.que[Q.front];
 Q.front++;
 printf("\nDeleted item is %d ",item);
 return Q.front;
 }
 void display()
 {
 int i;
 printf("\nThe elements are:- \n");
 for(i=Q.front;i<=Q.rear;i++)
 printf("%d ",Q.que[i]);
 }
 void main()
 {
 int choice,item;
 char ans;
 clrscr();
 Q.front=-1;
 Q.rear=-1;
 do
 {
 printf("\nMain Menu");
 printf("\n1.Insert\n2.Delete\n3.Disp
lay");
 printf("\nEnter your choice:- ");
 scanf("%d",&choice);
 switch(choice)
 {
 case 1:if(Qfull())
 printf("\nQUEUE is FULL");
 else
 {
 printf("\nEnter the element to
be inserted:- ");
 scanf("%d",&item);
 insert(item);
 }
 break;
 case 2:if(Qempty())
 printf("\nQUEUE is EMPTY");
 else
 item=delet();
 break;
 case 3:if(Qempty())
 printf("\nQUEUE is EMPTY");
 else
 display();
 break;
 default:printf("\nWRONG CHOICE");
 break;
 }
 printf("\nDo you want to continue?");
 ans=getche();
 }
 while(ans=='Y'||ans=='y');
 }
Q USING LINKLIST
 #include<stdio.h>
 #include<conio.h>
 #include<stdlib.h>
 typedef struct node
 {
 int data;
 struct node *next;
 }Q;
 Q *front,*rear;
 void main(void)
 {
 char ans;
 int ch;
 void insert();
 Q *delet();
 void display(Q *);
 front=NULL;
 rear=NULL;
 do
 {
 printf("\n\tProgram for queue using link list\n");
 printf("\nMain Menu");
 printf("\n1.Insert\n2.Delete\n3.Display");
 printf("\nEnter Your Choice");
 scanf("%d",&ch);
 switch(ch)
 {
 case 1:insert();
 break;
 case 2:front=delet();
 break;
 case 3:display(front);
 break;
 default:printf("\nDo you have entered Wrong
Choice\n");
 break;
 }
 printf("\nDo you want to continue?\n");
 flushall();
 ans=getch();
 }
 while(ans=='y'||ans=='Y');
 getch();
 clrscr();
 }
 Q *get_node(Q *temp)
 {
 temp=(Q *)malloc(sizeof(Q));
 temp->next=NULL;
 return temp;
 }
 void insert()
 {
 char ch;
 Q *temp;
 temp=get_node(temp);
 printf("\nInsert the elelment in the queue:\n");
 scanf("%d",&temp->data);
 if(front==NULL)
 {
 front=temp;
 rear=temp;
 }
 else
 {
 rear->next=temp;
 rear=rear->next;
 }
 }
 int Qempty(Q *front)
 {
 if(front==NULL)
 return 1;
 else
 return 0;
 }
 Q *delet()
 {
 Q *temp;
 temp=front;
 if(Qempty(front))
 {
 printf("\n\n\t\tsorry!The Queue is
empty\n");
 printf("\nCan't Delete the element");
 }
 else
 {
 printf("\n\tThe deleted Element is
%d",temp->data);
 front=front->next;
 temp->next=NULL;
 free(temp);
 }
 return front;
 }
 void display(Q *front)
 {
 if(Qempty(front))
 printf("\nThe Queue is Empty\n");
 else
 {
 printf("\n\t the display of oueue is\n");
 for(;front!=rear->next;front=front->next)
 printf("\t%d",front->data);
 }
 getch();

 }