【夜深人静学数据结构与算法 | 第九篇】栈与队列-Toy模板网

这篇具有很好参考价值的文章主要介绍了【夜深人静学数据结构与算法 | 第九篇】栈与队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言：

栈：

栈的实际应用：

队列：

队列的实际应用：

总结：

前言：

栈与队列是我们学习的两个经典的数据结构，这两个数据结构应用广泛，在计算机内有很多底层应用，而很多算法也是依靠栈和队列来实现的，因此我们要想学好数据结构与算法，就要学好栈与队列这两个最经典的数据机构。

栈：

栈是一种后进先出（Last-In-First-Out，LIFO）的数据结构，它可以实现快速的数据插入和删除操作。

栈可以具备以下几个特点：

1. 栈中添加和删除元素都在同一个位置进行，即栈顶。
2. 栈中元素的添加和删除顺序是相反的，即后进先出。
3. 栈的长度是动态变化的，但它有一个默认或者是最大长度限制。

在栈中，新元素被插入到栈顶位置，称为“压入”（push）操作；而栈顶元素被删除称为“弹出”（pop）操作。栈的本质是一种线性结构，可以使用数组或链表来实现，但由于它的特殊性，通常使用数组来实现更加便捷。

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 10

int top = -1; // 栈顶指针
int arr[MAX_SIZE]; // 存储栈数据的数组

// 添加元素
bool push(int item) {
    if (top >= MAX_SIZE-1) {
        printf("Stack Overflow\n");
        return false;
    } else {
        arr[++top] = item;
        printf("Pushed %d into the stack\n", item);
        return true;
    }
}

// 弹出元素
int pop() {
    if (top < 0) {
        printf("Stack Underflow\n");
        return -1;
    } else {
        int item = arr[top--];
        printf("Popped %d from the stack\n", item);
        return item;
    }
}

// 返回栈顶元素
int peek() {
    if (top < 0) {
        printf("Stack is empty\n");
        return -1;
    } else {
        return arr[top];
    }
}

// 判断栈是否为空
bool isEmpty() {
    return top == -1;
}

// 返回栈中元素个数
int size() {
    return top + 1;
}

栈的实际应用：

栈是计算机科学中基础的数据结构之一，它在程序设计和开发中有以下几个常见的作用：

1. 算法实现：栈可以被用来实现很多算法，例如：逆波兰表达式求值、中缀表达式转后缀表达式、深度优先遍历等。

2. 函数调用：在函数调用过程中，调用函数时的所有本地变量都会存储在一个函数调用栈中。当函数返回时，局部变量从栈中删除。函数调用栈跟踪函数调用顺序和状态。

3. 内存分配：内存分配函数（如 malloc 和 calloc 等）使用堆栈结构来存储和管理分配的内存块。

4. 缓存和历史记录：在Web开发中，栈可以用来实现浏览器缓存和历史记录，以保存用户的访问记录。

5. 数据结构实现：许多数据结构，如树、图、队列、堆等都可以使用栈来实现。

6. 编译器实现：编译器在编译和解析源码时，需要用到栈来处理语法分析和执行过程。

总言而之，栈是计算机科学中非常重要的数据结构，它帮助程序员解决了各种问题和挑战，不仅可以提高程序的执行效率，而且可以使代码更加简洁，易于理解和维护。

队列：

队列（Queue）是一种先进先出（FIFO）的线性数据结构。它只允许在队列的一端进行插入操作，而在另一端进行删除操作。原则上，第一个被插入的元素必须先被删除，这个规则被称为“先进先出”，简称为 FIFO。

和栈不同的是，队列的两端分别称为队尾和队头，插入操作插入在队尾，删除操作则是删除队头的元素。队列的一个重要特性是它可以帮助我们完成在大量数据集合或多任务下的管理和调度。

队列可以具备以下几个特点：

先进先出（FIFO）：队列的基本操作是在队尾入队和在队头出队。元素是按照它们入队的先后顺序排队等待出队，最先被入队的元素要先被出队。
只允许在队尾进行插入操作，只允许在队头进行删除操作：插入操作将元素加到队列的尾部，删除操作从队列的头部删除元素。因为队列只允许一侧进一侧出，所以保证了FIFO的顺序。
队列的长度可以动态变化：队列可以根据需要动态增加或减少，只要内存空间足够。这是与数组的静态大小不同的一个特点。
队列可以为空：当队列中没有元素时，我们说它是空队列。这是因为队列的长度是动态变化的，因此是有可能为空的。
队列可以具有大小限制：队列可以被限制成固定大小，当队列容量达到最大值后，继续插入元素就会失败，这是顺序存储队列的一个常见特点。
队列可以支持并发操作：队列可以被多个线程同时访问，因为队列的各个操作都是原子性的和无状态的。因此，它可以作为一个数据缓冲区在生产者和消费者之间传递数据。

常见的队列有数组队列和链表队列。在数组队列中，元素存储在一个固定大小的数组中。在链表队列中，元素是通过链表链接在一起的。

队列常见的操作有：入队（Enqueue）、出队（Dequeue）、获取队头元素（Front）、获取队尾元素（Rear）、判空（IsEmpty）、判满（IsFull）等。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int front;
    int rear;
} Queue;

void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

bool isFull(Queue *q) {
    return (q->rear == MAX_SIZE - 1);
}

bool isEmpty(Queue *q) {
    return (q->front == -1 && q->rear == -1);
}

void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full.\n");
    }
    else if (isEmpty(q)) {
        q->front = 0;
        q->rear = 0;
        q->items[q->rear] = value;
    }
    else {
        q->rear++;
        q->items[q->rear] = value;
    }
}

int dequeue(Queue *q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        item = -1;
    }
    else if (q->front == q->rear) {
        item = q->items[q->front];
        q->front = -1;
        q->rear = -1;
    }
    else {
        item = q->items[q->front];
        q->front++;
    }
    return item;
}

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    enqueue(&q, 40);

    printf("Dequeued item: %d\n", dequeue(&q));
    printf("Dequeued item: %d\n", dequeue(&q));

    return 0;
}