Queue using two stacks
Algorithm
Input An integer to be enqueue.
Output An integer to be dequeue.
Complexity O(n).
Enqueue()
1. Top1= Top1 +1;
2. A1[Top1]=item;
Dequeue()
1. If(Top=-1)then
Print queue is empty;
2. While(top1>=0)
Do
Top2=Top2+1;
A2[Top2]=A1[Top1];
Top1=Top1-1;
End of loop.
3. Print A2[Top2];
4. Top2=Top2-1;
5. While(Top2>=0)
Top1=Top1+1;
A1[Top1]=A2[Top2];
Top2 =Top2-1;
Algorithm Description
We are using two array A1 and A2 as a stack. Top1 and Top2 are used as a stack pointer respectively. Enqueue() This function push an element in the array A1 ; Dequeue() 1. Check boundary condition to know whether an element in the stack or not. 2. Transfer all element of array A1 to array A2 to reverse the order of elements. 3. Pop and Ptint the top element of array A2. 4. Decrease the Top pointer; 5. Transfer all elements of array A2 to array A1.
Java Code
import java.io.*;
class stack{
int stck[] = new int[10];
int tos;
stack(){
tos=-1;
}
boolean is_empty(){
if(tos<0)
return true;
else
return false;
}
boolean is_full(){
if(tos==9)
return true;
else
return false;
}
void push(int item){
if(is_full())
System.out.println("stack is full");
else
stck[++tos]=item;
}
int pop(){
if(is_empty()){
System.out.println("queue is empty");
return 0;
}
else
return stck[tos--];
}
void traverse(){
if(is_empty()){
System.out.println("queue is empty");
}else
for(int i=0;i<=tos;i++)
System.out.println(stck[i]);
}
void peek(){
System.out.print(stck[tos]);
}
}
class q_2stack{
public static void main(String args[])
throws java.io.IOException{
stack st1 = new stack();
stack st2 = new stack();
int choice=0;
int value,st=1;
BufferedReader br= new BufferedReader (new InputStreamReader(System.in));
while(choice!=4){
System.out.println("1.insert 2.delete 3.traverse 4.quit");
System.out.println("enter your choice");
choice=Integer.parseInt(br.readLine());
switch(choice){
case 1:
System.out.println("enter the value you want to insert");
value=Integer.parseInt(br.readLine());
if(st==1)
st1.push(value);
else
st2.push(value);
break;
case 2:if(st==1){
while(!st1.is_empty())
st2.push(st1.pop());
System.out.println(st2.pop()+"deleted");
}
else{
while(!st2.is_empty())
st1.push(st2.pop());
System.out.println(st1.pop()+"deleted");
}
break;
case 3:
if(st==1)
st1.traverse();
else
st2.traverse();
break;
case 4:
break;
default:
System.out.println("wrong choice");
break;
}
}
}
}
