用两个栈实现队列

用两个栈实现队列

​ 题目描述

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

​ 示例

// 1 输入： ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[],[]] 输出：[null,null,3,-1] // 2 输入： ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"] [[],[],[5],[2],[],[]] 输出：[null,-1,null,null,5,2]

1：双栈

栈：先进后出，队列：先进先出

假定有两个栈：stack1，stack2。stack1支持插入，stack2支持删除appendTail方法：直接在stack1中插入deleteHead方法： 判断stack2是否为空：stack2为空时，再次判断stack1是否为空，不为空情况下需要将stack1中的元素弹出加入到stack2中；stack2不为空时，直接弹出元素 class CQueue { Stack<Integer> stack1; Stack<Integer> stack2; public CQueue() { stack1 = new Stack<>(); stack2 = new Stack<>(); } public void appendTail(int value) { stack1.push(value); } public int deleteHead() { if(stack2.isEmpty()) { if(stack1.isEmpty()) return -1; while(!stack1.isEmpty()) { stack2.push(stack1.pop()); } return stack2.pop(); } else { return stack2.pop(); } } }

时间复杂度：O(1)，空间复杂度：O(n)