Queue using two Stacks in Data Structures using Java
WE CAN ALSO MAKE A QUEUE USING TWO STACKS.
In this process we make two separate stacks in Stack class. We stored data in the first stack and then we will call deQueue() from Queue to store this data in reverse order in the other stack so that we can retrieve data with the rule Queue(FIFO).
Following code is provided for your assistance.
public class Node {
protected int data;
protected Node next;
}
In this process we make two separate stacks in Stack class. We stored data in the first stack and then we will call deQueue() from Queue to store this data in reverse order in the other stack so that we can retrieve data with the rule Queue(FIFO).
Following code is provided for your assistance.
public class Node {
protected int data;
protected Node next;
}
public class Queue {
private Stack stack1/*I will take input from this and put in next*/, stack2;
public Queue() {
stack1 = new Stack();//same here top will be null
stack2 = new Stack();//same here top will be null
}
public boolean isEmpty()
{
return stack2.isEmpty();
}
public void enQueue(int data)
{
stack1.push(data);//This is new Data in the stack
}
public void showAllQueue()
{
if (stack2.isEmpty())
{
while(!stack1.isEmpty())
{
stack2.push(stack1.pop());//we will take values from stack1 and store in secound stack means
//Its order will become the backword in the stack
//e.g: stack1 = 1,2,3,4,5,6 means LIFO
//will become = 6,5,4,3,2,1 in row FIFO
}
}
stack2.showAll();
}
public int deQueue()
{
if (stack2.isEmpty())
{
while(!stack1.isEmpty())
{
stack2.push(stack1.pop());//we will take values from stack1 and store in secound stack means
//Its order will become the backword in the stack
}
}
// Return top of s1
return stack2.pop();
}
@Override
public String toString() {
return stack2.toString();
}
}
package queueusingtwostacks;
public class QueueUsingTwoStacks {
public static void main(String[] args) {
Queue q1 = new Queue();
int[] numbers = {1,2,3,4,5,6};
for (int num:numbers) {
q1.enQueue(num);
}
System.out.println(q1.isEmpty());
System.out.println("dequeue: "+q1.deQueue());//It will return 1
System.out.println("dequeue: "+q1.deQueue());//It will return 2
System.out.println("-----------");
q1.showAllQueue();
System.out.println("{-------------------------Queue toString------------------}");
System.out.println(q1);
}
}
public class Stack {
protected Node top;
public Stack() {
this.top = null;
}
public void push(int data)
{
Node curr = new Node();
curr.data = data;
curr.next = top;
top = curr;
}
public boolean isEmpty()
{
return top==null;
}
public int peek()
{
return top.data;
}
public int pop()
{
int result = -1000;
if(!isEmpty())
{
result = top.data;
top = top.next;
}
return result;
}
public void showAll()
{
if(isEmpty())
System.out.println("Stack underflow");
else
{
System.out.println("List of stack with respect to LIFO(last in first out)");
Node curr = top;
while(curr!=null)
{
System.out.println(curr.data);
curr = curr.next;
}
}
}
@Override
public String toString() {
String result = null;
if(!isEmpty())
{
Node curr = top;
while(curr != null)
{
result = result+curr.data+"\n";
curr = curr.next;
}
}
result = result.replaceAll("null", "");
return result;
}
}
If you have any question regarding to any post you may ask...
ReplyDelete