数据结构：栈和队列的定义与实现

1. 栈

1.1 栈的定义及结构

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出（LIFO, Last In First Out）的原则。

• 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
• 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

总结：栈是一个后进先出的容器。一个入栈序列可以对应多个出栈序列。

1.2 栈的实现

分析：顺序表和链表均可实现栈，但顺序表在一端操作更为方便，因此选择顺序表来实现栈。

大体思想如下：

顺序表已实现过动态增容，用其实现栈需注意细节。以下是头文件声明：

typedef int StackDataType;

typedef struct Stack {
    StackDataType* _Array;
    int _top;
    int _capacity;
} Stack;

// 栈初始化
void StackInit(Stack* s);
// 销毁栈
void StackDestory(Stack* s);
// 入栈
void StackPush(Stack* s, StackDataType x);
// 出栈
void StackPop(Stack* s);
// 获取栈顶元素
StackDataType StackTop(Stack* s);
// 获取栈有效元素个数
int StackSize(Stack* s);
// 判断栈是否为空，空返回 1，非空返回 0
int StackEmpty(Stack* s);

核心接口实现

// 栈初始化
void StackInit(Stack* s) {
    assert(s);
    // 修正：分配空间应为数据类型大小而非结构体大小
    s->_Array = (StackDataType*)malloc(sizeof(StackDataType) * ARRAYINITSIZE);
    s->_top = 0;
    s->_capacity = ARRAYINITSIZE;
}

// 销毁栈
void StackDestory(Stack* s) {
    assert(s);
    free(s->_Array);
    s->_Array = NULL;
    s->_top = s->_capacity = 0;
}

// 入栈
void StackPush(Stack* s, StackDataType x) {
    assert(s);
    if (s->_top == s->_capacity) {
        s->_capacity *= 2;
        // 修正：类型匹配
        StackDataType* temp = (StackDataType*)realloc(s->_Array, sizeof(StackDataType) * s->_capacity);
        if (temp == NULL) {
            printf("内存不足\n");
            exit(-1);
        } else {
            s->_Array = temp;
        }
    }
    s->_Array[s->_top] = x;
    s->_top++;
}

// 出栈
void StackPop(Stack* s) {
    assert(s);
    assert(s->_top != 0);
    s->_top--;
}

其它接口只需返回相应变量即可，建立接口是为了保持接口一致性。

2. 队列

2.1 队列的定义及结构

队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，具有先进先出（FIFO, First In First Out）特性。

• 入队列：进行插入操作的一端称为队尾。
• 出队列：进行删除操作的一端称为队头。

总结：队列如同日常排队，谁先进谁先出，一种入队序列只能对应一种出队序列。

2.2 队列的实现

分析：队列需要一头进、另一头出。顺序表头删效率低，单链表适合此场景。采用单链表形式实现队列。

typedef int QueueDataType;

typedef struct QueueListNode {
    QueueDataType _data;
    struct QueueListNode* _next;
} QueueListNode;

typedef struct Queue {
    QueueListNode* _front;
    QueueListNode* _rear;
} Queue;

// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回 0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

通过结构体存放头尾指针，使接口保持一致性，避免部分接口需传二级指针。

核心接口实现

// 队尾入队列
void QueuePush(Queue* q, QueueDataType data) {
    assert(q);
    if (q->_front == NULL) {
        // 修正：类型匹配
        QueueListNode* temp = (QueueListNode*)malloc(sizeof(QueueListNode));
        if (temp == NULL) {
            printf("内存不足\n");
            exit(-1);
        } else {
            q->_front = q->_rear = temp;
        }
    } else {
        QueueListNode* temp = (QueueListNode*)malloc(sizeof(QueueListNode));
        if (temp == NULL) {
            printf("内存不足\n");
            exit(-1);
        } else {
            q->_rear->_next = temp;
            q->_rear = temp;
        }
    }
    q->_rear->_data = data;
    q->_rear->_next = NULL;
}

// 队头出队列
void QueuePop(Queue* q) {
    assert(q);
    assert(q->_front != NULL);
    QueueListNode* frontNext = q->_front->_next;
    free(q->_front);
    q->_front = frontNext;
}

总结：栈常用于迷宫回溯等后进先出场景；队列常见于银行排队等先进先出场景。掌握这两种基础数据结构对理解算法设计至关重要。