Thread: Building a queue out of stacks - C

  1. #1
    Registered User
    Join Date
    Nov 2019
    Posts
    135

    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.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    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.
    Last edited by john.c; 12-02-2019 at 01:58 PM.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  4. #4
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    Quote Originally Posted by Salem View Post
    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.

  5. #5
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    Quote Originally Posted by john.c View Post
    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);
    }

  6. #6
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    I don't see anything wrong.

    BTW, we usually don't cast the return value of malloc (if your compiler complains then it's set for compiling C++, not C).
    A little inaccuracy saves tons of explanation. - H.H. Munro

  7. #7
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    Quote Originally Posted by john.c View Post
    I don't see anything wrong.

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

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Last edited by laserlight; 12-02-2019 at 04:20 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Your dequeue should copy stack1 to stack2 if stack2 is empty and stack1 is not.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  10. #10
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    LaserLight -
    Yea, I have written so for readability only.
    Thank you for the suggestion and the answer you added.

  11. #11
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    Quote Originally Posted by stahta01 View Post
    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...

  12. #12
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    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!

    About casting malloc, laserlight (and me!) are correct. Your instructor is wrong. However, you probably should do things the way he wants anyway.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  13. #13
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  14. #14
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    John - I'll ask someone. And maybe at the end of the semester I'll tell the lecturer about this casting

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

    Thank you all!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C Program to implement queue operations using linear queue
    By riteshkrjain in forum C Programming
    Replies: 2
    Last Post: 10-03-2017, 10:57 AM
  2. (queue*)this)->queue::qput’ does not have class type
    By brack in forum C++ Programming
    Replies: 13
    Last Post: 11-11-2010, 03:41 PM
  3. creating a queue of stacks
    By AJOHNZ in forum C++ Programming
    Replies: 1
    Last Post: 09-07-2009, 07:47 PM
  4. Stacks
    By Kunzy in forum C++ Programming
    Replies: 7
    Last Post: 01-28-2003, 04:10 PM
  5. Queue and Priority Queue
    By Pamela in forum C++ Programming
    Replies: 1
    Last Post: 12-07-2001, 11:09 PM

Tags for this Thread