I am dealing with a very popular problem of implementing a queue with two stacks and doing it in C language as it gives me an excuse to brush up my knowledge of structs and pointers .
I have created two stack variables with the help of struct , st1 and st2 respectively . I push the elements into st1 for enqueue operation and for dequeue , elements from st1 are popped and pushed simultaneously into st2 . After popping st2 , the elements are again transferred back into st1 (I know this is redundant but this is not the problem I am facing) . All of this has been implemented with respective functions in a switch case in main() .
The bug is , while invoking the dequeue operation , the 1st element of st1 gets mysteriously overridden by some other value .
Here is the complete code :
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct stack
{
char name[5] ;
int top ;
int *a ;
}Stack ;
int n ;
int main()
{
void push(Stack*,int) ;
int delete(Stack*,Stack*) ;
void display(Stack*) ;
printf("Enter the size of the queue: ") ;
scanf("%d",&n) ;
Stack st1,st2 ;
st1.a = (int*)malloc(n*sizeof(int)) ;
st1.top = -1 ;
st2 = st1 ;
strcpy(st1.name,"st1") ;
strcpy(st2.name,"st2") ;
while(1)
{
printf("Enter 1. to insert.\nEnter 2. to delete.\nEnter 3. to display.\nEnter anything else to exit.\n") ;
char c ;
int e ;
scanf(" %c",&c) ;
switch(c)
{
case '1':
printf("Enter the no. to be inserted: ") ;
scanf("%d",&e) ;
push(&st1,e) ;
break ;
case '2' :
e = delete(&st1,&st2) ;
printf("%d got deleted.\n",e) ;
break ;
case '3' :
display(&st1) ;
break ;
default :
free(st1.a) ;
free(st2.a) ;
return 0 ;
}
}
}
int delete(Stack *st1,Stack *st2)
{
void push(Stack*,int) ;
int pop(Stack*) ;
while(st1->top!=-1)
push(st2,pop(st1)) ;
int e = pop(st2) ;
while(st2->top!=-1)
push(st1,pop(st2)) ;
return e ;
}
void push(Stack *st,int e)
{
void display(Stack*) ;
printf("Operations on %s begin: \n",st->name) ;
printf("Currently %s:\n",st->name) ;
display(st) ;
st->top++ ;
if(st->top==n)
{
printf("Queue full.\n") ;
st->top-- ;
return ;
}
st->a[st->top] = e ;
printf("After operations , %s:\n",st->name) ;
display(st) ;
printf("Operations on %s end.\n\n",st->name) ;
}
int pop(Stack *st)
{
void display(Stack*) ;
printf("Operations on %s begin: \n",st->name) ;
display(st) ;
if(st->top==-1)
{
printf("Queue is empty.\n") ;
return -1 ;
}
int e = st->a[st->top] ;
st->top-- ;
printf("After operations , %s:\n",st->name) ;
display(st) ;
printf("Operations on %s end.\n\n",st->name) ;
return e ;
}
void display(Stack *st)
{
if(st->top==-1)
{
printf("Queue is empty.\n") ;
return ;
}
int i ;
for(i=0;i<=st->top;i++)
printf("%d ",st->a[i]) ;
printf("\n") ;
}
As you can see , I have written printf() statements for debugging .
And here is the output so you can see the bug :
Enter the size of the queue: 5
Enter 1. to insert.
Enter 2. to delete.
Enter 3. to display.
Enter anything else to exit.
1
Enter the no. to be inserted: 1
Operations on st1 begin:
Currently st1:
Queue is empty.
After operations , st1:
1
Operations on st1 end.
Enter 1. to insert.
Enter 2. to delete.
Enter 3. to display.
Enter anything else to exit.
1
Enter the no. to be inserted: 2
Operations on st1 begin:
Currently st1:
1
After operations , st1:
1 2
Operations on st1 end.
Enter 1. to insert.
Enter 2. to delete.
Enter 3. to display.
Enter anything else to exit.
2
Operations on st1 begin:
1 2
After operations , st1:
1
Operations on st1 end.
Operations on st2 begin:
Currently st2:
Queue is empty.
After operations , st2:
2
Operations on st2 end.
Operations on st1 begin:
2
After operations , st1:
Queue is empty.
Operations on st1 end.
Operations on st2 begin:
Currently st2:
2
After operations , st2:
2 2
Operations on st2 end.
Operations on st2 begin:
2 2
After operations , st2:
2
Operations on st2 end.
Operations on st2 begin:
2
After operations , st2:
Queue is empty.
Operations on st2 end.
Operations on st1 begin:
Currently st1:
Queue is empty.
After operations , st1:
2
Operations on st1 end.
2 got deleted.
Enter 1. to insert.
Enter 2. to delete.
Enter 3. to display.
Enter anything else to exit.
You can see when I invoke dequeue operation , after popping 2 from st1 and pushing it into st2 , the 0th index of st1 gets changed from 1 to 2 .
I have been baffled by this for quite some time now . I thought pointers were the problem , so I removed all of them and did the same thing but passed the stack variables by value . When I did that , there was an even bigger problem , each time I inserted a value it somehow got removed automatically . So when I tried to insert the next time , the previous insertion had disappeared .
I feel there are some fundamental problems causing these issues that need to be addressed to make the code work like it should .
st1 and st2 are using the same memory for a, because st2 = st1 just copies the a pointer, it doesn't make a copy of the memory it points to. So you need to allocate them separately.
Stack st1;
st1.a = malloc(n*sizeof(int)) ;
st1.top = -1 ;
Stack st2;
st2.a = malloc(n*sizeof(int)) ;
st2.top = -1 ;
Also, in C you shouldn't cast the result of malloc().