[笔记]算法复习笔记---栈、队列、链表（中）

一、用两个栈来实现队列

方法：
入队都在Stack1中操作，出队都在Stack2中进行，入队和出队的规则如下：
入队：直接把元素压入Stack1中。
出队：如果Stack2不为空，直接弹出stack2的元素，如果stack2为空，将stack1中所有元素倒入stack2，然后弹出stack2栈顶元素。如果两个队列都空，队列为空队，无法出栈。

public class Stack2Queue {
	
	private Stack stack1; 
	private Stack stack2; 
	private int maxLength;
	
	public Stack2Queue( int capacity) {
		maxLength = capacity;
		stack1 = new Stack(capacity);
		stack2 = new Stack(capacity);
	}
	
	public boolean put(int item) {
		if (stack1.isFull() || maxLength == size()) {
			//满了
			return false;
		}
		
		stack1.push(item);
		return true;
	}
	
	public int  poll() {
		if (!stack2.isEmpty()) {
			return stack2.pop();
		}else {
			while (!stack1.isEmpty()) {
				stack2.push(stack1.pop());
			}
			return stack2.pop();
		}
	}
	public int size() {
		return stack1.size() + stack2.size();
	}

}

public class Stack2QueueTest {
	
	public static void main(String[] args) {
		Stack2Queue queue = new Stack2Queue(5);
		queue.put(1);
		queue.put(2);
		System.out.println(queue.poll());//1
		queue.put(3);
		queue.put(4);
		System.out.println(queue.poll());//2
		System.out.println(queue.poll());//3,这次操作中，把3，4两个元素从stack1倒入stack2
		
	}
}

##二、两个队列实现栈

方案：

• 入栈：两个队列那个不为空，就把元素入队到那个队列中；如果都为空，则任选一个入队，假设这个队列为queue1

• 出栈：把不为空的队列去除最后一个元素外的所有元素移动到另一个队列中，然后出队最后一个元素。

  下面是实现代码：

public class Queue2Stack {
	
	private ArrayQueue queue1;
	private ArrayQueue queue2;
	private int maxLength;
	
	public Queue2Stack(int capacity) {
		maxLength = capacity;
		queue1 = new ArrayQueue(capacity);
		queue2 = new ArrayQueue(capacity);
	}
	
	/**
	 * 入栈
	 * @param item
	 * @return 入栈结果
	 */
	public boolean push(int item) {
		
		if (size() == maxLength) {
			return false;
		}
		if (queue2.isEmpty()) {
			queue1.put(item);
		}else{
			queue2.put(item);
		}
		return true;
	}
	
	public Object pop() {
		if (size() == 0) {
			throw new IndexOutOfBoundsException("栈里空了");
		}else{
			if (queue2.isEmpty()) {
				while (queue1.Size() > 1) {
					queue2.put(queue1.poll());
				}
				return queue1.poll();
			}else{
				while (queue2.Size() > 1) {
					queue1.put(queue2.poll());
				}
				return queue2.poll();
			}
		}
	}
	
	public int size() {
		return queue1.Size() + queue2.Size();
	}
}

public class Queue2StackTest {
	
	public static void main(String[] args) {
		Queue2Stack stack = new Queue2Stack(5);
		stack.push(1);
		stack.push(2);
		System.out.println(stack.pop());//2
		
		stack.push(3);
		stack.push(4);
		System.out.println(stack.pop());//4
		System.out.println(stack.pop());//3
	}
}