C语言数据结构之栈与队列的相互实现

一、栈(Stack)的介绍

1.1 栈的定义

栈(Stack)是一种特殊的线性表，只能在表的一端插入和删除元素，这一端被称为栈顶，另一端被称为栈底。栈是一种后进先出(LIFO, Last In First Out)的数据结构。栈的插入操作叫做入栈(push)，删除操作叫做出栈(pop)。

1.2 栈的实现

栈可以用数组或链表来实现。以下是用数组实现栈的代码示例。

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int top;    // 栈顶指针
} SqStack;

// 初始化栈
void InitStack(SqStack *s) {
    s->top = -1;
}

// 判断栈是否为空
bool IsEmpty(SqStack *s) {
    return s->top == -1;
}

// 判断栈是否已满
bool IsFull(SqStack *s) {
    return s->top == MAXSIZE - 1;
}

// 入栈操作
void Push(SqStack *s, int e) {
    if (IsFull(s)) {
        printf("Stack is full\n");
        return;
    }
    s->top++;
    s->data[s->top] = e;
}

// 出栈操作
int Pop(SqStack *s) {
    if (IsEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    }
    int e = s->data[s->top];
    s->top--;
    return e;
}

二、队列(Queue)的介绍

2.1 队列的定义

队列(Queue)也是一种特殊的线性表，只能在表的一端进行插入，另一端进行删除。这一端插入元素的操作叫做入队(enqueue)，删除元素的操作叫做出队(dequeue)。队列是一种先进先出(FIFO，First In First Out)的数据结构。

2.2 队列的实现

队列也可以用数组或链表来实现。以下是用数组实现队列的代码示例。

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int front, rear;    // 队头和队尾指针
} SqQueue;

// 初始化队列
void InitQueue(SqQueue *q) {
    q->front = q->rear = 0;
}

// 判断队列是否为空
bool IsEmpty(SqQueue *q) {
    return q->front == q->rear;
}

// 判断队列是否已满
bool IsFull(SqQueue *q) {
    return (q->rear + 1) % MAXSIZE == q->front;
}

// 入队操作
void Enqueue(SqQueue *q, int e) {
    if (IsFull(q)) {
        printf("Queue is full\n");
        return;
    }
    q->data[q->rear] = e;
    q->rear = (q->rear + 1) % MAXSIZE;
}

// 出队操作
int Dequeue(SqQueue *q) {
    if (IsEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int e = q->data[q->front];
    q->front = (q->front + 1) % MAXSIZE;
    return e;
}

三、栈与队列的相互实现

3.1 栈实现队列

栈实现队列，需要用到两个栈，一个栈作为插入栈(in-stack)，另一个栈作为删除栈(out-stack)。元素插入时，先将元素插入插入栈，取出元素时，先将插入栈中的元素全部转移至删除栈中，然后再从删除栈中出栈。如果删除栈中没元素了，就需要将插入栈中的所有元素转移至删除栈中。

以下是用两个栈实现队列的代码示例。

typedef struct {
    SqStack in_stack;   // 插入栈
    SqStack out_stack;  // 删除栈
} MyQueue;

// 初始化队列
void InitMyQueue(MyQueue *q) {
    InitStack(&q->in_stack);
    InitStack(&q->out_stack);
}

// 判断队列是否为空
bool IsEmpty(MyQueue *q) {
    return IsEmpty(&q->in_stack) && IsEmpty(&q->out_stack);
}

// 入队操作
void Enqueue(MyQueue *q, int e) {
    Push(&q->in_stack, e);
}

// 出队操作
int Dequeue(MyQueue *q) {
    if (IsEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    if (IsEmpty(&q->out_stack)) {
        while (!IsEmpty(&q->in_stack)) {
            int e = Pop(&q->in_stack);
            Push(&q->out_stack, e);
        }
    }
    return Pop(&q->out_stack);
}

3.2 队列实现栈

队列实现栈，需要用到两个队列，一个队列作为主队列(main-queue)，另一个队列作为临时队列(temp-queue)。元素入栈时，直接插入主队列，出栈时，将主队列中的元素依次弹出并插入临时队列，直到只剩一个元素，那么这个元素就是要弹出的元素。此时再交换主队列和临时队列的指针即可。

以下是用两个队列实现栈的代码示例。

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int front, rear;    // 队头和队尾指针
} SqQueue;

typedef struct {
    SqQueue main_queue; // 主队列
    SqQueue temp_queue; // 临时队列
} MyStack;

// 初始化栈
void InitMyStack(MyStack *s) {
    InitQueue(&s->main_queue);
    InitQueue(&s->temp_queue);
}

// 判断栈是否为空
bool IsEmpty(MyStack *s) {
    return IsEmpty(&s->main_queue);
}

// 入栈操作
void Push(MyStack *s, int e) {
    Enqueue(&s->main_queue, e);
}

// 出栈操作
int Pop(MyStack *s) {
    if (IsEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    }
    while (s->main_queue.rear - s->main_queue.front > 1) {
        int e = Dequeue(&s->main_queue);
        Enqueue(&s->temp_queue, e);
    }
    int e = Dequeue(&s->main_queue);
    SwapQueue(&s->main_queue, &s->temp_queue);
    return e;
}

四、示例说明

4.1 栈实现队列示例说明

以下是一个栈实现队列的示例说明。

MyQueue q;
InitMyQueue(&q);

Enqueue(&q, 1);
Enqueue(&q, 2);
Enqueue(&q, 3);

printf("%d\n", Dequeue(&q));    // 1
printf("%d\n", Dequeue(&q));    // 2

Enqueue(&q, 4);

printf("%d\n", Dequeue(&q));    // 3
printf("%d\n", Dequeue(&q));    // 4

Dequeue(&q);    // 队列已经为空，再次操作会有提示：Queue is empty

4.2 队列实现栈示例说明

以下是一个队列实现栈的示例说明。

MyStack s;
InitMyStack(&s);

Push(&s, 1);
Push(&s, 2);
Push(&s, 3);

printf("%d\n", Pop(&s));    // 3
printf("%d\n", Pop(&s));    // 2

Push(&s, 4);

printf("%d\n", Pop(&s));    // 4
printf("%d\n", Pop(&s));    // 1

Pop(&s);    // 栈已经为空，再次操作会有提示：Stack is empty

以上示例说明演示了栈与队列的相互实现，在实际的开发过程中，根据具体的需求选择合适的数据结构来实现相关功能。