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, and that much is 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.

The question seems odd. A stack is a LIFO (last in, first out) structure while a queue normally is FIFO (first in, first out) structure. Unless you have to implement a LIFO queue it is hard to use a stack. — Martin Liversage, Aug 18 '09 at 15:53
Related: http://stackoverflow.com/questions/688276/implement-stack-using-two-queues — Robert Harvey, Aug 18 '09 at 15:56
I don't think you meant to have your Stack constructor as you have it. Perhaps you meant "Stack() {top = -1;}"? — Jonathan, Aug 18 '09 at 16:00
Re:KM, Because the only answer we can give you is the assignment doesn't make sense. You can't use a stack as a queue. — jmucchiello, Aug 18 '09 at 16:26
We've been saying this about teachers for years, but teachers still give out assignments that don't make sense. Don't think that's going to change anytime soon. — Robert Harvey, Aug 18 '09 at 16:44

Stephan202 · Answer 1 · 2009-08-18T17:37:55.453

10

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).

edited Aug 18 '09 at 17:37

answered Aug 18 '09 at 16:02

Stephan202

59,965
13
127
133

Good point, Nick! I have updated the answer. (Did you just remove and then re-add your comment? It was gone for a short while...) – Stephan202 Aug 18 '09 at 16:32
What do you mean by "sensible", a word you seem far too fond of? – Aug 18 '09 at 17:01
It is not clear that I refer to `push` and `pop` implementations which have O(1) complexity? – Stephan202 Aug 18 '09 at 17:34
I removed the word "sensible". Just for you, Neil. – Stephan202 Aug 18 '09 at 17:38
OK, so what data structure are you using that gives you O(1) for push and pop? The obvious answer is a doubly linked list. In which case why not use one such list to implement the queue that the question is about? – Aug 18 '09 at 18:00
2

I am not disputing that there are better ways to implement a queue than using two stacks. However, the OP wants to know how to do this, and that is what my answer addresses. To be clear: I agree with you that the OP's assignment is contrived. – Stephan202 Aug 18 '09 at 18:14
The best answer to give to a question is always the most direct, correct solution. If the questioner doesn't like it, tough. – Aug 18 '09 at 18:23

score 4 · Answer 2 · answered Aug 18 '09 at 15:55

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

Thorarin · Accepted Answer · 2009-08-18T18:21:10.420

3

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

edited Aug 18 '09 at 18:21

answered Aug 18 '09 at 15:58

Thorarin

47,289
11
75
111

8

This appears to be a common interview question, asked by retard interviewers. – Aug 18 '09 at 16:10
1

It does make sense as an exercise, because it shows how one can use simple data structures to create more complex ones. By using two stacks in a sensible way one can create a queue with *O(1)* `enqueue` and `dequeue` operations: http://stackoverflow.com/questions/1294756/queue-that-uses-a-stack/1294845#1294845 – Stephan202 Aug 18 '09 at 16:10
3

There is no "sensible" way of using two stacks to implement a queue. The sensible way is to use a deque, list or vector. – Aug 18 '09 at 16:33
@Stephan202: True, but it still seems a little artificial. A queue is much easier to implement with just an array, and it would just be O(1) (non-amortized). – Thorarin Aug 18 '09 at 18:17
@Stephan202: it's not actually `O(1)`. But it is *amortized* `O(1)`. – Zifre Aug 18 '09 at 18:19
@Thorarin: an array based queue is not actually `O(1)` either. Once you fill the array, you have to reallocate it, which is `O(n)`. This is like a hash table. – Zifre Aug 18 '09 at 18:21
There's no need to reallocate the array, unless you need to grow it in size. The original stack implementation was also fixed size, so I assumed that was okay. If it needs to be resizing, it would be amortized O(1). – Thorarin Aug 18 '09 at 18:22

score 2 · Answer 4 · answered Aug 18 '09 at 15:54

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.

score 2 · Answer 5 · answered Aug 18 '09 at 15:55

2

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

answered Aug 18 '09 at 15:55

Nick Dandoulakis

42,588
16
104
136

1

+0. Yes, you need two stacks. No, the implementation will not necessarily be *O(n)*. See my answer: http://stackoverflow.com/questions/1294756/queue-that-uses-a-stack/1294845#1294845 – Stephan202 Aug 18 '09 at 16:07

score 2 · Answer 6 · answered Aug 18 '09 at 15:56

2

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.

answered Aug 18 '09 at 15:56

maxpower47

1,666
1
10
14

You don't have to shuffle back and forth. Once things are on the "dequeue" stack, they can stay there until the stack is empty. – Jeff Ferland Aug 18 '09 at 16:29
1

Until you have to add more items to the queue. – maxpower47 Aug 18 '09 at 16:41

score 0 · Answer 7 · answered Aug 18 '09 at 15:54

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.

score 0 · Answer 8 · answered Aug 18 '09 at 16:03

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.

score 0 · Answer 9 · answered Aug 18 '09 at 16:04

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.

score 0 · Answer 10 · answered Aug 18 '09 at 16:06

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.

score -1 · Answer 11 · answered Aug 18 '09 at 15:55

There are different types of 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.

score -2 · Answer 12 · answered Aug 18 '09 at 15:51

-2

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

answered Aug 18 '09 at 15:51

dr.

1,429
12
18

Queue that uses a Stack

12 Answers12