C语言栈与队列怎么相互实现

C语言栈与队列怎么相互实现

1. 引言

在计算机科学中，栈（Stack）和队列（Queue）是两种非常重要的数据结构。它们分别遵循不同的操作规则：栈遵循“后进先出”（LIFO）的原则，而队列遵循“先进先出”（FIFO）的原则。尽管它们在操作规则上有所不同，但栈和队列之间可以通过相互实现来展示它们之间的紧密联系。

本文将详细介绍如何在C语言中通过栈来实现队列，以及如何通过队列来实现栈。我们将从基本概念入手，逐步深入到具体的实现细节，并通过代码示例来帮助读者更好地理解这些概念。

2. 栈与队列的基本概念

2.1 栈（Stack）

栈是一种线性数据结构，它遵循“后进先出”（LIFO）的原则。栈的基本操作包括：

• Push：将元素压入栈顶。
• Pop：将栈顶元素弹出。
• Peek/Top：获取栈顶元素但不弹出。
• IsEmpty：判断栈是否为空。

栈通常用于实现递归算法、表达式求值、括号匹配等场景。

2.2 队列（Queue）

队列是一种线性数据结构，它遵循“先进先出”（FIFO）的原则。队列的基本操作包括：

• Enqueue：将元素加入队列的尾部。
• Dequeue：将队列头部的元素移除。
• Front：获取队列头部的元素但不移除。
• IsEmpty：判断队列是否为空。

队列通常用于实现任务调度、缓冲区管理、广度优先搜索等场景。

3. 用栈实现队列

3.1 思路分析

要用栈实现队列，我们需要模拟队列的“先进先出”特性。由于栈是“后进先出”的，我们需要使用两个栈来模拟队列的行为。具体思路如下：

1. 入队操作：将所有元素压入第一个栈（Stack1）。
2. 出队操作：如果第二个栈（Stack2）为空，则将Stack1中的所有元素依次弹出并压入Stack2，然后从Stack2中弹出栈顶元素。如果Stack2不为空，则直接从Stack2中弹出栈顶元素。

通过这种方式，我们可以确保先进入Stack1的元素会先进入Stack2，从而实现队列的“先进先出”特性。

3.2 代码实现

#include <stdio.h> #include <stdlib.h> #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; } Stack; void initStack(Stack *s) { s->top = -1; } int isEmpty(Stack *s) { return s->top == -1; } int isFull(Stack *s) { return s->top == MAX_SIZE - 1; } void push(Stack *s, int value) { if (isFull(s)) { printf("Stack overflow\n"); return; } s->data[++s->top] = value; } int pop(Stack *s) { if (isEmpty(s)) { printf("Stack underflow\n"); return -1; } return s->data[s->top--]; } int peek(Stack *s) { if (isEmpty(s)) { printf("Stack is empty\n"); return -1; } return s->data[s->top]; } typedef struct { Stack s1; Stack s2; } Queue; void initQueue(Queue *q) { initStack(&q->s1); initStack(&q->s2); } void enqueue(Queue *q, int value) { push(&q->s1, value); } int dequeue(Queue *q) { if (isEmpty(&q->s2)) { while (!isEmpty(&q->s1)) { push(&q->s2, pop(&q->s1)); } } return pop(&q->s2); } int front(Queue *q) { if (isEmpty(&q->s2)) { while (!isEmpty(&q->s1)) { push(&q->s2, pop(&q->s1)); } } return peek(&q->s2); } int isEmptyQueue(Queue *q) { return isEmpty(&q->s1) && isEmpty(&q->s2); } int main() { Queue q; initQueue(&q); enqueue(&q, 1); enqueue(&q, 2); enqueue(&q, 3); printf("Front element: %d\n", front(&q)); // Output: 1 printf("Dequeue: %d\n", dequeue(&q)); // Output: 1 printf("Dequeue: %d\n", dequeue(&q)); // Output: 2 printf("Dequeue: %d\n", dequeue(&q)); // Output: 3 return 0; } 

3.3 代码解析

• Stack结构体：定义了一个栈结构体，包含一个数组data和一个栈顶指针top。
• initStack：初始化栈，将栈顶指针top设置为-1。
• isEmpty：判断栈是否为空。
• isFull：判断栈是否已满。
• push：将元素压入栈顶。
• pop：将栈顶元素弹出。
• peek：获取栈顶元素但不弹出。
• Queue结构体：定义了一个队列结构体，包含两个栈s1和s2。
• initQueue：初始化队列，初始化两个栈。
• enqueue：将元素压入s1栈。
• dequeue：如果s2栈为空，则将s1栈中的所有元素依次弹出并压入s2栈，然后从s2栈中弹出栈顶元素。
• front：获取队列头部的元素但不移除。
• isEmptyQueue：判断队列是否为空。

3.4 复杂度分析

• 时间复杂度：
  • Enqueue：O(1)，直接将元素压入s1栈。
  • Dequeue：O(n)，最坏情况下需要将s1栈中的所有元素移动到s2栈。
• 空间复杂度：O(n)，需要两个栈来存储元素。

4. 用队列实现栈

4.1 思路分析

要用队列实现栈，我们需要模拟栈的“后进先出”特性。由于队列是“先进先出”的，我们需要使用两个队列来模拟栈的行为。具体思路如下：

1. 入栈操作：将元素加入非空队列（Queue1或Queue2）。
2. 出栈操作：将非空队列中的元素依次出队并加入另一个空队列，直到只剩下一个元素，然后将该元素出队。

通过这种方式，我们可以确保最后进入队列的元素会最先出队，从而实现栈的“后进先出”特性。

4.2 代码实现

#include <stdio.h> #include <stdlib.h> #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int front; int rear; } Queue; void initQueue(Queue *q) { q->front = q->rear = -1; } int isEmpty(Queue *q) { return q->front == -1; } int isFull(Queue *q) { return (q->rear + 1) % MAX_SIZE == q->front; } void enqueue(Queue *q, int value) { if (isFull(q)) { printf("Queue overflow\n"); return; } if (isEmpty(q)) { q->front = q->rear = 0; } else { q->rear = (q->rear + 1) % MAX_SIZE; } q->data[q->rear] = value; } int dequeue(Queue *q) { if (isEmpty(q)) { printf("Queue underflow\n"); return -1; } int value = q->data[q->front]; if (q->front == q->rear) { q->front = q->rear = -1; } else { q->front = (q->front + 1) % MAX_SIZE; } return value; } int front(Queue *q) { if (isEmpty(q)) { printf("Queue is empty\n"); return -1; } return q->data[q->front]; } typedef struct { Queue q1; Queue q2; } Stack; void initStack(Stack *s) { initQueue(&s->q1); initQueue(&s->q2); } void push(Stack *s, int value) { if (!isEmpty(&s->q1)) { enqueue(&s->q1, value); } else { enqueue(&s->q2, value); } } int pop(Stack *s) { Queue *nonEmptyQueue, *emptyQueue; if (!isEmpty(&s->q1)) { nonEmptyQueue = &s->q1; emptyQueue = &s->q2; } else { nonEmptyQueue = &s->q2; emptyQueue = &s->q1; } while (nonEmptyQueue->front != nonEmptyQueue->rear) { enqueue(emptyQueue, dequeue(nonEmptyQueue)); } return dequeue(nonEmptyQueue); } int peek(Stack *s) { Queue *nonEmptyQueue, *emptyQueue; if (!isEmpty(&s->q1)) { nonEmptyQueue = &s->q1; emptyQueue = &s->q2; } else { nonEmptyQueue = &s->q2; emptyQueue = &s->q1; } while (nonEmptyQueue->front != nonEmptyQueue->rear) { enqueue(emptyQueue, dequeue(nonEmptyQueue)); } int value = dequeue(nonEmptyQueue); enqueue(emptyQueue, value); return value; } int isEmptyStack(Stack *s) { return isEmpty(&s->q1) && isEmpty(&s->q2); } int main() { Stack s; initStack(&s); push(&s, 1); push(&s, 2); push(&s, 3); printf("Top element: %d\n", peek(&s)); // Output: 3 printf("Pop: %d\n", pop(&s)); // Output: 3 printf("Pop: %d\n", pop(&s)); // Output: 2 printf("Pop: %d\n", pop(&s)); // Output: 1 return 0; } 

4.3 代码解析

• Queue结构体：定义了一个队列结构体，包含一个数组data、队头指针front和队尾指针rear。
• initQueue：初始化队列，将队头指针front和队尾指针rear设置为-1。
• isEmpty：判断队列是否为空。
• isFull：判断队列是否已满。
• enqueue：将元素加入队列的尾部。
• dequeue：将队列头部的元素移除。
• front：获取队列头部的元素但不移除。
• Stack结构体：定义了一个栈结构体，包含两个队列q1和q2。
• initStack：初始化栈，初始化两个队列。
• push：将元素加入非空队列。
• pop：将非空队列中的元素依次出队并加入另一个空队列，直到只剩下一个元素，然后将该元素出队。
• peek：获取栈顶元素但不弹出。
• isEmptyStack：判断栈是否为空。

4.4 复杂度分析

• 时间复杂度：
  • Push：O(1)，直接将元素加入非空队列。
  • Pop：O(n)，最坏情况下需要将非空队列中的所有元素移动到另一个空队列。
• 空间复杂度：O(n)，需要两个队列来存储元素。

5. 总结

通过本文的介绍，我们了解了如何在C语言中通过栈来实现队列，以及如何通过队列来实现栈。尽管栈和队列在操作规则上有所不同，但通过巧妙地使用两个栈或两个队列，我们可以模拟出另一种数据结构的行为。

在实际应用中，栈和队列的选择取决于具体的需求。栈适用于需要“后进先出”操作的场景，而队列适用于需要“先进先出”操作的场景。通过相互实现，我们可以更好地理解这两种数据结构的特性和应用场景。

希望本文的内容能够帮助读者更好地理解栈和队列的概念，并在实际编程中灵活运用这些数据结构。