万隆的笔记
2022-02-13
目录

栈和队列

# 栈和队列

栈和队列是算法中经典的逻辑概念，两个都是线性排列的数据结构，两者具有相似性，所以常常放在一起讲解。

栈的特点是数据先进后出，生活中例如弹夹、摞书等。而队列的特点是数据先进先出，生活中的排队、一截水管等等。

那么怎么实现栈和队列呢？

# 双向链表实现

首先实现一个双线链表提供头部、尾部的增加、删除的功能，然后根据栈和队列的特点，去调用不同的功能就可以实现。

# 双向链表定义

节点定义：

public class Node<T> {
  public T value;
  public Node<T> last;
  public Node<T> next;

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

双线链表实现：

public class DoubleEndsQueue<T> {
  public Node<T> head;
  public Node<T> tail;
  
  public void addFromHead(T value) {
    Node<T> cur = new Node<>(value);
    if (head == null) {
      head = cur;
      tail = cur;
    } else {
      cur.next = head;
      head.last = cur;
      head = cur;
    }
  }

  public void addFromBottom(T value) {
    Node<T> cur = new Node<>(value);
    if (tail == null) {
      head = cur;
      tail = cur;
    } else {
      cur.last = tail;
      tail.next = cur;
      tail = cur;
    }
  }
  
  public T popFromHead() {
    if (head == null) {
      return null;
    }
    Node<T> cur = head;
    if (head = tail) {
      head = null;
      tail = null;
    } else {
      head = head.next;
      cur.next = null;
      head.last = null;
    }
    return cur.value;
  }
  
  public T popFromBottom() {
    if (head == null) {
      return null;
    }
    Node<T> cur = tail;
    if (tail = head) {
      tail = null;
      head = null;
    } else {
      tail = tail.last;
      tail.next = null;
      cur.last = null;
    }
    return cur.value;
  }
  
  public boolean isEmpty() {
    return head == null;
  }
 
}

# 实现栈

根据先进后出特点，调用方法实现入栈出栈。

public class MyStack<T> {
  private DoubleEndsQueue<T> queue;

  public MyStack() {
    queue = new DoubleEndsQueue<T>();
  }

  public void push(T value) {
    queue.addFromHead(value);
  }

  public T pop() {
    return queue.popFromHead();
  }

  public boolean isEmpty() {
    return queue.isEmpty();
  }
}

# 实现队列

根据先进先出特点，调用方法实现入队出队。

public class MyQueue<T> {
  private DoubleEndsQueue<T> queue;

  public MyQueue() {
    queue = new DoubleEndsQueue<T>();
  }

  public void push(T value) {
    queue.addFromHead(value);
  }

  public T poll() {
    return queue.popFromBottom();
  }

  public boolean isEmpty() {
    return queue.isEmpty();
  }
}

# 数组实现

# 实现栈

使用数组实现栈是比较简单的，只需要维护一个index即可。

public class MyStack {
  private int[] arr;
  private int index;
  private final int limit;

  public MyStack() {
    arr = new int[limit];
    index = 0;
  }

  public void push(int value) {
    if (index == limit) {
      throw new RuntimeException("栈满了，不能再加了");
    }
    arr[index] = value;
    index++;
  }

  public int pop() {
    if (index == 0) {
      throw new RuntimeException("栈空了，不能再拿了");
    }
    int ans = arr[index - 1];
    index--;
    return ans;
  }
  
	public boolean isEmpty() {
    return this.index == 0;
  }
}

# 实现队列

数组实现队列较难，因为循环数组中通常要维护一个指针“你追我赶”的关系，而实际上通过size变量可以将这种关系结构。

public class MyQueue {
  private int[] arr;
  // end
  private int pushi;
  // begin
  private int polli;
  private int size;
  private final int limit;

  public MyQueue(int limit) {
    arr = new int[limit];
    pushi = 0;
    polli = 0;
    size = 0;
    this.limit = limit;
  }
  
  public void push(int value) {
    if (size == limit) {
      throw new RuntimeException("队列满了，不能再加了");
    }
    size++;
    arr[pushi] = value;
    pushi = nextIndex(pushi);
  }

  public int poll() {
    if (size == 0) {
      throw new RuntimeException("队列空了，不能再拿了");
    }
    size--;
    int ans = arr[polli];
    polli = nextIndex(polli);
    return ans;
  }
  
	public boolean isEmpty() {
    return this.size == 0;
  }
  
  private int nextIndex(int i) {
    return i < limit - 1 ? i + 1 : 0;
  }
  
}

# 手写的原因

为什么语言的都有这些结构和api，为什么还要手写联系？

  • 算法问题无关语言
  • 语言提供的api是有限的，当有需要新的功能是api不提供的，就需要改写
  • 任何软件工具的底层都是最基本的算法和数据结构，这是绕不过去的

# 常见面试题

# 数组实现队列和栈

题目：怎么用数组实现不超过固定大小的队列和栈

核心：栈，正常使用，队列，环形数组。实现细节见上面。

# 最小栈

题目：实现一个特殊的栈，在基本功能（原有JDK提供的Stack）的基础上，再实现返回栈中最小元素的功能

  • pop、push、getMin操作的时间复杂度都是O(1)。

  • 设计的栈类型可以使用现成的栈结构。

这个题目的实现核心是 使用两个栈结构，一个栈存储数据，称为数据栈“Data Stack”，另一个栈负责存储最小值，称为最小栈“Min Stack”。而对怎么往“Min Stack”存储数据有两种实现。

  1. 数据栈入栈，当前数与最小栈的栈顶，最小栈谁小加谁；数据栈出栈，最小栈同步出栈。即“Data Stack”与“Min Stack”数量同步，空间换效率。

    public class MyStack1 {
  private Stack<Integer> stackData;
  private Stack<Integer> stackMin;

  public MyStack1() {
    this.stackData = new Stack<Integer>();
    this.stackMin = new Stack<Integer>();
  }

  public void push(int newNum) {
    if (this.stackMin.isEmpty()) {
      this.stackMin.push(newNum);
    } else if (newNum < this.getmin()) {
      this.stackMin.push(newNum);
    } else {
      int newMin = this.stackMin.peek();
      this.stackMin.push(newMin);
    }
    this.stackData.push(newNum);
  }

  public int pop() {
    if (this.stackData.isEmpty()) {
      throw new RuntimeException("Your stack is empty.");
    }
    this.stackMin.pop();
    return this.stackData.pop();
  }

  public int getmin() {
    if (this.stackMin.isEmpty()) {
      throw new RuntimeException("Your stack is empty.");
    }
    return this.stackMin.peek();
  }
}

  2. 数据栈入栈，当前数小于或等于则压入最小栈，否则不压入最小栈；数据栈出栈，出栈数等于最小栈的栈顶，最小栈也出栈。即节省了空间，但是浪费了一些时间。

    public class MyStack2 {
  private Stack<Integer> stackData;
  private Stack<Integer> stackMin;

  public MyStack2() {
    this.stackData = new Stack<Integer>();
    this.stackMin = new Stack<Integer>();
  }

  public void push(int newNum) {
    if (this.stackMin.isEmpty()) {
      this.stackMin.push(newNum);
    } else if (newNum <= this.getmin()) {
      this.stackMin.push(newNum);
    }
    this.stackData.push(newNum);
  }

  public int pop() {
    if (this.stackData.isEmpty()) {
      throw new RuntimeException("Your stack is empty.");
    }
    int value = this.stackData.pop();
    if (value == this.getmin()) {
      this.stackMin.pop();
    }
    return value;
  }

  public int getmin() {
    if (this.stackMin.isEmpty()) {
      throw new RuntimeException("Your stack is empty.");
    }
    return this.stackMin.peek();
  }
}

# 栈结构实现队列结构*

题目：如何使用栈结构实现队列结构

核心：使用两个栈，入队操作：“Push Stack”入栈，入栈前需要将全部数据导到“Pop Stack”，即保证“Push Stack”为空，可以称为“导数据”；出队操作：进行一次导数据操作， 然后将“Pop Stack”出栈即可。

public class TwoStacksQueue {
  public Stack<Integer> stackPush;
  public Stack<Integer> stackPop;

  public TwoStacksQueue() {
    stackPush = new Stack<Integer>();
    stackPop = new Stack<Integer>();
  }

  public TwoStacksQueue() {
    stackPush = new Stack<Integer>();
    stackPop = new Stack<Integer>();
  }

  // push栈向pop栈倒入数据
  private void pushToPop() {
    if (stackPop.empty()) {
      while (!stackPush.empty()) {
        stackPop.push(stackPush.pop());
      }
    }
  }

  public void add(int pushInt) {
    stackPush.push(pushInt);
    pushToPop();
  }

  public int poll() {
    if (stackPop.empty() && stackPush.empty()) {
      throw new RuntimeException("Queue is empty!");
    }
    pushToPop();
    return stackPop.pop();
  }

  public int peek() {
    if (stackPop.empty() && stackPush.empty()) {
      throw new RuntimeException("Queue is empty!");
    }
    pushToPop();
    return stackPop.peek();
  }
}

# 队列结构实现栈结构*

题目：如何使用队列结构实现栈结构

核心：使用两个队列，入栈：“Data Queue”负责数据入队；出栈：使用“Help Queue”辅助，将“Data Queue”的数出队到“Help Queue"直至剩余一个数，最后将这个数从“Data Queue”出队，并交换两个队列的引用。

public class TwoQueueStack<T> {
  public Queue<T> queue;
  public Queue<T> help;

  public TwoQueueStack() {
    queue = new LinkedList<>();
    help = new LinkedList<>();
  }

  public void push(T value) {
    queue.offer(value);
  }

  public T poll() {
    while (queue.size() > 1) {
      help.offer(queue.poll());
    }
    T ans = queue.poll();
    Queue<T> tmp = queue;
    queue = help;
    help = tmp;
    return ans;
  }

  public T peek() {
    while (queue.size() > 1) {
      help.offer(queue.poll());
    }
    T ans = queue.poll();
    help.offer(ans);
    Queue<T> tmp = queue;
    queue = help;
    help = tmp;
    return ans;
  }

  public boolean isEmpty() {
    return queue.isEmpty();
  }

}

如果面试过程说，宽度优先遍历（一般通过队列实现）能用栈实现，深度优先遍历（一般通过栈实现）能用队列实现，就是上面的应用。

#数据结构与算法
上次更新: 5/21/2023, 11:34:33 PM
递归

递归→

最近更新
01
2025
01-15
02
Elasticsearch面试题
07-17
03
Elasticsearch进阶
07-16
更多文章>
Theme by Vdoing