Stack is an abstract data structure with property of Last In First Out as contrast to queue - First In First Out.In order to implement stack using queue we have to choose between which operation do we want to make costly - push() or pop(), push() operation of stack is associated with enQueue() operation of queue and pop() operation is associated with dequeue().The fundamental concept is same as we discussed in Implementing Queue using two Stack.
Algorithm:-
1. Two Queues are used to implement Stack, for push() operation elements are pushed into queue-1 and for pop() operation elements are popped from queue-2 (push n-1 elements from queue-1 in queue-2 and return nth element as return of pop()).
2. push() operation is of order O(1) as elements are added at end and we do not have to traverse whole list for insertion(reference last is maintained by implementing linked list) and pop() operation is of order O(n) as in each operation elements are transferred between q1 and q2.
3. As queue is an abstract data structure,it can be implemented using singly linked list or array, here linked list has been used.
/* Insert into q1 - push operation is order of O(1) */
public void push(int data) {
q1.enQueue(data);
}
/* Transfer N-1 elements from q1 to q2 and return last element of q1 -
pop operation is order of O(n) */
public int pop() {
int size, i = 0;
size = q1.size();
i = 0;
while (i < size - 1) {
q2.enQueue(q1.deQueue());
i++;
}
/*Store last element from q1*/
int returnVal = q1.deQueue();
/* swap q1 and q2 - It avoids transferring all elements from q2 to q1 again*/
QueueCustom tempRef;
tempRef = q1;
q1 = q2;
q2 = tempRef;
return returnVal;
}
Explanation:- As stated earlier, push() is costly operation and pop() is of constant time, we can revert the cost of push() and pop().Here, on each pop() operation , elements from q1 is tranferred to q2 so that last inserted element is returned to caller of pop().
Swapping of references is done, in order to avoid transferring of elements from q2 to q1 , since if we do not swap then Stack's LIFO property would be violated.
Time complexity:- push(data) operation is of order O(1) and pop() operation is of order O(n).
Complete sample program - Implement a Stack using two Queues in Java
package com.devinline.queues;
public class CustomStackUsingtwoQueue {
QueueCustom q1;
QueueCustom q2;
public CustomStackUsingtwoQueue() {
q1 = new QueueCustom();
q2 = new QueueCustom();
}
/* Insert into q1 - push operation is order of O(1) */
public void push(int data) {
q1.enQueue(data);
}
/*
* Transfer N-1 elements from q1 to q2 and return last element of q1 - pop
* operation is order of O(n)
*/
public int pop() {
int size, i = 0;
size = q1.size();
i = 0;
while (i < size - 1) {
q2.enQueue(q1.deQueue());
i++;
}
/* Store last element from q1 */
int returnVal = q1.deQueue();
/*
* swap q1 and q2 - It avoids transferring all elements from q2 to q1
* again
*/
QueueCustom tempRef;
tempRef = q1;
q1 = q2;
q2 = tempRef;
return returnVal;
}
public int peek() {
return 0;
}
public int getSize() {
int size = 0;
if (!q1.isEmpty()) {
size += q1.size();
}
if (!q2.isEmpty()) {
size += q2.size();
}
return size;
}
public String toString() {
StringBuffer sbf = new StringBuffer();
if (!q1.isEmpty()) {
sbf.append(q1.toString());
}
if (!q2.isEmpty()) {
sbf.append(q2.toString());
}
return sbf.toString();
}
}
class SingleListImpQueue {
private Node first; // ref to first item
private Node last; // ref to last item
public SingleListImpQueue() {
first = null; // Empty list
last = null;
}
public static Node createNewNode(int data) {
return new Node(data);
}
/* get first element */
public Node getFistNode() {
if (first == null)
return null;
else
return first;
}
/* Data nodes */
public String toString() {
StringBuffer sbf = new StringBuffer();
Node current = first;
if (first != 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();
}
public void displayList() {
Node current = first;
while (current != null) // until end of list,
{
System.out.println(current.data);
current = current.next;
}
}
public int getSizeOfList() {
Node current = first;
int count = 0;
while (current != null) // until end of list,
{
count++;
current = current.next;
}
return count;
}
/* Delete First node,return new head */
public Node deleteFirstNode() {
if (first == null)
return null;
Node temp = first.next;
Node delNode = first;
first.next = null;// garbage collected
first = temp;
return delNode;
}
/* add elements at end of list */
public void insertLast(int data) {
Node newNode = createNewNode(data);
/* If list is empty, first node is newNode */
if (isEmpty()) {
// first --> newLink
first = newNode;
} else {
// old last --> newLink
last.next = newNode;
}
last = newNode; // newLink <-- last
}
public boolean isEmpty() {
return first == null ? true : false;
}
}
class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class QueueCustom {
private SingleListImpQueue list;
public QueueCustom() {
createQueue();
}
void createQueue() {
list = new SingleListImpQueue();
}
/* put item at rear of queue */
public void enQueue(int data) {
list.insertLast(data);
}
/* returns front element of queue and removes */
public int deQueue() {
Node temp = list.deleteFirstNode();
if (temp != null)
return temp.data;
else
return -1;
}
/* returns front element of queue without removing */
public int peekFront() {
if (list.getFistNode() != null)
return list.getFistNode().data;
return 0;
}
/* returns true if queue is empty */
public boolean isEmpty() {
return list.isEmpty();
}
/* returns number of items in queue */
public int size() {
return list.getSizeOfList();
}
public String toString() {
return list.toString();
}
}
Test Client program:-
package com.devinline.queues;=============Sample Output====================
public class CustomStackUsingtwoQueueTestClient {
public static void main(String[] args) {
CustomStackUsingtwoQueue stack = new CustomStackUsingtwoQueue();
stack.push(12);
stack.push(112);
stack.push(32);
stack.push(45);
stack.push(62);
stack.push(56);
stack.push(7);
stack.push(45);
System.out.println("Stack afte 8 push() operation " + stack.toString()
+ " Current size is " + stack.getSize());
System.out.println("pop()-1 " + stack.pop());
System.out.println("pop()-2 " + stack.pop());
System.out.println("pop()-3 " + stack.pop());
System.out.println("Stack after 3 pop() operation" + stack.toString()
+ " Current size is " + stack.getSize());
stack.push(52);
stack.push(612);
stack.push(772);
stack.push(487);
stack.push(63);
stack.push(36);
System.out.println("Stack afte 6 push() " + stack.toString()
+ " Current size is " + stack.getSize());
System.out.println("pop()-1 " + stack.pop());
System.out.println("pop()-2 " + stack.pop());
System.out.println("Stack after 2 pop() operation" + stack.toString()
+ " Current size is " + stack.getSize());
}
}
Stack afte 8 push() operation [12 112 32 45 62 56 7 45 ] Current size is 8
pop()-1 45
pop()-2 7
pop()-3 56
Stack after 3 pop() operation[12 112 32 45 62 ] Current size is 5
Stack afte 6 push() [12 112 32 45 62 52 612 772 487 63 36 ] Current size is 11
pop()-1 36
pop()-2 63
Stack after 2 pop() operation[12 112 32 45 62 52 612 772 487 ] Current size is 9
============================================
Reference:-
http://stackoverflow.com/questions/688276/implement-stack-using-two-queues
Aivivu chuyên vé máy bay, tham khảo
ReplyDeletevé máy bay đi Mỹ giá bao nhiêu
chuyến bay mỹ về việt nam
vé máy bay từ canada về việt nam
vé máy bay từ nhật về việt nam bao nhiêu
ve may bay vietnam airline tu han quoc ve viet nam
Vé máy bay từ Đài Loan về Việt Nam
bảng giá khách sạn cách ly tại hà nội
Chuyến bay cho chuyên gia nước ngoài