数据结构基础：栈与队列的实现原理

进栈操作

进栈只能放在最上面，需检查栈是否已满。

// 进栈操作
bool Push(SqStack *S, int x) {
    if (S->top == MAXSIZE) {
        return false; // 栈满
    }
    S->top++;      // 栈顶指针加 1
    S->data[S->top] = x; // 将 x 入栈
    return true;   // 入栈成功
}

出栈操作

出栈是从最上面拿走一个元素，需检查栈是否为空。

// 出栈操作
bool Pop(SqStack *S, int *x) {
    if (S->top == -1) {
        return false; // 栈为空
    }
    *x = S->data[S->top]; // 将栈顶元素出栈
    S->top--;             // 栈顶指针减 1
    return true;          // 出栈成功
}

获取栈顶元素

只想查看栈顶元素而不移除它。

// 获取栈顶元素
bool GetTop(SqStack *S, int *x) {
    if (S->top == -1) {
        return false; // 栈为空
    }
    *x = S->data[S->top]; // 将栈顶元素赋值给 x
    return true;          // 获取成功
}

2.2 共享栈

共享栈让两个栈共享同一块数组空间，栈底分别在数组的两端，向中间生长。

建立

// 共享栈建立
typedef struct {
    int data[100]; // 栈的数组
    int top;       // 第一个栈的栈顶指针
    int top1;      // 第二个栈的栈顶指针
} SharedStack; // 共享栈的类型定义

初始化

初始化时，第一个栈的 top 在 -1，第二个栈的 top1 在最大容量处。

// 初始化
void InitSharedStack(SharedStack *S) {
    S->top = -1;     // 将栈顶指针设为 -1
    S->top1 = MAXSIZE; // 将栈顶指针设为最大容量
}

当 top + 1 == top1 时，表示栈满。

2.3 链栈

链栈用链表实现，链表的头结点作为栈顶，进栈和出栈操作都能在 O(1) 时间内完成。

建立

// 链栈建立
typedef struct LinkNode {
    int data;
    struct LinkNode *next;
} LinkNode;

typedef LinkNode* LinkStack; // 链栈的类型定义

这里栈顶指针就是链表的头指针，进栈就是在头结点前插入新节点，出栈就是删除头结点。

三、队列

队列是'先进先出'（FIFO）的，只能在队尾插入（入队），在队头删除（出队）。

顺序队列

顺序队列用数组实现，存在假溢出问题。即 front 和 rear 都会往后移动，可能导致数组前面的空间浪费。

定义

初始化时，front 和 rear 都指向 0。

// 队列定义
typedef struct {
    int data[100]; // 队列的数组
    int front;     // 队头指针
    int rear;      // 队尾指针
} SqQueue; // 顺序队列的类型定义

初始化队列

// 初始化队列
void InitQueue(SqQueue *Q) {
    Q->front = Q->rear = 0; // 将队头指针和队尾指针设为 0
}

判断队列是否为空

// 判断队列是否为空
bool QueueEmpty(SqQueue *Q) {
    if (Q->front == Q->rear) {
        return true; // 队列为空
    } else {
        return false; // 队列不为空
    }
}

入队操作

// 入队操作
bool EnQueue(SqQueue *Q, int x) {
    if (Q->rear == MAXSIZE) {
        return false; // 队列满
    }
    Q->data[Q->rear] = x; // 将 x 入队
    Q->rear++;            // 队尾指针加 1
    return true;          // 入队成功
}

出队操作

// 出队操作
bool DeQueue(SqQueue *Q, int *x) {
    if (Q->front == Q->rear) {
        return false; // 队列为空
    }
    *x = Q->data[Q->front]; // 将队头元素赋值给 x
    Q->front++;             // 队头指针加 1
    return true;            // 出队成功
}

解决假溢出问题

法一：牺牲一个单元

上述方法中 rear 到达数组末尾时，即使前面有空位也会被判为队满。可以通过牺牲一个存储单元来解决，但这通常不是最优解。

法二：增加长度变量

增加一个 size 变量记录队列长度，队满条件是 size == MaxSize，队空条件是 size == 0。

#define MaxSize 10
typedef struct {
    int data[10];
    int front, rear;
    int size; // 队列当前长度
} SqQueue;

法三：增加 tag 变量

增加一个 tag 变量，记录最近操作是插入（1）还是删除（0）。队满条件是 front == rear && tag == 1，队空条件是 front == rear && tag == 0。

#define MaxSize 10
typedef struct {
    int data[10];
    int front, rear;
    int tag; // 最近进行的是删除 (0)/插入 (1)
} SqQueue;

链式存储实现队列

链式队列用链表实现，队头指针指向头结点，队尾指针指向最后一个节点。

定义一个链式队列

// 链队列的节点类型定义
typedef struct LinkNode {
    int data;
    struct LinkNode *next;
} LinkNode;

// 链队列的类型定义
typedef struct {
    LinkNode *front, *rear; // 队头指针和队尾指针
} LinkQueue;

初始化（带头结点）

头结点不存数据，只是为了操作方便。

// 初始化链队列
void InitQueue(LinkQueue *Q) {
    // 初始时队头指针和队尾指针都指向头结点
    Q->front = Q->rear = (LinkNode *)malloc(sizeof(LinkNode));
    Q->front->next = NULL; // 头结点的 next 指针设为 NULL
}

// 判断队列是否为空
bool QueueEmpty(LinkQueue *Q) {
    if (Q->front == Q->rear) {
        return true; // 队列为空
    } else {
        return false; // 队列不为空
    }
}

入队（带头结点）

入队就是在队尾添加新节点，然后把 rear 移到新节点。

// 入队操作（带头结点）
bool EnQueue(LinkQueue *Q, int x) {
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    if (s == NULL) {
        return false; // 内存分配失败
    }
    s->data = x;
    s->next = NULL;
    Q->rear->next = s; // 将原队尾节点的 next 指针指向新节点
    Q->rear = s;       // 将队尾指针指向新节点
    return true;       // 入队成功
}

入队（不带头结点）

// 入队操作（不带头结点）
bool EnQueue(LinkQueue *Q, int x) {
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    if (s == NULL) {
        return false;
    }
    s->data = x;
    s->next = NULL;

    if (QueueEmpty(Q)) {
        Q->front = s;
        Q->rear = s;
    } else {
        Q->rear->next = s;
        Q->rear = s;
    }
    return true;
}

不带头结点的链式队列入队操作，核心区别在于需要处理'首次入队'的特殊情况。

出队（带头结点）

// 出队操作（带头结点）
bool DeQueue(LinkQueue *Q, int *x) {
    if (QueueEmpty(Q)) {
        return false;
    }
    LinkNode *p = Q->front->next; // p 指向队头元素节点
    *x = p->data;                 // 保存出队元素的值
    Q->front->next = p->next;     // 头结点跳过队头元素

    if (Q->rear == p) {           // 若出队的是最后一个元素
        Q->rear = Q->front;       // 队尾指针需指向头结点
    }
    free(p);                      // 释放出队节点的内存
    return true;
}

出队（不带头结点）

// 出队操作（不带头结点）
bool DeQueue(LinkQueue *Q, int *x) {
    if (QueueEmpty(Q)) {
        return false;
    }
    LinkNode *p = Q->front; // p 指向队头元素节点
    *x = p->data;

    if (Q->front == Q->rear) { // 若队列只有一个元素
        Q->front = Q->rear = NULL;
    } else {
        Q->front = Q->front->next; // 队头指针后移
    }
    free(p);
    return true;
}

队列满的条件

• 顺序存储：预分配的空间耗尽时队满。
• 链式存储：一般不会队满，除非内存不足。

四、总结

栈和队列都是特殊的线性表，只是对操作的位置做了限制：

• 栈：只允许在栈顶操作，后进先出。
• 队列：只允许在队尾入队、队头出队，先进先出。

它们的实现可以用数组（顺序存储）或链表（链式存储），各有优缺点：

• 顺序存储：访问快，但大小固定（或需要扩容）。
• 链式存储：大小灵活，但访问需要遍历指针。

掌握它们的逻辑和实现，对于理解更复杂的数据结构至关重要。