# 栈和队列

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

## 单链表实现队列

```java
/**
 * 单链表实现队列
 * @param <T> 内部的数据类型
 */
static class MyQueue<T> {

  static class Node<T> {
    T value;
    Node<T> next;

    public Node(T data) {
      this.value = data;
    }
  }

  private Node<T> head;

  private Node<T> tail;

  private int size;

  public int size() {
    return this.size;
  }

  public void put(T value) {
    Node<T> node = new Node<>(value);
    if (head == null) {
      head = node;
    } else {
      tail.next = node;
    }
    tail = node;
    this.size++; 
  }

  public T peek() {
    return this.head != null ? this.head.value : null;
  }

  public T poll() {
    T result = null;
    if (this.head != null) {
      result = this.head.value;
      this.head = this.head.next;
      this.size--;
    }

    // 移除最后一个元素时，需要将尾部置空，否则可能存在垃圾对象的问题
    if (this.head == null) {
      tail = null;
    }
    return result;
  }
}

@Test
public void testMyQueue() {
  MyQueue<String> queue = new MyQueue<>();
  queue.put("a");
  queue.put("b");
  queue.put("c");
  Assert.assertEquals(queue.size, 3);
  Assert.assertEquals(queue.peek(), "a");
  Assert.assertEquals(queue.poll(), "a");
  Assert.assertEquals(queue.poll(), "b");
  Assert.assertEquals(queue.poll(), "c");
  Assert.assertEquals(queue.size, 0);
  Assert.assertNull(queue.head);
  Assert.assertNull(queue.tail);
}
```

## 单链表实现栈

```java
/**
 * 单链表实现栈
 * @param <T> 值类型参数
 */
public static class MyStack<T> {
  static class Node<V> {
    V value;

    Node<V> next;

    public Node(V value) {
      this.value = value;
    }
  }

  private Node<T> head;

  private int size;

  public int size() {
    return this.size;
  }

  public void push(T value) {
    Node<T> node = new Node<>(value);
    if (head != null) {
      node.next = head;
    }
    head = node;
    this.size++;
  }

  public T pop() {
    if (size == 0) {
      return null;
    }
    T value = head.value;
    this.head = head.next;
    this.size--;
    return value;
  }
}


@Test
public void testMyStack() {
  MyStack<String> stack = new MyStack<>();
  Assert.assertEquals(stack.size, 0);
  stack.push("a");
  stack.push("b");
  stack.push("c");
  Assert.assertEquals(stack.size, 3);
  Assert.assertEquals(stack.pop(), "c");
  Assert.assertEquals(stack.pop(), "b");
  Assert.assertEquals(stack.pop(), "a");
  Assert.assertEquals(stack.size, 0);

}
```

## 双链表实现双端队列

**双端队列**：支持`lpush`、`rpush`、`lpoll`、`rpoll`

```java
/**
 * 双链表实现双端队列
 *
 * @param <T> 节点内容类型参数
 */
public static class MyDeque<T> {

  static class Node<V> {
    V value;
    Node<V> next;
    Node<V> last;

    public Node(V value) {
      this.value = value;
    }
  }

  private Node<T> left;

  private Node<T> right;

  private int size;

  public int size() {
    return this.size;
  }

  public void lpush(T value) {
    Node<T> node = new Node<>(value);
    if (this.left == null) {
      this.right = node;
    } else {
      this.left.last = node;
      node.next = this.left;
    }
    this.left = node;
    this.size++;
  }

  public void rpush(T value) {
    Node<T> node = new Node<>(value);
    if (this.right == null) {
      this.left = node;
    } else {
      this.right.next = node;
      node.last = this.right;
    }
    this.right = node;
    this.size++;
  }

  public T lpoll() {
    if (this.size == 0) {
      return null;
    }

    T result = this.left.value;
    if (this.size == 1) {
      this.left = null;
      this.right = null;
    } else {
      this.left = this.left.next;
      this.left.last = null;
    }
    this.size--;
    return result;
  }

  public T rpoll() {
    if (this.size == 0) {
      return null;
    }

    T result = this.right.value;
    if (this.size == 1) {
      this.left = null;
      this.right = null;
    } else {
      this.right = this.right.last;
      this.right.next = null;
    }
    this.size--;
    return result;
  }
}


@Test
public void testMyDeque() {
  MyDeque<String> deque = new MyDeque<>();
  Assert.assertEquals(deque.size(), 0);
  deque.lpush("a");
  deque.lpush("b");
  Assert.assertEquals(deque.size(), 2);
  deque.rpush("c");
  deque.rpush("d");
  Assert.assertEquals(deque.size(), 4);
  Assert.assertEquals(deque.lpoll(), "b");
  Assert.assertEquals(deque.lpoll(), "a");
  Assert.assertEquals(deque.rpoll(), "d");
  Assert.assertEquals(deque.rpoll(), "c");
  Assert.assertEquals(deque.size(), 0);
}
```

## 数组实现栈

给定一个指定长度l的栈，创建一个长度为l的数组，并设置栈顶的索引。初始化为0，每当有数据压栈时，索引+1，出栈时，索引-1。移除元素不需要删除元素，只需要移动索引位置即可。

java代码如下：

```java
/**
 * 使用数组实现栈结构
 */
static class MyArrayStack {
  private final int[] array;

  private int cur; // 当前位置的索引，代表下一个可填充的位置

  public MyArrayStack(int size) {
    if (size < 1) {
      throw new IllegalArgumentException();
    }
    array = new int[size];
    cur = 0;
  }

  public void push(int value) {
    if (cur == array.length) {
      throw new IllegalArgumentException("栈已经满了");
    }
    array[cur] = value;
    cur++;
  }

  public int pop() {
    if (cur == 0) { // 没有元素
      throw new IllegalArgumentException("栈已经空了不能再取了");
    }
    return array[cur - 1];
  }
}
```

## 数组实现队列

```java
/**
 * 使用数组实现队列 
 * 使用环形buffer，两个指针表示开始与结尾的位置。 
 * 将队列长度与数组长度比较，避免处理两个指针之间复杂的前后关系
 */
static class MyArrayQueue {
  private final int[] array;
  private int pushIndex;
  private int popIndex;
  private final int limit;
  private int size;

  public MyArrayQueue(int limit) {
    if (limit <= 0) {
      throw new IllegalArgumentException();
    }
    this.pushIndex = 0;
    this.popIndex = 0;
    this.limit = limit;
    this.size = 0;
    this.array = new int[limit];
  }

  public void push(int value) {
    if (this.size == this.limit) {
      throw new RuntimeException("队列已经满了");
    }
    array[this.pushIndex] = value;
    size++;
    pushIndex = nextIndex(pushIndex);
    pushIndex++;
  }

  public int pop() {
    if (this.size == 0) {
      throw new RuntimeException("队列已经空了，没有元素可以弹出");
    }
    size--;
    int res = array[popIndex];
    popIndex = nextIndex(popIndex);
    return res;
  }

  // 计算下一次的索引值（环状）
  private int nextIndex(int index) {
    return index == this.limit - 1 ? 0 : index + 1;
  }

  public boolean isEmpty() {
    return this.size == 0;
  }
}
```

## 可以返回最小元素的栈

实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能

1. pop、push、getMin操作的时间复杂度都是 O(1)
2. 设计为栈类型可以使用现成的栈结构

**思路：**

```
假设有一个空栈，
向栈中填入5 => [5]          此时，最小值为5
向栈中填入7 => [5, 7]       此时，最小值为5
向栈中填入6 => [5, 7, 6]    此时，最小值为5
向栈中填入4 => [5, 7, 6, 4] 此时，最小值为4
```

创建两个栈，一个栈用于保存元素，另一个栈用于记录这个栈某个状态下的最小元素，如下图：

右侧栈记录上次的状态的最小值，每次push，只要判断当前值与上次最小值得大小关系，即可得到这次push状态的最小值信息。

**代码：**

```java
static class MyMinStack {
  private final Stack<Integer> dataStack;
  private final Stack<Integer> minStack;

  public MyMinStack() {
    this.dataStack = new Stack<>();
    this.minStack = new Stack<>();
  }

  public void push(int data) {
    if (dataStack.size() == 0) {
      this.minStack.push(data);
    } else {
      int preMin = this.minStack.peek();
      this.minStack.push(Math.min(preMin, data));
    }
    this.dataStack.push(data);
  }

  public int pop() {
    this.minStack.pop();
    return this.dataStack.pop();
  }

  public int getMin() {
    return this.minStack.peek();
  }
}

@Test
public void testStackMin() {
  MyMinStack stack = new MyMinStack();
  stack.push(5);
  Assert.assertEquals(stack.getMin(), 5);

  stack.push(7);
  Assert.assertEquals(stack.getMin(), 5);

  stack.push(6);
  Assert.assertEquals(stack.getMin(), 5);

  stack.push(4);
  Assert.assertEquals(stack.getMin(), 4);
}
```

## 使用队列结构实现栈结构

准备两个队列，分别为主队列和辅队列。当调用`push`方法时，向主队列添加元素。当调用pop方法弹出元素时，将最后一个元素之前的所有元素弹出到辅队列中，最后将主队列的元素弹出给方法，最后交换主队列与辅队列，即可完成栈的功能。

```java
 /**
  * 使用队列实现栈
  */
static class QueueStack {
  private Queue<Integer> mainQueue;
  private Queue<Integer> helperQueue;

  public QueueStack() {
    mainQueue = new ArrayDeque<>();
    helperQueue = new ArrayDeque<>();
  }

  public void push(Integer value) {
    mainQueue.add(value);
  }

  public Integer pop() {
    while (mainQueue.size() != 1) {
      helperQueue.add(mainQueue.poll());
    }
    Queue<Integer> mainTemp = mainQueue;
    this.mainQueue = helperQueue;
    this.helperQueue = mainTemp;
    return helperQueue.poll();
  }
}
```

## 使用栈结构实现队列结构

如图所示：

* 队列包含两个栈，一个用于push，一个用于pop

* 向队列中添加四个元素，1，2，3，4，向push栈中依次放入他们

* 出队一个元素1，将push栈中的所有元素，压栈到pop栈中，并弹出栈顶元素1

* 入队一个元素5，将元素5压入push栈中

* 出队第二个元素2，这里如果pop栈不为空，那么直接弹出pop栈的栈顶

* 一直弹出到5，当pop栈为空时，将push栈的所有元素压入到pop栈中，并弹出栈顶，这个过程与第一个元素相同

代码如下：

```java
/**
 * 使用栈实现队列
 */
static class StackQueue {
  private final Stack<Integer> push;
  private final Stack<Integer> pop;
  public StackQueue() {
    this.push = new Stack<>();
    this.pop = new Stack<>();
  }

  public void push(Integer value) {
    push.push(value);
  }

  public Integer pop() {
    if (pop.size() == 0 && push.size() == 0) {
      throw new RuntimeException("没有元素可以弹出 ");
    }
    if (pop.size() == 0) {
      while (!push.isEmpty()) {
        pop.push(push.pop());
      }
    }
    return pop.pop();
  }
}

@Test
public void testStackQueue() {
  StackQueue sq = new StackQueue();
  sq.push(1);
  sq.push(2);
  sq.push(3);
  sq.push(4);
  System.out.println(sq.pop());
  sq.push(5);
  System.out.println(sq.pop());
  System.out.println(sq.pop());
  System.out.println(sq.pop());
  System.out.println(sq.pop());
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yangsx95.gitbook.io/notes/computer-science/shu-ju-jie-gou-he-suan-fa/zhan-he-dui-lie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.