C 语言实现队列数据结构详解

2.3 队列入、出操作

这里涉及尾插和头删逻辑。入队时需分配新节点并更新尾指针；出队时需释放头节点并更新头指针。注意处理只有一个节点时的边界情况。

// 队列入队
void QueuePush(Queue* pq, QDatatype x) {
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newnode == NULL) {
        perror("malloc fail");
        return;
    }
    newnode->Data = x;
    newnode->next = NULL;

    if (pq->head == NULL) {
        assert(pq->tail == NULL);
        pq->head = pq->tail = newnode;
    } else {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
    pq->size++;
}

// 队列出队
void QueuePop(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));
    QueueNode* cur = pq->head;
    
    if (cur->next == NULL) {
        // 仅剩一个节点，出队后队列为空
        free(cur);
        pq->head = NULL;
        pq->tail = NULL;
    } else {
        pq->head = pq->head->next;
        free(cur);
    }
    pq->size--;
}

2.4 辅助功能：判空与大小

// 获取队列大小
int QueueSize(Queue* pq) {
    assert(pq);
    return pq->size;
}

// 判断队列是否为空
bool QueueEmpty(Queue* pq) {
    assert(pq);
    return pq->size == 0;
}

// 返回队头数据
QDatatype QueueFront(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->Data;
}

// 返回队尾数据
QDatatype QueueBack(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->Data;
}

// 销毁队列
void QueueDestroy(Queue* pq) {
    assert(pq);
    QueueNode* cur = pq->head;
    while (cur) {
        QueueNode* del = cur;
        cur = cur->next;
        free(del);
    }
    pq->head = NULL;
    pq->tail = NULL;
    pq->size = 0;
}

2.5 测试示例

int main() {
    Queue Q = { 0 };
    QueueInit(&Q);
    
    for (int i = 1; i <= 6; i++) {
        QueuePush(&Q, i);
    }

    while (!QueueEmpty(&Q)) {
        printf("%d ", QueueFront(&Q));
        QueuePop(&Q);
    }
    printf("\n");
    
    QueueDestroy(&Q);
    return 0;
}

运行结果应输出：1 2 3 4 5 6

三、实战练习

结合栈和队列的特性，我们来解决几个经典算法题。

3.1 有效的括号

给定一个只包括 '(', ')', '{', '}', '[', ']' 的字符串，判断字符串是否有效。

题目分析

此题适合用栈结构解决。遇到左括号入栈，遇到右括号则与栈顶元素比对。若匹配则弹出，否则无效。遍历结束后栈为空则说明有效。注意内存释放，避免泄漏。

解题代码

由于使用 C 语言，需手动实现栈结构。

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

typedef int StackDataType;

typedef struct stack {
    StackDataType* StackData;
    int top;
    int capacity;
} ST;

void InitStack(ST* ps) {
    assert(ps);
    ps->StackData = (StackDataType*)malloc(sizeof(StackDataType) * 4);
    if (ps->StackData == NULL) {
        perror("InitStack::malloc");
        return;
    }
    ps->capacity = 4;
    ps->top = 0;
}

void DestoryStack(ST* ps) {
    assert(ps);
    free(ps->StackData);
    ps->StackData = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

void STPush(ST* ps, StackDataType x) {
    assert(ps);
    if (ps->top == ps->capacity) {
        StackDataType* tmp = (StackDataType*)realloc(ps->StackData, sizeof(StackDataType) * ps->capacity * 2);
        if (tmp == NULL) {
            perror("STPush::realloc");
            return;
        }
        ps->StackData = tmp;
        ps->capacity *= 2;
    }
    ps->StackData[ps->top] = x;
    ps->top += 1;
}

void STPop(ST* ps) {
    assert(ps);
    assert(!STEmpty(ps));
    ps->top--;
}

bool STEmpty(ST* ps) {
    assert(ps);
    return ps->top == 0;
}

StackDataType STTop(ST* ps) {
    assert(ps);
    assert(!STEmpty(ps));
    return ps->StackData[ps->top - 1];
}

bool isValid(char* s) {
    ST st = { 0 };
    InitStack(&st);
    char* p = s;
    while (*p) {
        if (*p == '(' || *p == '[' || *p == '{') {
            STPush(&st, *p);
        } else {
            if (STEmpty(&st)) {
                DestoryStack(&st);
                return false;
            }
            char top = STTop(&st);
            STPop(&st);
            if ((*p == ')' && top != '(') || 
                (*p == ']' && top != '[') || 
                (*p == '}' && top != '{')) {
                DestoryStack(&st);
                return false;
            }
        }
        p++;
    }
    bool ret = STEmpty(&st);
    DestoryStack(&st);
    return ret;
}

3.2 用队列实现栈

仅使用两个队列实现一个后入先出（LIFO）的栈，支持 push, top, pop, empty 操作。

题目分析

利用两个队列模拟栈的核心在于：数据始终存在一个非空队列中。当需要 pop 或 top 时，将非空队列的元素逐个转移到空队列，直到剩下最后一个元素，该元素即为栈顶。此时交换两个队列的角色即可。

解题代码

复用前文实现的队列结构。

typedef int QDatatype;

typedef struct QueueNode {
    QDatatype Data;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    struct QueueNode* head;
    struct QueueNode* tail;
    int size;
} Queue;

void QueueInit(Queue* pq) {
    assert(pq);
    pq->size = 0;
    pq->head = NULL;
    pq->tail = NULL;
}

void QueueDestroy(Queue* pq) {
    assert(pq);
    QueueNode* cur = pq->head;
    while (cur) {
        QueueNode* del = cur;
        cur = cur->next;
        free(del);
    }
    pq->head = NULL;
    pq->tail = NULL;
    pq->size = 0;
}

void QueuePush(Queue* pq, QDatatype x) {
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newnode == NULL) {
        perror("malloc fail");
        return;
    }
    newnode->Data = x;
    newnode->next = NULL;
    if (pq->head == NULL) {
        assert(pq->tail == NULL);
        pq->head = pq->tail = newnode;
    } else {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
    pq->size++;
}

void QueuePop(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));
    if (pq->head->next == NULL) {
        free(pq->head);
        pq->head = NULL;
        pq->tail = NULL;
    } else {
        QueueNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
    pq->size--;
}

int QueueSize(Queue* pq) {
    assert(pq);
    return pq->size;
}

bool QueueEmpty(Queue* pq) {
    assert(pq);
    return pq->size == 0;
}

QDatatype QueueFront(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->Data;
}

QDatatype QueueBack(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->Data;
}

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    if (pst == NULL) {
        perror("myStackCreate::malloc");
        return NULL;
    }
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

void myStackPush(MyStack* obj, int x) {
    if (!QueueEmpty(&obj->q1)) {
        QueuePush(&obj->q1, x);
    } else {
        QueuePush(&obj->q2, x);
    }
}

int myStackPop(MyStack* obj) {
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;
    
    if (!QueueEmpty(&obj->q1)) {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }
    
    while (QueueSize(nonemptyQ) > 1) {
        QueuePush(emptyQ, QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }
    int top = QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
    return top;
}

int myStackTop(MyStack* obj) {
    if (!QueueEmpty(&obj->q1)) {
        return QueueBack(&obj->q1);
    } else {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

至此，队列的基础实现及典型应用已讲解完毕。在实际开发中，注意内存管理的完整性，避免悬空指针和泄漏问题。