用两个栈实现队列

问题描述

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能

思路分析

根据栈先进后出的特点，一个栈push元素后，另一个栈可push进它出栈的元素，这样存储的不就是原先顺序的元素吗，也就是原先栈顶元素现在在栈底

码上有戏

public class CQueue<T> {

	private Stack<T> stack1=new Stack<>();
	 private Stack<T> stack2=new Stack<>();
	 
	 public void appendTail(T t){
		 stack1.push(t);
	 }
	 
	 public T deleteHead() throws Exception{
		 if(stack2.isEmpty())
		 {
			 while(!stack1.isEmpty()){
				 stack2.push(stack1.pop());
			 }
		 }
		 if(stack2.isEmpty()){
			 throw new Exception("队列为空！不能删除");
		 }
		 return stack2.pop();
	 }
	
	
	public static void main(String[] args) throws Exception {
		CQueue queue=new CQueue<>();
		queue.appendTail(1);
		queue.appendTail(2);
		queue.appendTail(3);
		System.out.println(queue.deleteHead());
		System.out.println(queue.deleteHead());
		System.out.println(queue.deleteHead());
	}

}

两个队列实现一个栈

有了上面的经验，我们发现，可以用同样的思想去实现两个队列实现一个栈，当然还是有点不一样的
它的核心思想就是将一个队列的元素除队尾元素都放到另一个队列中，轮流操作就是栈了

码上有戏

private Queue<T> queue1=new ArrayBlockingQueue(10);
   private Queue<T> queue2=new ArrayBlockingQueue(10);
    private boolean flag=false;
 
   public void push(T t){
	   if(queue2.isEmpty())
	     queue1.add(t);
	   else if(queue1.isEmpty())
		   queue2.add(t);
	   else{
		   return;
	   }
   }
   
   public Queue pop()throws Exception{
	   int len;
	   int count=1;
	   if(queue2.isEmpty())
	   {
		   len=queue1.size();
		   while(!flag&&count<len){
			   queue2.add(queue1.poll());
			   count++;
		   }
		   flag=true;
		   queue1.poll();
		   count=1;
		   return  queue2;
	   }
	   else if(queue1.isEmpty()){
		   len=queue2.size();
		   while(flag&&count<len){
			   queue1.add(queue2.poll());
			   count++;
		   }
		   flag=false;
		   queue2.poll();
		   count++;
		   return  queue1;
	   }
	   else if(queue1.isEmpty()&&queue2.isEmpty()){
		   System.out.println("error");
		   return null;
	   }
	   else{
		   
	   }
	return null;
   }

测试：

queue.push(“a”);
queue.push(“b”);
queue.push(“c”);
System.out.println(queue.pop().toString());
System.out.println(queue.pop().toString());
queue.push(“d”);
System.out.println(queue.pop().toString());

结果：

[a, b]
[a]
[a]