Questions On Stack and Queue

I would highly recommend to read below posts before getting into questions on stack and queue-

Questions On Stack and Queue


Problem-1: Show how to implement a queue using two stacks.

The difference between stack and queue is the order, stack uses last in first out(LIFO) and queue uses first in first out(FIFO). Our goal here is to convert LIFO to FIFO. To achieve FIFO using Stack somehow we will have to reverse the order of Stack. We can use our second Stack to reverse the order of the elements by popping from Stack-1 and pushing the elements on to Stack-2.
Questions On Stack and Queue
Stack-1 will thus be ordered with the newest elements on the top, while Stack-2 will have the oldest elements on the top. We push the new elements onto Stack-1, and peek and pop from Stack-2. When Stack-2 is empty, we’ll transfer all the elements from Stack-1 onto Stack-2, in reverse order.


Problem-2: Show how to implement a Stack using two Queues.

This is just opposite of above question. Here we have to convert FIFO to LIFO and using two Queues. The solution is very simple.

When Push() is called, enqueue() into Q1.

question on stack and queue-2

When Pop() is called, move up to Q1.size-1 elements from Q1 to Q2. Now Q1 has the last element, dequeue() this last element and move elements back from Q2 to Q1.

question on stack and queue-3


Problem-3: Design a stack which, in addition to push() and pop(), also has functions min() which returns minimum element and max() which return maximum element. All operations should operate in O(1) time.

Here we will decorate the original Stack by extending from it. The MinMaxStack will have two Stacks to maintain minimum and maximum values.


Problem-4: Write a program to sort a stack in ascending order(with biggest item on top). You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure.

We have two stacks. Suppose that S2 is sorted and S1 is not sorted.
question on stack and queue-4
When we pop 7 from S1, it should be placed at the right position in S2 ie just above 6. We already have two elements 8 and 12 above 6. We can place 7 at right position in S2 by popping 7 from S1 and keeping it in a temporary variable. Then moving all the items from S2 to S1 which is greater than 7 and then push 7 to S2. Repeat the process for all the items in S1.
question on stack and queue-5



References:

  • Cracking The Coding Interview- Gayle Laakmann McDowell
  • Programming Interviews Exposed- John Mongan, Eric Giguère, Noah Kindler.
  • Coding Interviews- Harry He