Implement a queue using two stacks in Java

Queue is an abstract data structure with property of  First In First Out as contrast to stack's property First In Last Out.In order to implement queue using stack we have to choose between which operation do we want to make costly - enqueue() or dequeue(), enqueue() operation of queue is associated with push() operation of stack and dequeue() is associated with pop().

Algorithm:- 
1. Two stacks are used to implement Queue, for enQueue() operation elements are pushed into stack-1 and for deQueue() operation elements are popped from stack-2 (push elements from stack-1 if stack-2 is empty).
2. enQueue() operation is of order O(1) always and deQueue() operation is of order O(1) only if stack -2 is not empty, otherwise it will take more time(pushing elements from stack-1 to stack-2). However, number of elements transferred from stack-1 and number of elements popped from stack-2 is same, so average complexity of deQueue() operation is order of O(1).
3. Since, stack is an an abstract data structure, stack is implemented using singly linked list.

Sample code for enQueue() and deQueue operation :- 

/* Internally call push operation of order O(1) */
void enQueue(int data) {
 s1.push(data);
}

/* Internally call pop operation of amortized complexity order O(1) */
int deQueue() {
 int temp = -999999; // A marker value indicating empty queue
 /* If S2 is not empty, return top element in O(1) */
 if (!s2.isEmplty()) {
  return s2.pop();
 }
 if (s1.isEmplty()) {
  System.out.println("Queue is empty!!");
 }
 while (!s1.isEmplty()) {
  temp = s1.peek();
  s2.push(s1.pop());
 }
 /* Remove top element from S2 */
 if (!s2.isEmplty())
  s2.pop();
 return temp;
}

Explanation:- For enQueue() operation push operation is called and internally calls Linkedlist's insertFirst() operation to adds elements in stack-1.
For deQueue() operation , if stack-2 is empty , elements are transferred form  stack-1 to stack-2, otherwise elements are popped from stack-2. When stack-2 is empty, after elements transferred to stack-2, last element is removed from top.
Time complexity :- enQueue() operation of order O(1) and deQueue() operation is of amortized complexity order O(1).

Complete sample program - implementing Queue using 2 Stacks:-

package com.devinline.stacks;

/*Queue implementation assuming pop operation is costly*/
public class CustomQueueUsingTwoStack {
 StackCustom s1 = null;
 StackCustom s2 = null;

 public CustomQueueUsingTwoStack() {
  s1 = new StackCustom();
  s2 = new StackCustom();
 }

 /* Internally call push operation of order O(1) */
 void enQueue(int data) {
  s1.push(data);
 }

 /* Internally call pop operation of amortized complexity order O(1) */
 int deQueue() {
  int temp = -999999; // A marker value indicating empty queue
  /* If S2 is not empty, return top element in O(1) */
  if (!s2.isEmplty()) {
   return s2.pop();
  }
  if (s1.isEmplty()) {
   System.out.println("Queue is empty!!");
  }
  while (!s1.isEmplty()) {
   temp = s1.peek();
   s2.push(s1.pop());
  }
  /* Remove top element from S2 */
  if (!s2.isEmplty())
   s2.pop();
  return temp;
 }

 boolean isEmptyQueue() {
  return true;
 }

 int getQueueSize() {
  int size = 0;

  if (!s1.isEmplty()) {
   size += s1.getSize();
  }
  if (!s2.isEmplty()) {
   size += s2.getSize();
  }
  return size;
 }

 public String toString() {
  StringBuffer str = new StringBuffer();
  if (!s1.isEmplty()) {
   str.append(s1.toString());
  }
  if (!s2.isEmplty()) {
   str.append(s2.toString());
  }
  return str.toString();
 }

}

class SinglyLinkedList {
 Node head = null;

 private void createLikedList() {
  head = null;
 }

 public static Node createNewNode(int data) {
  return new Node(data);
 }

 /* get first element */
 public Node getFistNode() {
  if (head == null)
   return null;
  else
   return head;
 }

 /* Delete First node,return new head */
 public Node deleteFirstNode() {
  if (head == null)
   return null;
  Node temp = head.next;
  Node delNode = head;
  head.next = null;// garbage collected
  head = temp;
  return delNode;
 }

 /* Display data of nodes/iterate linked list */
 public String iterateLinkedList() {
  StringBuffer sbf = new StringBuffer();
  Node current = head;
  if (head != null) {
   sbf.append("[");
   while (current != null) {
    sbf.append(current.data + " ");
    current = current.next;
   }
   sbf.append(" ]");
  } else {
   System.out.println("Linked list is empty.");
  }
  return sbf.toString();

 }

 /* Add New node at start of linked list */
 public void insertFirst(int data) {
  Node newNode = createNewNode(data);
  if (head == null) {
   head = newNode;
  } else {
   newNode.next = head;
   head = newNode;
  }
 }

}

class Node {
 public int data;
 public Node next;

 public Node(int data) {
  this.data = data;
  this.next = null;
 }
}

class StackCustom {
 Node node = null;
 int top = -1;
 SinglyLinkedList list;

 public StackCustom() {
  createStack();
 }

 void createStack() {
  top = -1;
  list = new SinglyLinkedList();
 }

 int pop() {
  if (list.getFistNode() != null) {
   top--;
   return list.deleteFirstNode().data;
  } else
   return -1;
 }

 void push(int data) {
  list.insertFirst(data);
  ++top;
 }

 int peek() {
  return list.getFistNode().data;
 }

 boolean isEmplty() {
  return (top == -1) ? true : false;
 }

 public String toString() {
  return list.iterateLinkedList();
 }

 public int getSize() {
  return top + 1;
 }
}

Test client program:-

package com.devinline.stacks;

public class customQueueTestClient {

 public static void main(String[] args) {
  CustomQueueUsingTwoStack queue = new CustomQueueUsingTwoStack();
  queue.enQueue(12);
  queue.enQueue(52);
  queue.enQueue(62);
  queue.enQueue(162);
  queue.enQueue(222);
  System.out.println("Five enQueue operation" + queue.toString());
  System.out.println("Queuue size is: " + queue.s1.getSize());
  System.out.println("deQueue() operation - deQueued element: "
    + queue.deQueue());
  System.out.println("deQueue() operation- deQueued element: "
    + queue.deQueue());
  System.out.println("Queuue size is: " + queue.getQueueSize());

  queue.enQueue(62);
  queue.enQueue(162);
  System.out.println("Two enQueue operation: " + queue.toString());
  System.out.println("Intermediate size after enQueue(s1 + s2): "
    + queue.getQueueSize());
  System.out.println("deQueue() - deQueued element: " + queue.deQueue());
  System.out.println("deQueue() - deQueued element: " + queue.deQueue());
  System.out.println("deQueue() - deQueued element: " + queue.deQueue());
  System.out.println("deQueue() - deQueued element: "
    + queue.getQueueSize());
  System.out.println("deQueue() - deQueued element: " + queue.deQueue());
  System.out.println("Queuue size is: " + queue.getQueueSize());
  queue.enQueue(76);
  queue.enQueue(453);
  queue.enQueue(122);
  queue.enQueue(192);
  queue.enQueue(82);
  System.out.println("Five enQueue operation: " + queue.toString());
  System.out.println(queue.getQueueSize());
  System.out.println("deQueue() - deQueued element: " + queue.deQueue());
  System.out.println(queue.getQueueSize());
 }

}

==========Sample output=============
Five enQueue operation[222 162 62 52 12  ]
Queuue size is: 5
deQueue() operation - deQueued element: 12
deQueue() operation- deQueued element: 52
Queuue size is: 3
Two enQueue operation: [162 62  ][62 162 222  ]
Intermediate size after enQueue(s1 + s2): 5
deQueue() - deQueued element: 62
deQueue() - deQueued element: 162
deQueue() - deQueued element: 222
deQueue() - deQueued element: 2
deQueue() - deQueued element: 62
Queuue size is: 1
Five enQueue operation: [82 192 122 453 76  ][162  ]
6
deQueue() - deQueued element: 162
5

====================================

Note:- We have made push() operation less costlier as compare to pop() , we can reverse this implementation and cane make push() operation  costlier.