DB2-两个栈模拟一个队列¶

代码实现¶

C
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100  // 栈的最大容量

/**
 * 栈的顺序存储结构定义
 */
typedef struct {
    int data[MAXSIZE];  // 存储栈元素的数组
    int top;            // 栈顶指针
} Stack;

/**
 * 初始化栈
 * @param s 指向栈的指针
 */
void init_stack(Stack* s) {
    s->top = -1;
}

/**
 * 判断栈是否为空
 * @param s 栈
 * @return 空栈返回true，非空返回false
 */
bool is_empty(Stack s) {
    return s.top == -1;
}

/**
 * 判断栈是否已满
 * @param s 栈
 * @return 栈满返回true，未满返回false
 */
bool is_full(Stack s) {
    return s.top == MAXSIZE - 1;
}

C
/**
 * 入队操作（使用两个栈模拟队列）
 * @param s1 栈1（负责入队）
 * @param s2 栈2（负责出队）
 * @param x 要入队的元素
 * @return 入队成功返回true，队满返回false
 */
bool enqueue(Stack* s1, Stack* s2, int x) {
    // 1. 判断空间是否溢出
    // 若栈1已满，且栈2不为空，说明总空间已用完
    if (s1->top == MAXSIZE - 1 && s2->top != -1) {
        printf("队列已满，无法入队\n");
        return false;
    }

    // 2. 元素转移（仅在必要时）
    // 若栈1满但栈2为空，则将栈1中元素逐个弹出并压入栈2
    if (s1->top == MAXSIZE - 1 && s2->top == -1) {
        while (s1->top != -1) {
            s2->data[++s2->top] = s1->data[s1->top--];
        }
    }

    // 3. 完成入队：将新元素压入栈1顶
    if (s1->top < MAXSIZE - 1) {
        s1->data[++s1->top] = x;
        return true;
    } else {
        return false;  // 理论上不应该到达这里
    }
}

/**
 * 出队操作（使用两个栈模拟队列）
 * @param s1 栈1（负责入队）
 * @param s2 栈2（负责出队）
 * @param x 指向存储出队元素的指针
 * @return 出队成功返回true，队空返回false
 */
bool dequeue(Stack* s1, Stack* s2, int* x) {
    // 1. 判断是否为空队列
    // 如果两个栈都为空，说明队列为空
    if (s2->top == -1 && s1->top == -1) {
        printf("队列为空，无法出队\n");
        return false;
    }

    // 2. 若s2不为空：直接从s2弹出栈顶元素
    if (s2->top != -1) {
        *x = s2->data[s2->top--];
        return true;
    }

    // 3. 若s2为空而s1不为空：将s1中的所有元素依次弹出并压入s2
    if (s2->top == -1 && s1->top != -1) {
        while (s1->top != -1) {
            s2->data[++s2->top] = s1->data[s1->top--];
        }
    }

    // 从s2弹出栈顶元素
    *x = s2->data[s2->top--];
    return true;
}

/**
 * 判断队列是否为空
 * @param s1 栈1
 * @param s2 栈2
 * @return 空队列返回true，非空返回false
 */
bool is_queue_empty(Stack s1, Stack s2) {
    return (s1.top == -1 && s2.top == -1);
}

/**
 * 判断队列是否已满
 * @param s1 栈1
 * @param s2 栈2
 * @return 队满返回true，未满返回false
 */
bool is_queue_full(Stack s1, Stack s2) {
    return (s1.top == MAXSIZE - 1 && s2.top != -1);
}

/**
 * 获取队列中元素个数
 * @param s1 栈1
 * @param s2 栈2
 * @return 队列中元素个数
 */
int get_queue_size(Stack s1, Stack s2) {
    return (s1.top + 1) + (s2.top + 1);
}

算法原理图解¶

双栈模拟队列结构：¶

Text Only

入队操作：使用栈1（s1）
出队操作：使用栈2（s2）

初始状态：
s1: [ ][ ][ ][ ]    s2: [ ][ ][ ][ ]
     ↑                    ↑
   top=-1               top=-1

入队1,2,3：
s1: [1][2][3][ ]    s2: [ ][ ][ ][ ]
         ↑                ↑
       top=2            top=-1

出队操作：
需要将s1中元素转移到s2：
s1: [ ][ ][ ][ ]    s2: [3][2][1][ ]
     ↑                    ↑
   top=-1               top=2

然后从s2出队：
出队1：s2: [3][2][ ]  出队2：s2: [3][ ][ ]  出队3：s2: [ ][ ][ ]
              ↑                 ↑                ↑
            top=1             top=0            top=-1

算法执行流程图解¶

入队操作流程：¶

Text Only

enqueue(4)：
1. 检查空间：s1未满，直接入栈
s1: [1][2][3][4]    s2: [3][2][1][ ]
         ↑                ↑
       top=3            top=2

enqueue(5)：
1. 检查空间：s1已满但s2不为空 → 队满
返回false

特殊情况：s1满但s2空
s1: [1][2][3][4]    s2: [ ][ ][ ][ ]
         ↑                ↑
       top=3            top=-1

enqueue(5)：
1. s1满但s2空，转移元素
   s1: [ ][ ][ ][ ]    s2: [4][3][2][1]
        ↑                    ↑
      top=-1               top=3

2. 新元素入s1
   s1: [5][ ][ ][ ]    s2: [4][3][2][1]
        ↑                    ↑
      top=0                top=3

出队操作流程：¶

Text Only

dequeue(&x)：
情况1：s2不为空，直接出栈
s1: [1][2][3][ ]    s2: [3][2][1][ ]
         ↑                ↑
       top=2            top=2

x = s2->data[2] = 3
s1: [1][2][3][ ]    s2: [3][2][ ][ ]
         ↑                ↑
       top=2            top=1

情况2：s2为空，s1不为空
s1: [4][5][ ][ ]    s2: [ ][ ][ ][ ]
         ↑                ↑
       top=1            top=-1

转移s1到s2：
s1: [ ][ ][ ][ ]    s2: [5][4][ ][ ]
        ↑                    ↑
      top=-1               top=1

然后出队：x = 4
s1: [ ][ ][ ][ ]    s2: [5][ ][ ][ ]
        ↑                    ↑
      top=-1               top=0

复杂度分析¶

时间复杂度分析：¶

入队操作： - 最好情况：O(1) - s1未满，直接入栈 - 最坏情况：O(n) - 需要转移所有元素 - 摊还复杂度：O(1) - 每个元素最多被转移一次

出队操作： - 最好情况：O(1) - s2不为空，直接出栈 - 最坏情况：O(n) - 需要转移所有元素 - 摊还复杂度：O(1) - 每个元素最多被转移一次

总体摊还时间复杂度：O(1)

空间复杂度：O(n)¶

两个栈空间：总共2×MAXSIZE的存储空间
实际使用：最多存储n个元素
总体空间复杂度：O(n)

算法优化版本¶

C
/**
 * 优化版本：使用结构体封装
 */
typedef struct {
    Stack s1;  // 入队栈
    Stack s2;  // 出队栈
} QueueWithStacks;

void init_queue(QueueWithStacks* q) {
    init_stack(&q->s1);
    init_stack(&q->s2);
}

bool enqueue_optimized(QueueWithStacks* q, int x) {
    if (is_full(q->s1) && !is_empty(q->s2)) {
        return false;  // 队满
    }

    if (is_full(q->s1) && is_empty(q->s2)) {
        // 转移元素
        while (!is_empty(q->s1)) {
            int temp;
            // 模拟出栈入栈
            temp = q->s1.data[q->s1.top--];
            q->s2.data[++q->s2.top] = temp;
        }
    }

    if (!is_full(q->s1)) {
        q->s1.data[++q->s1.top] = x;
        return true;
    }

    return false;
}

bool dequeue_optimized(QueueWithStacks* q, int* x) {
    if (is_empty(q->s1) && is_empty(q->s2)) {
        return false;  // 队空
    }

    if (!is_empty(q->s2)) {
        *x = q->s2.data[q->s2.top--];
        return true;
    }

    // 转移s1到s2
    while (!is_empty(q->s1)) {
        int temp = q->s1.data[q->s1.top--];
        q->s2.data[++q->s2.top] = temp;
    }

    *x = q->s2.data[q->s2.top--];
    return true;
}

与其他队列实现的对比¶

实现方式	时间复杂度	空间复杂度	特点
顺序队列	O(1)	O(n)	简单但可能假溢出
循环队列	O(1)	O(n)	高效但需预分配
链队列	O(1)	O(n)	动态分配，无容量限制
双栈队列	O(1)摊还	O(n)	只使用栈操作，理论优雅

测试用例¶

C
/**
 * 测试函数
 */
void test_stack_queue() {
    Stack s1, s2;
    init_stack(&s1);
    init_stack(&s2);

    printf("队列初始化完成\n");
    printf("队列是否为空：%s\n", 
           is_queue_empty(s1, s2) ? "是" : "否");

    // 测试入队
    for (int i = 1; i <= 5; i++) {
        if (enqueue(&s1, &s2, i)) {
            printf("入队：%d\n", i);
        } else {
            printf("入队失败：%d\n", i);
        }
    }

    printf("队列大小：%d\n", get_queue_size(s1, s2));

    // 测试出队
    int x;
    while (dequeue(&s1, &s2, &x)) {
        printf("出队：%d\n", x);
    }

    printf("队列是否为空：%s\n", 
           is_queue_empty(s1, s2) ? "是" : "否");
}

算法特点¶

核心思想：利用两个栈的特性，一个负责入队（栈1），一个负责出队（栈2），通过元素在两个栈之间的转移实现队列的先进先出特性。

关键技术： 1. 栈的反转特性：栈的后进先出与队列的先进先出通过两次反转实现 2. 延迟转移：只在必要时才进行元素转移，提高效率 3. 空间优化：充分利用两个栈的存储空间

优势： - 理论优雅：只使用栈的基本操作实现队列 - 摊还高效：虽然单次操作可能为O(n)，但摊还后为O(1) - 灵活性好：可以根据需要动态调整策略

应用场景： - 函数式编程语言中的队列实现 - 需要严格使用栈操作的场景 - 理论研究和教学演示 - 某些特定的系统设计

这种双栈模拟队列的方法在理论计算机科学中具有重要意义，展示了如何用一种数据结构来实现另一种数据结构的功能。