栈和队列

栈

栈简介

• 栈是一种特殊的线性表，它只允许在固定的一端(栈顶top)进行插入和删除操作，栈中的元素遵循LIFO(Last In First Out)原则。

栈的实现

• 在JDK中，栈的实现类是Stack,它的继承关系如下：
  
  从上图可以看到，Stack继承自Vector,Vector与ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。

Stack中的常用方法如下：

方法	功能
Stack()	构造一个空栈
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	返回栈顶元素
int size()	返回栈中有效元素个数
boolean empty()	检查栈是否为空

常用方法时间复杂度：
访问：O(n)
插入删除：O(1)

• 栈的模拟实现
  栈常用数组或链表来实现，用数组实现的叫顺序栈，链表实现的叫链栈。这里我采用数组实现一个简易的栈。

  public class MyStack {
      private int[] elementData;//存储数据的容器
      private int elementCount;//栈中有效元素个数
      private static final int DEFAULT_CAPACITY = 5;
  
      //创建一个空栈
      public MyStack() {
          this.elementData = new int[DEFAULT_CAPACITY];
      }
  
      //入栈
      public int push(int item) {
          ensureCapacityHelper(elementCount);
          elementData[elementCount++] = item;
          return item;
      }
  
      //出栈
      public synchronized int pop() {
          if (size() == 0) {
              throw new EmptyStackException();
          }
          return elementData[--elementCount];
      }
  
      //查看栈顶元素
      public synchronized int peek() {
          if (size() == 0) {
              throw new EmptyStackException();
          }
          return elementData[elementCount - 1];
      }
  
      //判断栈是否为空
      public boolean empty() {
          return size() == 0;
      }
  
      //确认容器大小
      private void ensureCapacityHelper(int elementCount) {
          if (elementCount == elementData.length) {
              elementData = this.grow();
          }
      }
  
      //扩容
      private int[] grow() {
          return Arrays.copyOf(elementData, elementCount << 1);
      }
  
      //栈有效元素个数
      public int size() {
          return elementCount;
      }
  }

• 验证

  public static void main(String[] args) {
      MyStack stack = new MyStack();
      stack.push(1);
      stack.push(2);
      stack.push(3);
      stack.push(5);
      stack.push(6);
      stack.push(7);
      stack.push(8);
      stack.pop();
      System.out.println(stack.peek());//7
      System.out.println(stack.size());//7
      while (!stack.empty()){
          stack.pop();
      }
      System.out.println(stack.empty());//true
      System.out.println(stack.pop());//java.util.EmptyStackException
  }

栈相关的题目

LeetCode 20.有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

public boolean isValid(String s) {
    if (s == null || s.length() < 2 || s.length() % 2 != 0) {
        return false;
    }
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(') stack.push(')');
        else if (c == '[') stack.push(']');
        else if (c == '{') stack.push('}');
        else if (stack.isEmpty() || c != stack.pop()) return false;
    }
    return stack.isEmpty();
}

剑指Offer 31.栈的压入、弹出操作
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列
是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

public boolean validateStackSequences(int[] pushed, int[] popped) {
    if (pushed.length == 0 || popped.length == 0) return true;
    Stack<Integer> num = new Stack<>();
    int res = 0;
    for (int i = 0; i < pushed.length; i++) {
        num.push(pushed[i]);
        while (res < popped.length && !num.isEmpty() && num.peek() == popped[res]) {
            num.pop();
            res++;
        }
    }
    return res == popped.length;
}

LeetCode 155.设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> miniStack;

    public MinStack() {
        stack = new Stack<>();
        miniStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (miniStack.isEmpty() || val <= miniStack.peek()) {
            miniStack.push(val);
        }
    }

    public void pop() {
        if (stack.pop().equals(miniStack.peek())) {
            miniStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return miniStack.peek();
    }
}

队列

队列简介

• 队列只允许在后端(rear)入队，在前端(front)出队，队列中的元素遵循FIFO(First In First Out)原则。

队列的实现

• 队列的访问与插入删除操作的时间复杂度和栈类似，唯一的区别在于队列只允许新元素在其尾端(rear)进行添加。
  Queue中的常用方法如下:

  方法	功能
  boolean offer(E e)	入队列
  E poll()	出队列
  E peek()	返回队头元素
  int size()	返回队列中有效元素个数
  boolean isEmpty()	检查队列是否为空

  部分方法的区别：
  offer()和add():若在队列满的情况下添加元素,add()抛出异常，offer()返回false()。
  poll()和remove():poll()在队列为空的情况下返回null。
  peek()和element():与remove()类似，peek()在队列为空的情况下返回null。

• 队列的模拟实现
  在JDK中，Queue是个接口，底层通过链表实现，我们可以采用Queue<E> queue = new LinkedList<>()来创建一个队列。

  public class MyQueue {
      private static class ListNode {
          int val;
          ListNode prev;
          ListNode next;
  
          public ListNode(int val) {
              this.val = val;
          }
      }
  
      public ListNode head;
      public ListNode tail;
      public int size;
  
      //入队
      public void offer(int val){
          ListNode node = new ListNode(val);
          if (head == null){
              head = node;
          }else {
              tail.next = node;
              node.prev = tail;
          }
          tail = node;
          size++;
      }
  
      //出队
      public Object poll() {
          if (head == null) {
              return null;
          }
          int val = head.val;
          head = head.next;
          if (head == null) {
              tail = null;
          } else {
              head.prev.next = null;//处理前驱节点
              head.prev = null;
          }
          size--;
          return val;
      }
  
      //查看队头元素
      public Object peek(){
          if (head == null){
              return null;
          }
          return head.val;
      }
  
      //查看队列长度
      public int size(){
          return size;
      }
  
      //判断队列是否为空
      public boolean isEmpty(){
          return size == 0;
      }
  }

• 验证

  public static void main(String[] args) {
      MyQueue queue = new MyQueue();
      queue.offer(1);
      queue.offer(2);
      queue.offer(3);
      queue.offer(4);
      queue.offer(5);
      System.out.println(queue.poll());//5
      System.out.println(queue.size());//4
      System.out.println(queue.peek());//4
      while (!queue.isEmpty()){
          queue.poll();
      }
      System.out.println(queue.poll());//null
  }

• 用链表实现的队列称为链式队列，链式队列的好处是除了用来存放指向下一个节点的next指针外，它不会浪费其它空间，且它可以一直入队，直到系统资源耗尽，不存在越界问题。

• 此外，还可以用数组来实现一个队列，称为顺序队列，顺序队列存在假溢出情况，即当我们进行入队、出队操作时，front和rear都会向后移动，当rear移动到最后，我们就不能再向数组内添加元素，但实际上经过出队操作，front之前存在可用空间。为了解决假溢出，我们引入了循环队列。

循环队列

• 当我们把数组首尾相接的时候，无论入队还是出队，front和rear总是在一个闭环内活动，这样就解决了数组假溢出和越界的问题，当front = rear时，队列为空。但由于不断地入队和出队操作，front和rear的总是在变化，我们该如何确定其相对的关系呢？答案就是取余操作。
• 模拟实现

  class MyCircularQueue {
      private int[] element;
      private int front;
      private int rear;
  
      //初始化队列
      public MyCircularQueue(int k) {
          //用冗余空间处理，k + 1
          element = new int[k + 1];
      }
  
      //入队
      public boolean enQueue(int value) {
          if (isFull()) {
              return false;
          }
          element[rear] = value;
          rear = (rear + 1) % element.length;
          return true;
      }
  
      //出队
      public boolean deQueue() {
          if (isEmpty()) {
              return false;
          }
          front = (front + 1) % element.length;
          return true;
      }
  
      //返回队头元素
      public int Front() {
          if (isEmpty()) {
              throw new RuntimeException("队列为空");
          }
          return element[front];
      }
  
      //返回队尾元素
      public int Rear() {
          if (isEmpty()) {
              throw new RuntimeException("队列为空");
          }
          //当rear = 0,此时若直接取rear - 1将数组越界
          int index = (rear - 1 + element.length) % element.length;
          return element[index];
      }
  
      //判断是否队空
      public boolean isEmpty() {
          return front == rear;
      }
  
      //判断是否队满
      public boolean isFull() {//考虑出队front会变，不能(rear + 1) % element.length == 0
          return (rear + 1) % element.length == front;
      }
  }

  同时它也是LeetCode 622.设计循环队列的解法。

队列的拓展

• 阻塞队列(BlockingQueue)：当队列为空时，出队操作阻塞；当队列为满时，入队操作阻塞。主要用于多线程。
• 双端队列(Deque):具有栈和队列的性质，比起栈或队列，它更加灵活，插入和删除操作可在两端进行。

经典题目

以下题目均来自LeetCode。

用两个栈实现队列

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

class CQueue {
    Stack<Integer> A;
    Stack<Integer> B;
    public CQueue() {
        A = new Stack<>();
        B = new Stack<>();
    }
    
    public void appendTail(int value) {
        A.push(value);
    }
    
    public int deleteHead() {
        if(!B.isEmpty()){
            return B.pop();
        }
        if(A.isEmpty()){
            return -1;
        }
        while(!A.isEmpty()){
            B.push(A.pop());
        }
        return B.pop();
    }
}

两个栈实现队列

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

class MyStack {
    Queue<Integer> enQueue;
    Queue<Integer> deQueue;
    public MyStack() {
        enQueue = new LinkedList<>();
        deQueue = new LinkedList<>();
    }
    
    public void push(int x) {
        enQueue.offer(x);
        while(!deQueue.isEmpty()){
            enQueue.offer(deQueue.poll());
        }
        Queue<Integer> tmp = enQueue;
        enQueue = deQueue;
        deQueue = tmp;
    }
    
    public int pop() {
        if(empty()){
            return -1;
        }
        return deQueue.poll();
    }
    
    public int top() {
        if(empty()){
            return -1;
        }
        return deQueue.peek();
    }
    
    public boolean empty() {
        return deQueue.isEmpty();
    }
}