题目

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTaildeleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,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 <= values <= 10000
  • 最多会对 appendTail、deleteHead 进行 10000 次调用

解题思路

1、双栈法

维护两个栈,第一个栈支持插入操作,第二个栈支持删除操作。将第一个栈记作 stack ,存储正序的结果。将第二个栈记作 reverseStack ,存储的是 stack 的逆序结果。举个例子,比如当 stack 由底至顶的顺序是:123 时,reverseStack 由底至顶的顺序应是:321 。

根据题意,我们需要用两个栈来模拟队列,并且实现队列的两个函数,分别是添加至队尾(appendTail)和删除队头(deleteHead)。

1、appendTail(添加至队尾)
我们可以将数据压入到 stack 中,也就是正序栈。并且,在将数据压入到 stack 后,生成一个 stack 的逆序结果,将其写入 reverseStack 中。

2、deleteHead(删除队头)
由于 reverseStack 中栈顶元素就是队头,将其 pop 掉就可以。再根据 pop 后的 reverseStack 生成一个 reverseStack 的逆序结果(逆序的逆序,也就是正序 stack 了)。

复杂度分析:

  • 时间复杂度 O(N): 最多循环 n - 1 次(n>=2)。
  • 空间复杂度 O(1): 额外维护两个变量,常数级。

实现

1、双栈法

  1. class CQueue {
  2. // 正序栈
  3. private Stack<Integer> stack = new Stack();
  4. // 逆序栈
  5. private Stack<Integer> reverseStack = new Stack();
  6. public CQueue() {
  7. }
  8. // 附加到队列尾部
  9. public void appendTail(int value) {
  10. // 先压到正序栈
  11. stack.push(value);
  12. // 更新逆序栈数据
  13. Stack<Integer> tempStack = (Stack<Integer>) stack.clone();
  14. Stack<Integer> tempReverseStack = new Stack<>();
  15. while (tempStack.isEmpty() != true) {
  16. int result = tempStack.pop();
  17. tempReverseStack.push(result);
  18. }
  19. reverseStack = tempReverseStack;
  20. }
  21. public int deleteHead() {
  22. // 为空
  23. if (reverseStack.isEmpty()) {
  24. return -1;
  25. }
  26. // 对逆序
  27. int result = reverseStack.pop();
  28. // 更新正序栈数据
  29. Stack<Integer> tempReverseStack = (Stack<Integer>) reverseStack.clone();
  30. Stack<Integer> tempStack = new Stack<>();
  31. while (tempReverseStack.isEmpty() != true) {
  32. tempStack.push(tempReverseStack.pop());
  33. }
  34. stack = tempStack;
  35. return result;
  36. }
  37. }
  38. /**
  39. * Your CQueue object will be instantiated and called as such:
  40. * CQueue obj = new CQueue();
  41. * obj.appendTail(value);
  42. * int param_2 = obj.deleteHead();
  43. */

image.png