Ran across a question on how to implement a stack by only using queues on SO, so I decided to give it a go in Java and PHP. It’s actually pretty straight forward:
- Initialize two queues.
- On every push operation, if both queues are empty, add to the first queue.
- If one of the queues is full (one will always be empty), pop off all the elements from the full queue and add them to the empty queue in the same order (as they were popped). This guarantees the full queue will always be sorted like a stack, so when a pop occurs, it is popped in the “LIFO” order, not “FIFO” order.
Code after the break. Continue reading
Exploring and refreshing data structures and algorithms, you will inevitably find the question “how do you reverse a linked list?”. For this exercise, we assume a singly-linked list, with a head, and the last item pointing to null (as shown).
Singly Linked List
The goal is to end up with the following linked list:
Reversed Linked List
I decided to implement Breadth First Search and Depth First Search in Java. The implementation uses a Directed as the underlying abstract data type, keeps track of visited graph nodes by keeping a separate data structure, and implements BFS by using a Queue.
Some implementations only implement DFS and BFS on trees, but this implementation uses a graph because a tree is really a directed graph with no cycles (i.e. a node cannot reach itself in traversal). However, in the case of a graph, when a node can reach itself, you have to pay special attention to those loops by marking nodes as “visited” so that you don’t “visit” them again and end up in a stack overflow or an infinite loop. There is more than one way to do this: by keeping a separate data structure of the visited nodes (the way I did it) or by adding an extra field to each node, mark it as visited each time it is visited, and reset it once you are done with the search. Since both methods would take linear time but resetting the nodes’ visited flags would make coding more complicated, I chose to keep a separate data structure for that.
UPDATE 2012/10/16: Graph in PHP. Interestingly, PHP arrays use hash maps as the underlying structure, so using key/value pairs might actually speed up the algorithm.