Stack from Queues

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.

Java code:

package datastructures;

import java.util.Queue;
import java.util.LinkedList;
public class StackUsingQueues {
	
	Queue  q1, q2;
	
	public StackUsingQueues() {
		q1 = new LinkedList();
		q2 = new LinkedList();
	}
	
	public void push(String s) throws Exception{
		if (q1.isEmpty() && q2.isEmpty()) {
			q1.add(s);
		} else {
			Queue qA = q1;
			Queue qB = q2;
			if (q1.isEmpty() ) {
				qA = q1;
				qB = q2;
			} else if (q2.isEmpty()) {
				qA = q2;
				qB = q1;
			} else {
				throw new Exception("None of the queues are eligible to have data inserted");
			}
			
			qA.add(s);
			while (!qB.isEmpty() ) {
				qA.add(qB.poll());
			}
		}
	}
	
	public String pop() {
		String retStr = null;
		
		if (!q1.isEmpty()) {
			retStr = q1.poll();
		} else {
			retStr = q2.poll();
		}
		
		return retStr;
	}
	
	public static void main(String[] args) {
		StackUsingQueues stack = new StackUsingQueues();
		
		try {
			stack.push("A");
			String s = stack.pop();
			System.out.println(s);
			
			System.out.println("Adding YZ");
			stack.push("Y");
			stack.push("Z");
			
			s = stack.pop();
			System.out.println(s);
			s = stack.pop();
			System.out.println(s);

			
			System.out.println("added BCDEFGH");
			stack.push("B");
			stack.push("C");
			stack.push("D");
			stack.push("E");
			stack.push("F");
			stack.push("G");
			stack.push("H");

			while ( (s = stack.pop()) != null) {
				System.out.println(s);
			}
			
		} catch (Exception e) {
			e.printStackTrace();
		}
		
	}
}

PHP code:

class Stack {

	var $q1= array();
	var $q2 = array();
	
	//array_push pushes on to end of array
	//array_pop pops from end of array
	//array_shift takes an element from beginning of array
	//array_unshift inserts an element into beginning of array
	
	//So array_push/array_shift makes a queue (as does array_unshift/array_pop) (FIFO)
	public function push($s) {
		if (count($this->q1) == 0 && $this->q2 == 0) {
			array_push($this->q1, $s);
		} else {
			if (count($this->q1) == 0) {
				array_push($this->q1, $s);
				$this->transferFromQ1toQ2($this->q2, $this->q1);
			} else if (count($this->q2) == 0) {
				array_push($this->q2, $s);
				$this->transferFromQ1toQ2($this->q1, $this->q2);
			} else {
				echo "Something went wrong";
			}
		}
	}
	
	private function transferFromQ1toQ2(&$q1, &$q2) {
		while (count($q1) > 0) {
			array_push($q2, array_shift($q1));
		}
	}
	
	public function pop() {
		if (count($this->q1) != 0) {
			return array_shift($this->q1);
		} else if (count($this->q2) != 0) {
			return array_shift($this->q2);
		} else {
			return NULL;
		}
	}
}

function p($s) {
	echo "$s
"; } $stack = new Stack(); $stack->push("A"); p($stack->pop()); p("---- adding BC ----"); $stack->push("B"); $stack->push("C"); p($stack->pop()); p($stack->pop()); p("---- Adding DEFGH ----"); $stack->push("D"); $stack->push("E"); $stack->push("F"); $stack->push("G"); $stack->push("H"); while (($s = $stack->pop()) != NULL) { p($s); }

Leave a Reply