C语言利用栈与队列实现数据逆置的算法解析

算法核心逻辑

要实现队列中元素的逆置，关键在于引入一个辅助栈。整个操作过程分为两个阶段：

1. 阶段一：队列转栈。当源队列不为空时，持续执行出队操作，并将取出的元素立即压入栈中。由于栈的特性是后进先出，原本先进入队列的元素会最后被压入栈底，从而改变了相对顺序。
2. 阶段二：栈转队列。当原队列为空且栈不为空时，持续执行出栈操作，将弹出的元素重新入队到原队列中。此时，原本在栈底的元素（即最初进入队列的元素）会被最先取出，从而实现整体的逆序效果。

C语言完整实现代码

以下代码实现了基于顺序存储结构的栈和队列，并包含了核心的逆置函数 ReverseQueue。请注意，代码使用了简单的数组模拟实现，适用于固定大小的场景。

#include <stdio.h>
#define MaxSize 10
typedef int ElemType;

// 队列结构定义
typedef struct {
    ElemType data[MaxSize];
    int front, rear;
} Queue;

// 栈结构定义
typedef struct {
    ElemType data[MaxSize];
    int top;
} SqStack;

// --- 栈的操作函数 ---
void InitStack(SqStack &S) {
    S.top = -1;
}

bool EmptyStack(SqStack S) {
    return (S.top == -1);
}

bool OverflowStack(SqStack S) {
    return (S.top == MaxSize - 1);
}

bool Push(SqStack &S, ElemType x) {
    if (OverflowStack(S)) return false;
    S.data[++S.top] = x;
    return true;
}

bool Pop(SqStack &S, ElemType &x) {
    if (EmptyStack(S)) return false;
    x = S.data[S.top--];
    return true;
}

// --- 队列的操作函数 ---
void InitQueue(Queue &Q) {
    Q.front = Q.rear = 0;
}

bool IsEmpty(Queue Q) {
    return (Q.front == Q.rear);
}

bool IsOverflow(Queue Q) {
    return ((Q.rear + 1) % MaxSize == Q.front);
}

bool EnQueue(Queue &Q, ElemType x) {
    if (IsOverflow(Q)) return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;
    return true;
}

bool DeQueue(Queue &Q, ElemType &x) {
    if (IsEmpty(Q)) return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

// --- 核心：队列逆置函数 ---
bool ReverseQueue(Queue &Q) {
    SqStack S;
    ElemType x;
    InitStack(S);
    
    // 第一步：队列所有元素出队并入栈
    while (!IsEmpty(Q)) {
        DeQueue(Q, x);
        Push(S, x);
    }
    
    // 第二步：栈所有元素出栈并重新入队
    while (!EmptyStack(S)) {
        Pop(S, x);
        EnQueue(Q, x);
    }
    return true;
}

int main() {
    Queue Q;
    ElemType val;
    
    InitQueue(Q);
    // 入队测试数据: 1, 2, 3
    EnQueue(Q, 1);
    EnQueue(Q, 2);
    EnQueue(Q, 3);
    
    printf("逆置前队列头部元素: ");
    DeQueue(Q, val); // 查看但不移除以保持简单演示
    
    // 重新构建队列以便演示逆置结果
    InitQueue(Q);
    EnQueue(Q, 1);
    EnQueue(Q, 2);
    EnQueue(Q, 3);
    
    ReverseQueue(Q);
    
    printf("\n逆置后队列头部元素: %d\n", Q.data[Q.front]);
    return 0;
}

执行流程演示

为了更直观地理解算法运作过程，假设初始队列中的元素顺序为 1 → 2 → 3 → 出队方向。

• 步骤1：清空队列并填充栈
  - 取出队首 1，压入栈。栈状态：[1]
  - 取出队首 2，压入栈。栈状态：[1, 2]（2在顶）
  - 取出队首 3，压入栈。栈状态：[1, 2, 3]（3在顶）
  - 此时队列为空。
• 步骤2：清空栈并回填队列
  - 弹出栈顶 3，入队。队列变为：3 → ...
  - 弹出栈顶 2，入队。队列变为：3 → 2 → ...
  - 弹出栈顶 1，入队。队列变为：3 → 2 → 1 → ...
  - 此时栈为空。

最终，队列中的元素顺序由 1,2,3 成功逆置为 3,2,1。这种方法的时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 为队列中的元素个数。

注意事项

• 循环队列边界：上述代码使用循环队列实现，涉及取模运算 (rear+1)%MaxSize，在处理实际生产环境的大容量数据时，建议考虑动态扩容机制或链表实现以避免空间浪费和溢出风险。
• 输入验证：在实际应用中，建议在操作前检查队列是否为空，虽然本例的 ReverseQueue 对空队列也能正确返回（不执行任何操作），但良好的防御性编程习惯有助于排查潜在错误。
• 内存管理：如果使用指针实现的链式栈和链式队列，需在程序结束时释放所有分配的节点内存，防止内存泄漏。

以上就是的详细内容，更多关于的资料请关注本站其它相关文章！