How to reverse a String using Stack / Queue

Reversing a string / word / name is very common interview question to see how the candidate studied his data structures. This involves the knowledge of Stacks and Queues.

How to reverse using a Stack.


This is straight forward if you know how a stack is working. Stack is working as a First In Last Out (FILO) data structure. So what you have to do is put letters from beginning to end in to the stack and pop one by one and write in popping order. Lets see an example for word HELP.

Pushing to the stack:

HELP

+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

ELP

+---+---+---+---+---+
| H |   |   |   |   |
+---+---+---+---+---+

LP

+---+---+---+---+---+
| E | H |   |   |   |
+---+---+---+---+---+

P

+---+---+---+---+---+
| L | E | H |   |   |
+---+---+---+---+---+

+---+---+---+---+---+
| P | L | E | H |   |
+---+---+---+---+---+

Popping from stack:

P

+---+---+---+---+---+
| L | E | H |   |   |
+---+---+---+---+---+

PL

+---+---+---+---+---+
| E | H |   |   |   |
+---+---+---+---+---+

PLE

+---+---+---+---+---+
| H |   |   |   |   |
+---+---+---+---+---+

PLEH

+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

Here we go: HELP --> PLEH

How to reverse using a Queue.
This is not that straight forward as we did using a Stack. But if you know how to do it using a stack, and how to implement a stack using queues you are done with this.

Implementation of a stack can be done using 2 queues. Lets see the above example using 2 queues.


HELP

+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

+---+---+---+---+---+   +---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+   +---+---+---+---+---+

ELP

+---+---+---+---+---+
| H |   |   |   |   |
+---+---+---+---+---+

Put H to first queue.
+---+---+---+---+---+   +---+---+---+---+---+
| H |   |   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+   +---+---+---+---+---+

LP

+---+---+---+---+---+
| E | H |   |   |   |
+---+---+---+---+---+

Dequeue values from first queue and put them to second queue. Put E to the same.
+---+---+---+---+---+   +---+---+---+---+---+
|   |   |   |   |   |   | E | H |   |   |   |
+---+---+---+---+---+   +---+---+---+---+---+

P

+---+---+---+---+---+
| L | E | H |   |   |
+---+---+---+---+---+

Dequeue values from second queue and put them to first. Put L to the same.
+---+---+---+---+---+   +---+---+---+---+---+
| L | E | H |   |   |   |   |   |   |   |   |
+---+---+---+---+---+   +---+---+---+---+---+

+---+---+---+---+---+
| P | L | E | H |   |
+---+---+---+---+---+

+---+---+---+---+---+   +---+---+---+---+---+
|   |   |   |   |   |   | P | L | E | H |   |
+---+---+---+---+---+   +---+---+---+---+---+

Same way you can dequeue by swapping the queues to implement pop method of the stack.

Vidula Hasaranga
http://vidula-sinhala.blogspot.com
http://vidulahasaranga.blogspot.com