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

Happy New Year.....

  /""/_/""/
 /         /
/_/""/_/appy

    /""\   /""/
  /  /\  \/  /
/_/    \_/ew

 \""\/""/
   \   /
  /  /
/_/ear

/"""""\
|  |""|  |
     /  /
    /  /
  /  /
 |    """|012
  """"""

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

HOW LONG DOES IT TAKE TO DECOMPOSE

This is something I received as an email and thought to share with you all.....

Paper Towel - 2-4 weeks

Banana Peel - 3-4 weeks

Paper Bag - 1 month

Newspaper - 1.5 months

Apple Core - 2 months

Cardboard - 2 months

Cotton Glove - 3 months

Orange peels - 6 months

Plywood - 1-3 years

Wool Sock - 1-5 years

Milk Cartons - 5 years

Cigarette Butts - 10-12 years

Leather shoes - 25-40 years

Tinned Steel Can - 50 years

Foamed Plastic Cups - 50 years

Rubber-Boot Sole - 50-80 years

Plastic containers - 50-80 years

Aluminum Can - 200-500 years

Plastic Bottles - 450 years

Disposable Diapers - 550 years

Monofilament Fishing Line - 600 years

Plastic Bags - 200-1000 years

Glass - 1-2 million years

So think before you throw things away.....

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

Happy Halloween 2011

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