数据结构与算法——栈和队列

栈和队列

//1.栈
#include <stdio.h>
#include <stdlib.h>

// 定义栈的结构体
typedef struct Stack {
    int capacity; // 栈的容量
    int top;      // 栈顶指针，表示当前栈顶元素的位置
    int* array;   // 存储栈元素的数组
} Stack;

// 创建一个新的栈
Stack* createStack(int size) {
    Stack* stack = (Stack*)malloc(sizeof(Stack)); // 分配内存创建栈对象
    stack->capacity = size;                      // 设置栈的容量
    stack->top = -1;                            // 初始化栈顶指针为-1，表示栈为空
    stack->array = (int*)malloc(stack->capacity * sizeof(int)); // 分配内存用于存储栈元素
    return stack;                                 // 返回新建的栈对象
}

// 入栈操作
void push(Stack* stack, int item) {
    if (stack->top >= stack->capacity - 1) {     // 判断栈是否已满
        printf("栈已满，无法入栈!\n");
        return;
    }
    stack->array[++stack->top] = item;         // 栈顶指针加1，然后在新位置放入元素
    // 注解：这一行代码模拟了生活中把物品“压”入栈的过程，新的物品总是在栈顶。
}

// 出栈操作
int pop(Stack* stack) {
    if (stack->top == -1) {                    // 判断栈是否为空
        printf("栈为空，无法出栈!\n");
        return INT_MIN;                         // 返回一个特殊值表示出栈失败
    }
    int item = stack->array[stack->top];       // 获取栈顶元素的值
    stack->top--;                              // 减小栈顶指针，相当于移除栈顶元素
    return item;                               // 返回栈顶元素
    // 注解：这一行代码模拟了生活中从栈顶取出物品的过程，总是最先放入的最后取出。
}

// 生活案例：
// 栈可以模拟停车场出口收费系统，车辆进入停车场（push）时按顺序停放，离开（pop）时按照先进先出的原则收费。

//2.队列

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

typedef struct Queue {
    int front;  // 队首指针，表示队首元素的位置
    int rear;   // 队尾指针，表示队尾元素的位置
    int capacity;
    int* array;
} Queue;

Queue* createQueue(int size) {
    // 同样地，此处省略了创建队列的内存分配和初始化过程，逻辑与创建栈类似
    // ...
}

int isFull(Queue* queue) {
    return (queue->rear == queue->capacity - 1);  // 判断队列是否已满
}

int isEmpty(Queue* queue) {
    return (queue->front == -1);                 // 判断队列是否为空
}

void enqueue(Queue* queue, int item) {
    if (isFull(queue)) {
        printf("队列已满，无法入队!\n");
        return;
    }
    // 如果队列为空，则队首和队尾都是0，否则队尾指针加1并模容量，确保始终在数组范围内
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->array[queue->rear] = item;           // 在队尾位置添加新元素
    // 注解：这一行代码模拟了生活中顾客在队尾排队的过程，新来的顾客总是站在队列的最后面。
}

int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空，无法出队!\n");
        return INT_MIN;
    }
    int item = queue->array[queue->front];       // 获取队首元素的值
    // 如果队列只有一个元素，那么出队后队首和队尾都置为-1；否则队首指针加1并模容量
    queue->front = (queue->front + 1) % queue->capacity;
    return item;
    // 注解：这一行代码模拟了生活中服务窗口的服务过程，总是最先排队的顾客首先被服务（出队）。
}

// 生活案例：
// 队列可以模拟银行排队叫号系统，顾客按照先来后到的原则排队（enqueue），窗口根据队列顺序呼叫顾客办理业务（dequeue）。