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

核心接口实现

// 栈初始化
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;
}

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