剑指 Offer 09. 用两个栈实现队列

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

剑指offer--栈与队列 - 图1
image.png

  1. class CQueue {
  2.     Deque<Integer> stackin;
  3.     Deque<Integer> stackout;
  5.     public CQueue() {
  6.         stackin = new LinkedList<>();
  7.         stackout = new LinkedList<>();
  8.     }
  10.     public void appendTail(int value) {
  11.         stackin.push(value);
  12.     }
  14.     public int deleteHead() {
  15.         if(stackout.isEmpty()){
  16.             while(!stackin.isEmpty()){
  17.                 stackout.push(stackin.pop());
  18.             }
  19.         }
  20.         // if(!stackout.isEmpty()){
  21.         //     return stackout.pop();
  22.         // }else{
  23.         //     return -1;
  24.         // }
  25.         return !stackout.isEmpty() ? stackout.pop(): -1;
  26.     }
  27. }
  29. /**
  30.  * Your CQueue object will be instantiated and called as such:
  31.  * CQueue obj = new CQueue();
  32.  * obj.appendTail(value);
  33.  * int param_2 = obj.deleteHead();
  34.  */

225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。 实现 MyStack 类： void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。 boolean empty() 如果栈是空的，返回 true ；否则，返回 false

剑指offer--栈与队列 - 图3

一个队列

.image.png
image.png

两个队列

  1. class MyStack {
  2.     Queue<Integer> queue1;
  3.     Queue<Integer> queue2;
  5.     /** Initialize your data structure here. */
  6.     public MyStack() {
  7.         queue1 = new LinkedList<Integer>();
  8.         queue2 = new LinkedList<Integer>();
  9.     }
  11.     /** Push element x onto stack. */
  12.     public void push(int x) {
  13.         queue2.offer(x);
  14.         while (!queue1.isEmpty()) {
  15.             queue2.offer(queue1.poll());
  16.         }
  17.         Queue<Integer> temp = queue1;
  18.         queue1 = queue2;
  19.         queue2 = temp;
  20.     }
  22.     /** Removes the element on top of the stack and returns that element. */
  23.     public int pop() {
  24.         return queue1.poll();
  25.     }
  27.     /** Get the top element. */
  28.     public int top() {
  29.         return queue1.peek();
  30.     }
  32.     /** Returns whether the stack is empty. */
  33.     public boolean empty() {
  34.         return queue1.isEmpty();
  35.     }
  36. }

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

image.png
剑指offer--栈与队列 - 图7
image.png

剑指 Offer 30. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

image.png
image.png
image.png

  1. class MinStack {
  2.     Stack<Integer> stack;//实际数据栈
  3.     Stack<Integer> minStack;//辅助栈，栈顶一直存储当前最小元素，数据个数和实际数据栈中个数一致
  5.     /** initialize your data structure here. */
  6.     public MinStack() {
  7.         stack = new Stack<>();
  8.         minStack = new Stack<>();
  10.     }
  12.     public void push(int x) {
  13.         stack.push(x);
  14.         //辅助栈为空或者当前入栈元素小于之前的最小值，说明当前元素就是最小值
  15.         if(minStack.isEmpty() || x < minStack.peek()){
  16.             minStack.push(x);
  17.         }else{//辅助栈顶元素仍然是最小的，让他再次入栈
  18.             int temp = minStack.peek();
  19.             minStack.push(temp);    
  20.         }
  21.     }
  23.     public void pop() {
  24.         stack.pop();
  25.         //数据栈弹出了一个元素，辅助栈相应弹出一个元素
  26.         minStack.pop();
  27.     }
  29.     public int top() {
  30.         return stack.peek();
  31.     }
  33.     public int min() {
  34.         return minStack.peek();
  35.     }
  36. }
  37. /**
  38.  * Your MinStack object will be instantiated and called as such:
  39.  * MinStack obj = new MinStack();
  40.  * obj.push(x);
  41.  * obj.pop();
  42.  * int param_3 = obj.top();
  43.  * int param_4 = obj.min();
  44.  */

剑指 Offer 31. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

image.png
image.png

剑指 Offer 59 - II. 队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

image.png
image.png