155-最小栈

思路：

  • minStack 只放入最小值。
  • minStack 和 dataStack 同时放入值。

image.png
代码：

  1. public class MinStack_155 {
  3.     Deque<Integer> xStack;
  4.     Deque<Integer> minStack;
  6.     /** initialize your data structure here. */
  7.     public MinStack_155() {
  8.         xStack = new LinkedList<>();
  9.         minStack = new LinkedList<>();
  10.         minStack.push(Integer.MAX_VALUE);
  11.     }
  13.     public void push(int val) {
  14.         xStack.push(val);
  15.         if (!minStack.isEmpty())
  16.             minStack.push(Math.min(val, minStack.peek()));
  17.         else
  18.             minStack.push(val);
  19.     }
  21.     public void pop() {
  22.         if (!xStack.isEmpty() && !minStack.isEmpty()) {
  23.             xStack.pop();
  24.             minStack.pop();
  25.         }
  26.     }
  28.     public int top() {
  29.         return xStack.peek();
  30.     }
  32.     public int getMin() {
  33.         return minStack.peek();
  34.     }
  36.     public static void main(String[] args) {
  37.         MinStack_155 minStack = new MinStack_155();
  38.         minStack.push(-2);
  39.         minStack.push(0);
  40.         minStack.push(-3);
  41.         System.out.println(minStack.getMin());   //--> 返回 -3.
  42.         minStack.pop();
  43.         System.out.println(minStack.top());      //--> 返回 0.
  44.         System.out.println(minStack.getMin());   //--> 返回 -2.
  46.     }
  47. }

232-用栈实现队列

image.png
代码：

  1. public class StackToQueue_232 {
  2.     Deque<Integer> inStack;
  3.     Deque<Integer> outStack;
  5.     public StackToQueue_232() {
  6.         inStack = new LinkedList<>();
  7.         outStack = new LinkedList<>();
  8.     }
  10.     public void push(int x) {
  11.         inStack.push(x);
  12.     }
  14.     public int pop() {
  15.         if (outStack.isEmpty()) {
  16.             in2out();
  17.         }
  18.         return outStack.pop();
  19.     }
  21.     public int peek() {
  22.         if (outStack.isEmpty()) {
  23.             in2out();
  24.         }
  25.         return outStack.peek();
  26.     }
  28.     public boolean empty() {
  29.         return inStack.isEmpty() && outStack.isEmpty();
  30.     }
  32.     public void in2out () {
  33.         while (!inStack.isEmpty()) {
  34.             outStack.push(inStack.pop());
  35.         }
  36.     }
  38.     public static void main(String[] args) {
  39.         StackToQueue_232 myQueue = new StackToQueue_232();
  40.         myQueue.push(1); // queue is: [1]
  41.         myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
  42. //        myQueue.printQueue();
  44.         System.out.println(myQueue.peek()); // return 1
  45.         System.out.println(myQueue.pop()); // return 1, queue is [2]
  46.         System.out.println(myQueue.pop());
  47.         System.out.println(myQueue.empty()); // return false
  49.     }
  50. }

225-用队列实现栈

image.png
代码：

  1. public class QueueToStack_225 {
  3.     /**
  4.      * queue1 作为出栈元素的队列
  5.      * queue2 作为入栈元素的辅助队列，并且入栈操作后 queue2 永远是空队列
  6.      */
  7.     Queue<Integer> queue1;
  8.     Queue<Integer> queue2;
  10.     public QueueToStack_225() {
  11.         queue1 = new LinkedList<>();
  12.         queue2 = new LinkedList<>();
  13.     }
  15.         public void push(int x) {
  16.             queue2.offer(x);
  17.             while (!queue1.isEmpty()) {
  18.                 queue2.offer(queue1.poll());
  19.             }
  20.             // 交换 queue1 和 queue2 队列
  21.             Queue<Integer> tmp = queue1;
  22.             queue1 = queue2;
  23.             queue2 = tmp;
  24.         }
  26.         public int pop() {
  27.             return queue1.poll();
  28.         }
  30.         public int top() {
  31.             return queue1.peek();
  32.         }
  34.         public boolean empty() {
  35.             return queue1.isEmpty();
  36.         }
  38.         public static void main(String[] args) {
  39.             QueueToStack_225 myStack = new QueueToStack_225();
  40.             myStack.push(1);
  41.             myStack.push(2);
  42.             System.out.println(myStack.top()); // 返回 2
  43.             System.out.println(myStack.pop()); // 返回 2
  44.             myStack.empty(); // 返回 False
  46.         }
  47. }