数据结构：堆栈和队列

精彩文章

堆栈和队列经常被用作程序运行过程中程序员的工具，并且通常在任务完成后被删除。

堆

堆栈是一种遵循“后进先出”或LIFO模型的抽象数据结构。一些现实世界中的例子包括“点击返回”到上一个网页，以及文本编辑器的撤消功能。

堆栈有 3 种基本操作：
1. 压栈：在堆栈中插入一个数据项。2
. 弹出：从堆栈顶部移除一个数据项。3
. 窥视：从堆栈顶部读取一个数据项的值，但不将其移除。

在编程中，可以使用数组或链表来实现堆栈。（下面是使用 Java 实现堆栈的示例）

class StackX {
    private int maxSize;
    private long[] stackArray;
    private int top;

    public StackX(int s) {                // constructor
        maxSize = s;                      // set the array size
        stackArray = new long[maxSize];   // create an array
        top = -1;                         // no items yet
    }

    public void push(long j) {        // put items on top of the stack
        stackArray[++top] = j;        // increment top when item inserted
    }
    public long pop() {               // take item from the top of the stack
        return stackArray[top--];     // access item, then decrement top
    }
    public long peek() {              // peek at the top of the stack
        return stackArray[top];
    }
    public boolean isEmpty() {        // true if the stack is empty
        return (top == -1);
    }
    public boolean isFull() {         // true if the stack is full
        return (top == maxSize -1);
    }

堆栈应用程序

反转数据；例如反转字符串
解析：将数据分解成独立的部分以进行进一步的验证；例如检查分隔符是否匹配 [,{,(,),},]。
工作原理：
- 每次从字符串中读取一个字符
- 如果遇到开头的分隔符[,{,(, 将其放在堆栈上
- 如果遇到结束分隔符，则从堆栈顶部弹出该项目
- 如果它们不匹配（开始和结束分隔符），则会发生错误。
例如：a{b(c[d]e)f}h

细绳	堆
一个	空的
{	{
b	{
(	{（
c	{（
[	{([
d	{([
]	{（
e	{（
)	{
f	{
{	空的
h	空的

推迟：当数据的使用必须推迟一段时间时。例如，解析算术表达式：3+(5-9)*4
我们将要使用的符号：
- 前缀 -> + ab
- 中缀 -> a + b
- 后缀 ab +
+、-、*、/，这些是运算符。
而我们把数字（1、2、3、...）称为操作数。

优先顺序（优先级、等级）关系：
- +、- 具有相同的优先级
- *、/ 具有相同的优先级，并且高于 +、-

我认为使用视频来解释它的工作原理应该更容易，所以我们开始吧......

我们必须这样做的原因是，计算机只能向前或向后浏览表达式。

让我们看看如何将中缀表达式转换为后缀表达式。

这是如何评估后缀表达式的视频。

更详细的解释请点击这里。

回溯：用于许多搜索应用，八皇后问题等。查找路径的示例：

n 皇后问题示例：

队列

队列是一种遵循“先进先出”或FIFO模型的抽象数据结构。一些现实世界的例子包括打印文件（队列中有一个文件）、进程调度程序、等待队列。

队列的基本操作： 1. 入队/添加/放入：在队列尾部插入数据项。2 .
出队/删除/获取：从队列前端移除数据项。3. 窥视：从队列前端读取数据项的值，但不将其移除。

现在，我们下面就来看一下java中一个队列的实现吧！

class Queue {
    private int maxSize;
    private long[] queArray;
    private int front;
    private int back;
    private int nItems;

    public Queue(int s) {                    // Constructor
        maxSize = s;
        quaArray = new long[maxSize];
        front = 0;
        back = -1;
        nItems = 0;
    }

    public void insert(long j) {            // Put an item at the back of the queue
        if(back == maxSize -1) back = -1;   // Deal with wraparound
        queArray[++back] = j;               // Increment back and insert the item
        nItems++;                           // One more item
    }
    public long remove() {                  // Take item from the front of the queue
        long temp = queArray[front++];      // Get the item and increment front
        if(front == maxSize) front = 0;     // Deal with wraparound
        nItems--;                           // One less item
        return temp;
    }
    public long peekFront() {
        return queArray[front];
    }

操作系统中的队列

当我们只有一个处理器，但有多个进程需要执行时，为了使这些进程看起来同时运行，我们必须将 CPU 时间切分成多个槽位，并创建一个包含待执行作业的队列。

优先级队列

队列中的项目将按键值排序（即按优先级排序）。优先级队列有两种类型。

升序优先级队列 - 具有最小键的项目具有最高优先级
降序优先级队列 - 具有最大关键项的项目具有最高优先级

在优先级队列中插入项目：O（n）

我们不是将项目插入到队列的后面或末尾，而是根据项目与其他项目的比较值来插入项目。

# 移除/删除项目：O（n）

就像普通队列一样，我们删除队列中最前面的一个。

这篇文章就到这里啦 :) 下次再见~

文章来源：https://dev.to/rinsama77/data-struct-stack-and-queue-4ecd

数据结构：堆栈和队列 awesome-article