Implement a Queue using two Stacks in C

Question

Why my code is getting crushed when I'm running it. It says passing incompatible pointer type passing in Push() function. How to solve this problem?

Here is the code of my implementation in C. Here is a quick summery How I tried to solve the problem.

• First I created a struct for Stack
• Wrote Push and Pop function for stack
• Wrote a struct for Queue

• First Stack for EnQueue and Second Stack for DeQueue operation.

  #include <stdio.h>
  #include <stdlib.h>
  #include <limits.h>
  struct Stack {
   int data;
   struct Stack *next;
  };
  struct Stack *CreateStack () {
   return NULL;
  }
  int isEmptyStack(struct Stack *top) {
   return (top == NULL);
  }
  void Push(struct Stack **top, int data) {
   struct Stack *newNode = (struct Stack*) malloc(sizeof(struct Stack));
   if(!newNode)
   return;
   newNode->data = data;
   newNode->next = *top;
   *top = newNode;
  }
  int Pop(struct Stack **top) {
   struct Stack *temp;
   int data;
   if(isEmptyStack(*top)) {
   printf("Empty Stack.\n");
   return INT_MIN;
   }
   temp = *top;
   data = (*top)->data;
   *top = (*top)->next;
   free(temp);
   return data;
  }
  struct Queue {
   struct Stack *S1;
   struct Stack *S2;
  };
  struct Queue *CreateQueue() {
   return NULL;
  }
  void EnQueue(struct Queue *Q, int data) {
   Push(Q->S1, data);
  }
  int DeQueue(struct Queue *Q) {
   if(!isEmptyStack(Q->S2)) {
   return Pop(Q->S2);
   }
   else {
   while(!isEmptyStack(Q->S1)) {
   Push(Q->S2, Pop(Q->S1));
   }
   return Pop(Q->S2);
   }
  }
  int main() {
   struct Queue *Q = CreateQueue();
   Q->S1 = Q->S2 = NULL;
   EnQueue(Q, 1);
   EnQueue(Q, 2);
   EnQueue(Q, 3);
   printf("%d ", DeQueue(Q));
   printf("%d ", DeQueue(Q));
   printf("%d ", DeQueue(Q));
   return 0;
  }
  

• user0042: Why did you tag this c++?
• user0042: You need to pass the address of the pointer here: Push(&(Q->S1), data);
• Afikur Rahman: C++ has backward compatibility with C. may be that's why. BTW thanks
• user0042: "C++ has backward compatibility with C" That's not entirely true. C and C++ are different languages.

Answer 1

Three problems:

a) calling Push - wrong parameter type: struct Stack **top expected not astruct Stack *top

b) calling Pop - wrong parameter type: struct Stack **top expected not astruct Stack *top

c) Queue *CreateQueue - memory not allocated

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct Stack {
 int data;
 struct Stack *next;
};
struct Stack *CreateStack () {
 return NULL;
}
int isEmptyStack(struct Stack *top) {
 return (top == NULL);
}
void Push(struct Stack **top, int data) {
 struct Stack *newNode = (struct Stack*) malloc(sizeof(struct Stack));
 if(!newNode)
 return;
 newNode->data = data;
 newNode->next = *top;
 *top = newNode;
}
int Pop(struct Stack **top) {
 struct Stack *temp;
 int data;
 if(isEmptyStack(*top)) {
 printf("Empty Stack.\n");
 return INT_MIN;
 }
 temp = *top;
 data = (*top)->data;
 *top = (*top)->next;
 free(temp);
 return data;
}
struct Queue {
 struct Stack *S1;
 struct Stack *S2;
};
struct Queue *CreateQueue() {
 struct Queue *newNode = (struct Queue *) malloc(sizeof(struct Queue ));
 return newNode;
}
void EnQueue(struct Queue *Q, int data) {
 Push(&Q->S1, data);
}
int DeQueue(struct Queue *Q) {
 if(!isEmptyStack(Q->S2)) {
 return Pop(&Q->S2);
 }
 else {
 while(!isEmptyStack(Q->S1)) {
 Push(&Q->S2, Pop(&Q->S1));
 }
 return Pop(&Q->S2);
 }
}
int main() {
 struct Queue *Q = CreateQueue();
 Q->S1 = Q->S2 = NULL;
 EnQueue(Q, 1);
 EnQueue(Q, 2);
 EnQueue(Q, 3);
 printf("%d ", DeQueue(Q));
 printf("%d ", DeQueue(Q));
 printf("%d ", DeQueue(Q));
 return 0;
}

Output:

1 2 3