用栈实现队列

队列可以通过两个栈来实现。先以 ADT 形式开放以下栈操作。

typedef struct stack_t stack_t;

stack_t* alloc_stack(void);
int empty(stack_t*);
void free_stack(stack_t*);
void push(stack_t*, int /*elem*/);
int pop(stack_t*);

为了方便看官测试，我们以单向链表实现以上接口。

#include <malloc.h>
#include <stddef.h>

struct node_t
{
    int elem;
    struct node_t* next;
};

struct stack_t
{
    struct node_t* top;
};

struct stack_t*
alloc_stack(void)
{
    return calloc(1, sizeof (struct stack_t));
}

int
empty(struct stack_t* stack)
{
    return stack->top == 0;
}

void
free_stack(struct stack_t* stack)
{
    while (!empty(stack)) {
        struct node_t* next = stack->top->next;
        free(stack->top);
        stack->top = next;
    }
    free(stack);
}

void
push(struct stack_t* stack, int elem)
{
    struct node_t* node;
    struct node_t* top = malloc(sizeof (struct node_t));
    top->elem = elem;
    top->next = stack->top;
    stack->top = top;
}

int
pop(struct stack_t* stack)
{
    int elem;
    struct node_t top;
    
    if (stack->top == 0)
        return 0;

    top = *stack->top;
    free(stack->top);
    stack->top = top.next;
    
    return top.elem;
}

用两个栈实现队列的思路是：用一个栈存储输入的数据，另一个栈负责输出。将输入的数据按顺序从输入栈 pop 并 push 到输出栈，原本的元素顺序便会反转，从后进先出变为先进先出。

struct queue_t
{
    struct stack_t* in;
    struct stack_t* out;
};

struct queue_t*
alloc_queue(void)
{
    struct queue_t* queue = malloc(sizeof (struct queue_t));
    queue->in = alloc_stack();
    queue->out = alloc_stack();
    return queue;
}

void
free_queue(struct queue_t* queue)
{
    free_stack(queue->in);
    free_stack(queue->out);
    free(queue);
}

void
enqueue(struct queue_t* queue, int elem)
{
    push(queue->in, elem);
}

int
dequeue(struct queue_t* queue)
{
    if (empty(queue->out))
        while (!empty(queue->in))
            push(queue->out, pop(queue->in));
    return pop(queue->out);
}

时间复杂度（n=队列中元素数量）：最坏场合下 dequeue()∈Ɵ(n*(push()+pop()))，平摊分析下 dequeue()∈Ɵ(pop())，而 enqueue∈Ɵ(push())。