队列实现栈和栈实现队列
程序员文章站
2022-07-10 23:34:15
...
1、如何仅用队列结构实现栈
import java.util.LinkedList;
import java.util.Queue;
//如何仅用队列结构实现栈
/*
①创建两个队列data和help;
②push操作,直接数字add进data队列;
③pop操作,将data中除了队列最后一个之外全部出队poll,
进到help队列中,然后将data中的最后一个元素出队;
然后交换help和data的引用,继续循环,可以将队列中的数一栈的
形式输出来。
④
*/
public class e3_StackQueue {
private Queue<Integer> data;
private Queue<Integer> help;
public e3_StackQueue(){
data=new LinkedList<Integer>();
help=new LinkedList<Integer>();
}
public void push(Integer obj){
data.add(obj);
}
public Integer pop(){
if (data.isEmpty()){
throw new ArrayIndexOutOfBoundsException("Queue is empty");
}
while (data.size()>1){
help.add(data.poll());
}
Integer tem = data.poll();
swap();
return tem;
}
public Integer peek(){
if (data.isEmpty()){
throw new ArrayIndexOutOfBoundsException("Queue is empty");
}
while (data.size()>1){
help.add(data.poll());
}
Integer tem=data.peek();
help.add(data.poll());
swap();
return tem;
}
public void swap(){
Queue<Integer> tem=data;
data=help;
help=tem;
}
public static void main(String[] args) {
e3_StackQueue s=new e3_StackQueue();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(5);
System.out.println(s.data);
System.out.println("栈的peek操作:");
System.out.println(s.peek());
System.out.println("栈的pop操作,pop两次");
System.out.println(s.pop());
System.out.println(s.pop());
}
}
2、如何仅用栈结构实现队列
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/*
①创建两个栈pushStack和popStack;
②进队操作,正常使用pushStack.push()的方法;
③出队操作,让pushStack栈的每个元素都弹出来,并依次压到popStack中。
(就像倒水一样,从pushStack到popStack)
出队操作就可以通过栈popStack.pop实现了
*/
public class e4_StackQueue {
private Stack<Integer> pushStack;
private Stack<Integer> popStack;
public e4_StackQueue(){
pushStack=new Stack<Integer>();
popStack=new Stack<Integer>();
}
public void push(Integer obj){
pushStack.push(obj);
}
public Integer pop(){
if (popStack.isEmpty()&&pushStack.isEmpty()){
throw new ArrayIndexOutOfBoundsException("Queue is empty1");
}
pouraway();
return popStack.pop();
}
public Integer peek(){
if (!popStack.isEmpty()){
throw new ArrayIndexOutOfBoundsException("Queue is empty2");
}
pouraway();
return popStack.peek();
}
public void pouraway(){
//PopStack必须为空才能倒数据
if (!popStack.isEmpty()){
return;
}//倒数据要一次倒完
while (!pushStack.isEmpty()){
popStack.push(pushStack.pop());
}
}
public static void main(String[] args) {
e4_StackQueue q=new e4_StackQueue();
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
System.out.println(q.pushStack);
System.out.println("队列的peek操作:");
System.out.println(q.peek());
System.out.println("队列的poll操作,poll两次");
System.out.println(q.pop());
System.out.println(q.pop());
}
}