16 - 堆栈 - 优先级队列

**堆栈与优先级队列**

在计算机科学中，堆栈（Stack）和优先级队列（Priority Queue）是两种常见的数据结构，它们都用于管理元素的顺序。虽然它们看起来很相似，但它们有着不同的使用场景和特点。

**堆栈（Stack）**

堆栈是一种线性数据结构，遵循后进先出（LIFO）的原则。这意味着最后添加的元素将首先被移除。堆栈通常用于实现递归算法、函数调用栈以及表达式求值等场景。

**优先级队列（Priority Queue）**

优先级队列是一种非线性数据结构，它根据元素的优先级来组织元素。每个元素都有一个关联的优先级，优先级高的元素将首先被移除。优先级队列通常用于实现任务调度、资源分配以及最短路径寻找等场景。

**堆栈的实现**

堆栈可以使用数组或链表来实现。下面是一个简单的堆栈实现示例（使用 Java语言）：

javapublic class Stack {
 private int[] elements;
 private int size;

 public Stack(int capacity) {
 elements = new int[capacity];
 size =0;
 }

 public void push(int element) {
 if (size == elements.length) {
 // 堆栈已满，需要扩容 int[] newElements = new int[elements.length *2];
 System.arraycopy(elements,0, newElements,0, elements.length);
 elements = newElements;
 }
 elements[size++] = element;
 }

 public int pop() {
 if (size ==0) {
 // 堆栈为空 throw new RuntimeException("Stack is empty");
 }
 return elements[--size];
 }

 public int peek() {
 if (size ==0) {
 // 堆栈为空 throw new RuntimeException("Stack is empty");
 }
 return elements[size -1];
 }
}

**优先级队列的实现**

优先级队列可以使用堆数据结构来实现。下面是一个简单的优先级队列实现示例（使用 Java语言）：

javaimport java.util.Comparator;

public class PriorityQueue {
 private int[] elements;
 private Comparator comparator;
 private int size;

 public PriorityQueue(Comparator comparator) {
 this.comparator = comparator;
 elements = new int[10];
 size =0;
 }

 public void add(int element) {
 if (size == elements.length) {
 // 队列已满，需要扩容 int[] newElements = new int[elements.length *2];
 System.arraycopy(elements,0, newElements,0, elements.length);
 elements = newElements;
 }
 insert(element);
 }

 private void insert(int element) {
 int index = size -1;
 while (index >=0 && comparator.compare(element, elements[index]) >0) {
 elements[index +1] = elements[index];
 index--;
 }
 elements[index +1] = element;
 size++;
 }

 public int remove() {
 if (size ==0) {
 // 队列为空 throw new RuntimeException("Queue is empty");
 }
 return elements[0];
 }

 public int peek() {
 if (size ==0) {
 // 队列为空 throw new RuntimeException("Queue is empty");
 }
 return elements[0];
 }
}

**使用堆栈和优先级队列的场景**

堆栈通常用于实现递归算法、函数调用栈以及表达式求值等场景。例如，在计算机图形学中，堆栈可以用于管理渲染管线中的元素。

优先级队列通常用于实现任务调度、资源分配以及最短路径寻找等场景。例如，在操作系统中，优先级队列可以用于管理进程的执行顺序。

**总结**

堆栈和优先级队列是两种常见的数据结构，它们都用于管理元素的顺序。虽然它们看起来很相似，但它们有着不同的使用场景和特点。堆栈通常用于实现递归算法、函数调用栈以及表达式求值等场景，而优先级队列通常用于实现任务调度、资源分配以及最短路径寻找等场景。

**参考**

* 《数据结构与算法》(第3 版)
* 《计算机图形学》(第2 版)
* 《操作系统》(第4 版)