Building a queue out of stacks - C

* 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:

Test	Result
/*** 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.

A stack is a LIFO (Last In, First Out) data structure.
That is, you 'push' and 'pop' from just one end.

A queue on the other hand is a FIFO (First In, First Out) data structure.
You 'push' on one end, and 'pop' off the other.

So every time you pop from your synthesised queue, you need some way to get at the first thing you pushed.
I guess the question is, do you prefer to do all this stack reversal when you push or when you pop?

Firstly, always post real code (this code is not real since newQueue doesn't even return the queue, which your compiler should've warned you about).

Secondly, always post a complete program (and any required input, particularly input that causes the problem) so that we can run it easily.

It should also be noted that making a queue in this way (with two stacks) is incredibly dumb (but it's just an exercise).
And I notice that your enqueue doesn't follow the instructions since they have the stack transfer happens in dequeue.

Quote:

---

Originally Posted by Salem

A stack is a LIFO (Last In, First Out) data structure.
That is, you 'push' and 'pop' from just one end.

A queue on the other hand is a FIFO (First In, First Out) data structure.
You 'push' on one end, and 'pop' off the other.

So every time you pop from your synthesised queue, you need some way to get at the first thing you pushed.
I guess the question is, do you prefer to do all this stack reversal when you push or when you pop?

---

Actually the second_stack is used here as the reversed form of the stack.
To my understanding, as long as the stack has a peek - it is placed at the top of the second stack.
So, when we would like to pop an element from the queue, we approach to the second stack - popping its "upper" element up.
When we would like to push an element to the queue - we just enqueue it to the first stack - its turn will be soon as the second stack happens to be empty again.

Quote:

---

Originally Posted by john.c

Firstly, always post real code (this code is not real since newQueue doesn't even return the queue, which your compiler should've warned you about).

Secondly, always post a complete program (and any required input, particularly input that causes the problem) so that we can run it easily.

It should also be noted that making a queue in this way (with two stacks) is incredibly dumb (but it's just an exercise).
And I notice that your enqueue doesn't follow the instructions since they have the stack transfer happens in dequeue.

---

Thanks for the remarks.
As you have seen - they provide us with interface only and not detailed implementation, but next time I will implement also and paste the whole program as needed.

I have noticed your points and fixed them, but their automatic tests says I haven't passed some hidden tests (The inputs are hidden) - but the input in the example succeeded.

Do you have maybe an idea?

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();
    return newQ;
}


void enqueue(Queue* q, int i) {
    StackPush(q->first_stack, i);
}


int dequeue(Queue* q) {
    if (q == NULL) {
        return 0;
    }
    if (StackEmpty(q->second_stack)) {
        if (StackEmpty(q->first_stack)) {
            return 0;
        }
        else {
            do {
                StackPush(q->second_stack, StackPop(q->first_stack));
            } while (!StackEmpty(q->first_stack));
        }
    }


    return StackPop(q->second_stack);
}

---

I don't see anything wrong. :confused:

BTW, we usually don't cast the return value of malloc (if your compiler complains then it's set for compiling C++, not C).

Quote:

---

Originally Posted by john.c

I don't see anything wrong. :confused:

BTW, we usually don't cast the return value of malloc (if your compiler complains then it's set for compiling C++, not C).

---

Weird, probably it's some edge case they have in the tests...

As for the casting - we are told in lectures that this is a good practice.

Thank you!

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?"

I have a small stylistic suggestion. Instead of this:

Code:

---

if (StackEmpty(q->first_stack)) {
    return 0;
}
else {
    do {
        StackPush(q->second_stack, StackPop(q->first_stack));
    } while (!StackEmpty(q->first_stack));
}

---

You could write:

Code:

---

if (StackEmpty(q->first_stack)) {
    return 0;
}

do {
    StackPush(q->second_stack, StackPop(q->first_stack));
} while (!StackEmpty(q->first_stack));

---

The reason is that the if branch ends in a return statement, so if control enters the if branch, you know that it will leave the function there. Therefore, you don't need the explicit else branch. Effectively, what you're doing is checking that some pre-conditions are satisfied (in this case, that the first stack is not empty), and if not, you return early. After doing all these pre-condition checks, you then do the "actual" work.

EDIT:

Quote:

---

Originally Posted by HelpMeC

As for the casting - we are told in lectures that this is a good practice.

---

It is good practice if you want to write C code that can be compiled as C++, but then there are so many other things you need to know about C and C++ compatibility if you want to properly write C code that will be compilable as C++. If you're only writing for a C compiler, then it becomes poor practice because it is both unnecessarily verbose, and could suppress a possible warning from forgetting to #include <stdlib.h>

Quote:

---

Originally Posted by HelpMeC

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?

---

The alternative would be to simply declare them as member objects. This can be a Good Thing in that then you don't have to worry about allocating memory for them (and remembering to deallocate), but if the stack interface provided insists on newStack(), then perhaps you should use pointers instead.

Your dequeue should copy stack1 to stack2 if stack2 is empty and stack1 is not.

Tim S.

LaserLight -
Yea, I have written so for readability only.
Thank you for the suggestion and the answer you added.

Quote:

---

Originally Posted by stahta01

Your dequeue should copy stack1 to stack2 if stack2 is empty and stack1 is not.

Tim S.

---

And it's done in the code I have attached...

The only "edge case" I can conceive is if the queue is empty, but you handle that as per instructions (returning 0). Can you contact another student and ask if they are having trouble? Maybe the test is bad. The code is so simple that I just can't imagine anything wrong with it. Then again, I've felt that way many many times before and been wrong! :tongue:

About casting malloc, laserlight (and me!) are correct. Your instructor is wrong. However, you probably should do things the way he wants anyway.

> Your instructor is wrong. However, you probably should do things the way he wants anyway.
Or send the instructor here for better education, or just forward them the message threads.

John - I'll ask someone. And maybe at the end of the semester I'll tell the lecturer about this casting:cool:

Salem - I don't want to embarrass - I probably will embarrass my final grade:)

Thank you all!