Queue that uses a Stack

Question

I am having trouble understanding a question. The question asks first to write a C++ class to represent a stack of integers. Done. Here are my prototypes:

class Stack{
private:
    int top;
    int item[100];
public:
    Stack() {top = -1;}
    ~Stack();
    void push(int x) {item[++top] = x;}
    int pop() {return item[top--];}
    int empty(int top);
};

The second part of the question says "Using the stack for storage purposes, write a C++ class to represent a queue of integers". My queue is as follows:

class Queue{
private:
    int * data;
    int beginning, end, itemCount;
public:
    Queue(int maxSize = 100);
    Queue(Queue &OtherQueue);
    ~Queue();
    void enqueue(int x);
    void dequeue();
    int amount();
};

I don't understand how I am meant to use a stack for storage purposes for a queue.

Answer 1

A queue is a stack of integers in your instance. You add integers to the stack and remove them from the stack.

Answer 2

Obviously it wouldn't be the recommended method of storage, since one is LIFO and the other is FIFO.

To queue, you would push your integer onto the stack.

To dequeue, you would have to pop all integers off the stack, get the last integer, and push all other integers back onto the stack. Have a temporary stack where you push all the integers as you pop them off, get your answer, then pop all integers off the temporary stack back onto your main storage.

Answer 3

I suspect the intent of the question is to first define a class Stack as you have which has the capacity to store ints.

then declare a class inherited from stack called Queue which has it's own addtoqueue and servefromqueue functions but uses the same storage mechanism as Stack.

Given your implementation this may seem a little strange, but they probably intended some kind of linked list implementation of the stack (which has the advantage of not having a predefined upper limit) in which case the queue inherited from stack makes clear design sense.

Answer 4

Queue with stack? You will need 2 stacks, of course that would be a O(n) queue implementation.

Answer 5

There are different types of queues:

• First in - first out (FIFO) queues
• Last in - first out (LIFO) queues

If your queue is a LIFO queue, than it merely becomes a facade of a stack where enque/deque map to push/pop.

If you want a FIFO queue you will need two stacks and shift the elements from one to the others in order to get to the first element when it is enqued, then you can deque from the top of the second stack (which is in reverse order) as long as nothing else is enqued. if that happens you ned to shift everything back to the first stack... Not very efficient but maybe realizing that is the point of the exercise...

NB: you might want to at least make the max capacity of your stack configurable at construction time. Making it entirely dynamic is probably out of the scope of the excercise you are trying to solve.

Answer 6

Queue's private data must be a Stack. With that only you can of course trivially implement a LIFO queue only; for a FIFO queue you need TWO stacks -- to quote the hint for exercise 10 at this excellent page, "Hint: If you push elements onto a stack and then pop them all, they appear in reverse order. If you repeat this process, they're now back in order."...

Answer 7

The difference between a stack and a queue is in a stack you both add and remove items from the top, whereas in a queue you add at the top and remove from the bottom. So to implement a queue using a stack, the enqueue operation will be a normal push on the stack, while the dequeue operation will have to pop the entire stack, retrieve the last item, then push all the items back on the stack. You'll have to use another stack to store the items temporarily.

Answer 8

I don't agree with the existing answer. Typically, a queue is First In First Out, while a stack is obviously Last In First Out. I can only think of an implementation using two stacks, popping the whole thing and adding all but the last item to the second stack.

Seems like a silly thing to do, but I guess it's for the sake of the exercise. As commented below, it is possible to do in amortized O(1), because the second stack will be in the right order. You can just take elements from the second stack, until you run out, in which case you move everything from the original stack to the second stack.

A FIFO queue would just be a stack with Enqueue being Push and Dequeue being Pop. That doesn't make any sense as an exercise, so I'd definitely assume a FIFO queue was intended.

Edit: added some links, something not easily done on my phone :)

Answer 9

Take two stacks, in and out.

• To enqueue an element, push it on stack in.
• To dequeue an element,
  1. pop an element from stack out if out is not empty; otherwise,
  2. pop and push all elements from in to out, then serve the top element of out.

It is important that you perform step 2 only if necessary. Note that enqueue has complexity O(1), and dequeue has amortized complexity O(1), provided your implementations of pop and push are O(1).

Answer 10

I suspect that "using the stack for storage purposes" means use the stack instead of the heap. That is, don't call malloc, and don't use global variables.

Edit: Or maybe not. The more I think about this, the more I suspect it's a poorly worded, or poorly thought out assignment.

Answer 11

If you really want to implement a queue using a stack you could add a Stack member variable to the Queue class. The methods are then implemented like this:

void Queue::enqueue(int value) {
  stack.push(value);
}

int Queue::dequeue() {
  // TODO: Check for empty queue.
  Stack tempStack;
  do {
    tempStack.push(stack.pop());
  } while (!stack.empty());
  int value = tempStack.pop();
  while (!tempStack.empty()) {
    stack.push(tempStack.pop());
  }
  return value;
}

It is a very inefficient implementation.

Answer 12

So really, it's a matter of giving a stack input and then taking out information from that stack as if it were a que.

I dont think that you need to pop ALL of the integers off of the stack. Are you allowed to use any other methods for the stack? I mean, based on x86, you can always obtain elements on a stack based on their address.

In this sense, you can always get the first element on the que by retrieving the 'first-in' data member which will always be at the first index of the array within the stack data structure (as represented in your prototype).

So - since the stack is LIFO and the que is FIFO, use that to your advantage since the que data structure is dependent on the stack data structure. If you can, include a method that allows the retrieval of the first element on 'top' of the stack (which would be the element @ index 0).

Make sure that this is ok with your professor first though.