用队列实现栈

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

typedef struct queue_t queue_t;

queue_t* alloc_queue(void);
void free_queue(queue_t*);
void enqueue(queue_t*, int /*elem*/);
int dequeue(queue_t*);
int size(queue_t*);

为了方便看官测试，我们以动态数组实现以上接口。

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

struct queue_t
{
    int* arr;
    size_t cap;
    size_t size;
};

struct queue_t*
alloc_queue(void)
{
    struct queue_t* queue = malloc(sizeof (struct queue_t));
    queue->cap = 2;
    queue->arr = malloc(queue->cap * sizeof (int));
    queue->size = 0;
    return queue;
}

void
free_queue(struct queue_t* queue)
{
    free(queue->arr);
    free(queue);
}

void
enqueue(struct queue_t* queue, int elem)
{
    if (queue->size >= queue->cap) {
        queue->cap *= 2;
        queue->arr = realloc(queue->arr, queue->cap * sizeof (int));
    }
    queue->arr[queue->size++] = elem;
}

int
dequeue(struct queue_t* queue)
{
    int elem;

    if (queue->size == 0)
        return 0;
    elem = queue->arr[0];
    memmove(queue->arr, queue->arr + 1, --queue->size * sizeof (int));
    return elem;
}

int
size(struct queue_t* queue)
{
    return queue->size;
}

以一个队列实现栈的思路是：将队列头部的元素重新添加到队列尾部，直到原队列尾部的元素被推到头部。此时队列中除头部外，其余元素的顺序依旧，如果进行 dequeue 操作，返回的便是最近一次添加到队列中的元素，也就满足了栈后进先出的特性，而对于整个队列来说便如同移除了尾部元素。

struct stack_t
{
    queue_t* queue;
};

struct stack_t*
alloc_stack(void)
{
    struct stack_t* stack = malloc(sizeof (struct stack_t));
    stack->queue = alloc_queue();
    return stack;
}

void
free_stack(struct stack_t* stack)
{
    free_queue(stack->queue);
    free(stack);
}

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

int
pop(struct stack_t* stack)
{
    int i;

    for (i = 1; i < queue; ++i)
        enqueue(stack->queue, dequeue(stack->queue));
    return dequeue(stack->queue);
}

以上是在每次 pop 时将队列尾部推至队列头部。我们也可以采用抢先模式在 push 时就为 pop 做好准备工作。每次 push 时，我们可以用相同的方法将最近添加的元素推至队列头部，如此一来队列实际上就是以相反的顺序存储了元素，故而 pop 时从头部 dequeue 即可实现后进先出。

void
push(struct stack_t* stack, int elem)
{
    int i;
    
    enqueue(stack->queue, elem);
    for (i = 1; i < queue; ++i)
        enqueue(stack->queue, dequeue(stack->queue));
}

int
pop(struct stack_t* stack)
{
    return dequeue(stack->queue);
}

时间复杂度（n=栈中元素数量）：第一个版本的栈实现，push()∈Ɵ(enqueue())，pop()∈Ɵ(n*(enqueue()+dequeue()))；第二个版本的栈实现，push()∈Ɵ(n*(enqueue()+dequeue()))，pop()∈Ɵ(dequeue())。可见第一个版本的 push 效率高，pop 效率低，而第二个版本反之。