* In this question we will implement a Queue data structure for integers. Your queue will be implemented using two stacks (stack1 and stack2). You can do it as follows:
- the enqueue function (add to queue) always adds an element on top of stack1.
- the dequeue function (remove from queue) removes an element from the top of stack2. if stack 2 is empty, all stack1 elements are moved to stack2 (using StackPop and StackPush).
You are given a stack implementation with the following functions:
Code:
Stack* newStack();
void StackPush(Stack* st, int num);
int StackPop(Stack* st);
bool StackEmpty(const Stack* st)
Your task is as follows:
1. declare the Queue type
2. implement 3 functions newQueue, enqueue, and dequeue.
- newQueue - creates an emply queue
- enqueue - gets an integer and adds it into a queue
- deque - returns the queue member that was inserted first. The call on empty queue should have no effect and can return 0
You may assume that all memory allocations are successful.
Do NOT use VLAs!
Paste ONLY your type declarations and functions into the answer box, NOT the whole program.
For example:
/*** YOUR CODE HERE ***/
Code:
int main() {
Queue *q = newQueue();
for(int i=0; i<5; i++) {
enqueue(q, i);
}
for(int i=0; i<5; i++) {
printf("%d\n", dequeue(q));
}
/* Should free queue but omit for simplicity */
return 0;
}
|
0
1
2
3
4 |
My try:
Code:
typedef struct Queue {
Stack *first_stack;
Stack *second_stack;
} Queue;
Queue* newQueue() {
Queue* newQ = (Queue*)malloc(sizeof(Queue));
newQ->first_stack = newStack();
newQ->second_stack = newStack();
}
void enqueue(Queue* q, int i) {
StackPush(q->first_stack, i);
if (StackEmpty(q->second_stack)) {
do {
StackPush(q->second_stack, StackPop(q->first_stack));
} while (!StackEmpty(q->first_stack));
}
}
int dequeue(Queue* q) {
if (q == NULL || StackEmpty(q->second_stack)) {
return 0;
}
return StackPop(q->second_stack);
}
For some reason it returns always zeroes to the input in the example, which is wrong of course. Does someone figure the problem out?
BTW, when I created the struct for a Queue - I automatically defined the Stacks as pointers to Stacks and not just regular Stacks.
Is it good? There is another better alternative?"
Thanks you all.