栈和队列数据结构初阶：模拟实现与 STL 应用

理论部分

栈的模拟实现

typedef int STDataType;
typedef struct Stack {
    STDataType* a; // 数组
    int top;       // 当前容量/下标
    int capacity;  // 总容量
} ST;

void STInit(ST* ps) {
    assert(ps);
    ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    if (ps->a == NULL) {
        perror("malloc fail");
        return;
    }
    ps->capacity = 4;
    ps->top = 0;
}

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

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

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

int STSize(ST* ps) {
    assert(ps);
    return ps->top;
}

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

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

注意：栈顶元素下标为 top-1。初始化时检查内存分配是否成功，扩容后需更新指针。

STL 中的栈容器

#include <stack>
// stack<T> st; // T 为任意类型
// size(), empty(), push(), pop(), top()
// 特性：先进后出 (LIFO)

队列的模拟实现

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

typedef char QDatatype;
typedef struct QueueNode {
    struct QueueNode* next;
    QDatatype data;
} QNode;

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

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

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

void QueuePush(Queue* pq, QDatatype x) {
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    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(pq->head != NULL);
    if (pq->head->next == NULL) {
        free(pq->head);
        pq->head = pq->tail = NULL;
    } else {
        QNode* 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(Queu* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}

注意：结构体嵌套定义无需单独手动开辟内存；assert 用于断言条件成立。

STL 中的队列容器

#include <queue>
// queue<T> q; // T 为任意类型
// size(), empty(), push(), pop(), front(), back()
// 特性：先进先出 (FIFO)，pop 删除队头

作业部分

力扣 有效的括号

题目链接： https://leetcode.cn/problems/valid-parentheses/

思路： 使用栈匹配左右括号，右括号数量不等于左括号时需特殊处理。

typedef struct Stack {
    char* a;
    int top;
    int capacity;
} ST;

void STInit(ST* ps) {
    ps->a = (char*)malloc(sizeof(char) * 4);
    ps->capacity = 4;
    ps->top = 0;
}

void STPush(ST* ps, char x) {
    assert(ps);
    if (ps->top == ps->capacity) {
        char* tmp = (char*)malloc(sizeof(char) * ps->capacity * 2);
        memcpy(tmp, ps->a, sizeof(char) * ps->capacity);
        free(ps->a);
        ps->a = tmp;
        ps->capacity *= 2;
    }
    ps->a[ps->top] = x;
    ps->top++;
}

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

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

char STTop(ST* ps) {
    return ps->a[ps->top - 1];
}

bool isValid(char* s) {
    ST st;
    STInit(&st);
    for (int i = 0; s[i]; i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            STPush(&st, s[i]);
        } else {
            if (STEmpty(&st)) {
                STDestroy(&st);
                return false;
            }
            char top = STTop(&st);
            if ((s[i] == ')' && top != '(') ||
                (s[i] == ']' && top != '[') ||
                (s[i] == '}' && top != '{')) {
                STDestroy(&st);
                return false;
            }
            STPop(&st);
        }
    }
    bool result = STEmpty(&st);
    STDestroy(&st);
    return result;
}

力扣 用栈实现队列

题目链接： https://leetcode.cn/problems/implement-queue-using-stacks/

思路： 双栈法，一个栈入栈，一个栈出栈。出栈空时将入栈数据倒入。

class MyQueue {
public:
    stack<int> q1; // 入栈
    stack<int> q2; // 出栈

    void push(int x) {
        q1.push(x);
    }

    int pop() {
        if (!q2.empty()) {
            int m = q2.top();
            q2.pop();
            return m;
        } else {
            while (!q1.empty()) {
                q2.push(q1.top());
                q1.pop();
            }
            int n = q2.top();
            q2.pop();
            return n;
        }
    }

    int peek() {
        if (!q2.empty()) {
            return q2.top();
        } else {
            while (!q1.empty()) {
                q2.push(q1.top());
                q1.pop();
            }
            return q2.top();
        }
    }

    bool empty() {
        return q1.empty() && q2.empty();
    }
};

力扣 设计循环队列

题目链接： https://leetcode.cn/problems/design-circular-queue/

思路： 使用数组模拟，通过取模运算实现循环。需注意区分空和满状态（通常预留一个空间）。

typedef struct {
    int* a;
    int front;
    int rear;
    int k;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->front = obj->rear = 0;
    obj->k = k;
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) return false;
    obj->a[obj->rear] = value;
    obj->rear = (++obj->rear) % (obj->k + 1);
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) return false;
    obj->front = (++obj->front) % (obj->k + 1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) return -1;
    return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) return -1;
    return obj->a[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

注：队列和栈均属于线性数据结构，循环队列亦为线性结构。内存分配后务必释放，避免泄漏。