Make the following stack algorithm in Java A stack can be implemented using two
ID: 3568262 • Letter: M
Question
Make the following stack algorithm in Java
A stack can be implemented using two queues. Let stack to be implemented be 's' and queues used to implement be 'q1? and 'q2?. Stack 's' can be implemented in two ways:
Method 1
This method makes sure that newly entered element is always at the front of 'q1?, so that pop operation just dequeues from 'q1?. 'q2? is used to put every new element at front of 'q1?.
push(s, x) // x is the element to be pushed and s is stack
1) Enqueue x to q2
2) One by one dequeue everything from q1 and enqueue to q2.
3) Swap the names of q1 and q2
// Swapping of names is done to avoid one more movement of all elements
// from q2 to q1.
pop(s)
1) Dequeue an item from q1 and return it.
Method 2
In push operation, the new element is always enqueued to q1. In pop() operation, if q2 is empty then all the elements except the last, are moved to q2. Finally the last element is dequeued from q1 and returned.
push(s, x)
1) Enqueue x to q1 (assuming size of q1 is unlimited).
pop(s)
1) One by one dequeue everything except the last element from q1 and enqueue to q2.
2) Dequeue the last item of q1, the dequeued item is result, store it.
3) Swap the names of q1 and q2
4) Return the item stored in step 2.
// Swapping of names is done to avoid one more movement of all elements
// from q2 to q1.
Explanation / Answer
Method-1 implementaion using java program
import java.util.LinkedList;
import java.util.Queue;
public class StackUsingQueueMethod1
{
//Create two Queue of LinkedList class type
//since Queue is an interface .
//Instantiate a class LinkedList that implements Queue
//class
private static Queue<Integer>q1=new LinkedList<Integer>();
private static Queue<Integer>q2=new LinkedList<Integer>();
public static void main(String[] args)
{
//insert elements into queue,q1 as like inserting
//inserting into stack.
System.out.println("Method2-Demonstration");
System.out.println("Push elements into the queue like a stack");
System.out.println("Queue-elements");
System.out.println(" Front- 1,2,3- Rear");
push(1,q1);
push(2,q1);
push(3,q1);
//remover elements from the q1 as poping element from
//the stack
System.out.println("Method2");
System.out.println("Pop element from the stack using Queue");
int element=pop(q1,q2);
System.out.println(element);
}
//remover element fromt q1 as like poping element from the stack
operation
private static int pop(Queue<Integer> q1, Queue<Integer> q2)
{
int size=q1.size();
for (int index = 0; index < size-1; index++)
q2.add(q1.remove());
//returns the last element in the queue
return q1.peek();
}
//insert element into the q1 as like push element into stack
private static void push(int element, Queue<Integer> q1)
{
//call add method to insert element into the queue
q1.add(element);
}
}
------------------------------------------------------------------------
Sample output:
Method2-Demonstration
Push elements into the queue like a stack
Queue-elements
Front- 1,2,3- Rear
Method2
Pop element from the stack using Queue
3
------------------------------------------------------------------------------------
Method-2 java program
import java.util.LinkedList;
import java.util.Queue;
public class StackUsingQueueMethod2
{
//Create two Queue of LinkedList class type
//since Queue is an interface .
//Instantiate a class LinkedList that implements Queue
//class
private static Queue<Integer>q1=new LinkedList<Integer>();
private static Queue<Integer>q2=new LinkedList<Integer>();
public static void main(String[] args)
{
//insert elements into queue,q1 as like inserting
//inserting into stack.
System.out.println("Method2-Demonstration");
System.out.println("Push elements into the queue like a stack");
System.out.println(" Front- 1,2,3- Rear");
push(1,q2,q1);
push(2,q2,q1);
push(3,q2,q1);
//remover elements from the q1 as poping element from
//the stack
System.out.println("Method2");
System.out.println("Pop element from the stack using Queue");
int element=pop(q1);
System.out.println(element);
}
//insert elment into the queueq2 as like pushing element into stack
private static void push(int element, Queue<Integer>
q2,Queue<Integer>q1)
{
//call add method to insert element into the queue
q2.add(element);
int size=q2.size();
if(size>1)
{
for (int index = 0; index < size-1; index++)
q1.add(q2.remove());
}
}
//Method remove element from the q1 as like poping element from stack
private static int pop(Queue<Integer> q1)
{
return q2.peek();
}
}
---------------------------------------------------------------------------
Sample output:
Method2-Demonstration
Push elements into the queue like a stack
Front- 1,2,3- Rear
Method2
Pop element from the stack using Queue
3
Hope this would helps you.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.