队列和栈

数组实现队列

public class MyQueue {
	private int[] arr;
	private int pushi;
	private int polli;
	private int size;
	private final int limit;

	public MyQueue(int limit) {
		this.limit = limit;
		pushi = 0;// 头指针
		polli = 0;// 尾指针
		size = 0;
		arr = new int[limit];
	}

	public void push(int value) {
		if (size == limit) {
			throw new RuntimeException("队列已满 无法继续添加");
		}
		size++;
		arr[pushi] = value;
		pushi = nextIndex(pushi);
	}

	public int pop(int value) {
		if (size == 0) {
			throw new RuntimeException("队列为空");
		}
		size--;
		int ans = arr[polli];
		polli = nextIndex(polli);
		return ans;

	}

	public boolean isEmpty() {
		return size == 0;
	}

	private int nextIndex(int index) {
		// index = (index+1) % limit;
		return index < limit - 1 ? index + 1 : 0;
	}

}

栈实现队列

// 使用两个栈实现
	public static class Myqueue {
		private Stack<Integer> StackPull;
		private Stack<Integer> StackPop;
       
	public Myqueue() {
		StackPull = new Stack<Integer>();
		StackPop = new Stack<Integer>();
	}

	public void push(int value) {
		StackPull.push(value);
		pushToPop();
	}

	private void pushToPop() {
		if (StackPop.isEmpty()) {
			while (!StackPull.isEmpty()) {
				StackPop.push(StackPull.pop()); // 将栈顶 压到 pop栈中
			}
		}

	}

	public int pop() {
		if (StackPull.isEmpty() && StackPop.isEmpty()) {
			throw new RuntimeException("队列中无元素");
		}
		pushToPop();
		return StackPop.pop();
	}

	public int peek() {
		if (StackPull.isEmpty() && StackPop.isEmpty()) {
			throw new RuntimeException("队列中无元素");
		}
		pushToPop();
		return StackPop.peek();
	}

}

public static void main(String[] args) {
	Myqueue test = new Myqueue();
	test.push(1);
	test.push(2);
	test.push(5);
	System.out.println(test.peek());
	System.out.println(test.pop());
	System.out.println(test.peek());
	System.out.println(test.pop());
	System.out.println(test.peek());
	System.out.println(test.pop());
}

队列实现栈

// 两个队列实现
	public static class TwoQueueStack<T> {
		public Queue<T> queue;
		public Queue<T> help;

		public TwoQueueStack() {
			queue = new LinkedList<>();
			help = new LinkedList<>();
		}

		public void push(T value) {
			queue.offer(value); // 加入到队尾
		}

		public T pop() {
			while (queue.size() > 1) {
				help.offer(queue.poll()); // 除了队尾的元素 全部转移到另外一个队列中
			}
			T ans = queue.poll(); // 当前队尾元素为栈顶
			Queue<T> tep = queue; // 缓存当前空队列
			queue = help; // 重新转移到queue中
			help = tep;
			return ans;
		}

		public T peek() {
			while (queue.size() > 1) {
				help.offer(queue.poll());
			}
			T ans = queue.poll();
			help.offer(ans); // 由于是查看栈顶 所以获取到值后 重新添加到另外队列中
			Queue<T> tep = queue;
			queue = help;
			help = tep;
			return ans;
		}

		public boolean isEmpty() {
			return queue.isEmpty();
		}

	}