Java Stack Help

Question

How would you implement a stack using two queues. And what would the running time of the push() and pop() methods be.

Answer 1

Here is a good starting reference for your homework. Here is an example of analyzing a computational complexity problem. That may make it easier for you to calculate the running times of push and pop.

Both of those should help you understand your textbook a little bit better.

Answer 2

So, a Queue has a characteristic of First-In-First-Out (FIFO). This is typically achieved by only allowing add (enqueue) operations to one end and remove (dequeue) operations from the opposite end of a single List.

A Stack has a characteristic of Last-In-First-Out (LIFO). This is achieved by only allowing add (push) and remove (pop) operations from the same end of a List.

It stands to reason then that a single Queue will work just fine for at least one of the Stack's operations (push, or pop). The trick then comes in how to implement the second operation. So a buffer space is needed to allow for the moving around of data while trying to reach the desired item, that is the purpose of the second Queue.