Data structures and algorithms in Java

Previously I have discussed the implementation of stack data structure using two queues. This post discusses about queue implementation using two stacks. The implementation uses Stack class available from java.util package.

Prerequisites:

Knowledge of Java, data structures, stack data structure and the operations that can be performed on it. Basics of stack and knowledge of LIFO implementation is required.

Explanation:

The basic idea is to perform queue ADT operations using stack two stacks. The stacks used in this implementation are from java.util package.

If you want to learn more about the operations that can be performed on the stack visit java.util.Stack common operations.

Algorithm:

1. Declare two stacks enqueue and dequeue of type Stack<Integer>. The enqueue stack will contain all the elements which are pushed to the queue. And dequeue stack is used when an element is to be dequeued/peeked from the queue.
2. To enqueue a new element, push it to enqueue stack.
3. To dequeue the front element –
   • Check if the dequeue stack is empty. If it is empty then pop all the elements from the enqueue stack one by one and push it to the dequeue stack. In this way the front element of the queue(the element at the bottom of enqueue stack) comes at the top of the dequeue stack.
   • Pop the top element of dequeue stack.
4. To peek the front element –
   • Check if the dequeue stack is empty. If it is empty then pop all the elements from the enqueue stack one by one and push it to the dequeue stack. In this way the front element of the queue (the element at the bottom of enqueue stack) comes at the top of the dequeue stack.
   • Peek the top element of dequeue stack.

Diagrammatic representation:

Implementation:

public class QueueUsing2Stacks {

	/* Stack data structure */
	Stack<Integer> enqueue;
	Stack<Integer> dequeue;

	/* Initialization of data structure */
	public QueueUsing2Stacks() {
		enqueue = new Stack<Integer>();
		dequeue = new Stack<Integer>();
	}

	/* Method to push a new element to the enqueue stack */
	void push(int data) {
		enqueue.push(data);
	}

	/* Method to pop an element from dequeue stack */
	void pop() {
		if (enqueue.empty() && dequeue.empty()) {
			System.out.println("Queue is empty. Cannot pop element.");
			return;
		}
		ensureElementsInDequeueStack();
		dequeue.pop();
	}

	/* Method to peek an element */
	int peek() {
		ensureElementsInDequeueStack();
		return dequeue.peek();
	}

	/* Method which ensures elements are present in dequeue stack */
	void ensureElementsInDequeueStack() {
		if (dequeue.empty()) {
			populateDequeueStack();
		}

	}

	/* Method which populates dequeue stack from enqueue stack */
	private void populateDequeueStack() {
		while (!enqueue.empty()) {
			dequeue.push(enqueue.pop());
		}
	}

	public static void main(String[] args) {

		QueueUsing2Stacks q = new QueueUsing2Stacks();
		q.push(1);
		q.push(2);
		q.push(3);
		System.out.println("Top element = " + q.peek());
		q.pop();
		System.out.println("Top element = " + q.peek());

	}

}

Code output:

Top element = 1
Top element = 2

Time and space complexity:

Time complexity of enqueue operation is O(1) since no iteration over any elements in done when an element is enqueued. The time required to dequeue an element or to view the the top element is O(n), where n= number of elements. Since during the dequeue or peek operation, if the dequeue stack is empty then all elements are moved from enqueue to dequeue stack before any element is removed or top element is viewed.

Space complexity required = O(n) for enqueue stack and O(n) for dequeue stack. Hence total space complexity = O(n) + O(n) = O(2n) = O(n). Also an important point to note here is that at any point, most of the elements are present only in one stack.

Here is the link to the above code on my github profile, Queue using 2 stacks.

I hope you have gained some useful information on queue data structures implementation from this article and please provide any feedback or comments below. Thank you for reading..!!