C语言怎么实现栈和队列

C语言怎么实现栈和队列

在计算机科学中，栈（Stack）和队列（Queue）是两种非常重要的数据结构。它们广泛应用于各种算法和程序中，如表达式求值、函数调用、任务调度等。本文将详细介绍如何在C语言中实现栈和队列，并通过代码示例帮助读者理解其工作原理。

1. 栈（Stack）

1.1 栈的基本概念

栈是一种遵循后进先出（LIFO, Last In First Out）原则的线性数据结构。这意味着最后进入栈的元素将最先被移除。栈的操作主要包括：

• Push（入栈）：将元素添加到栈的顶部。
• Pop（出栈）：移除并返回栈顶的元素。
• Peek（查看栈顶元素）：返回栈顶的元素但不移除它。
• IsEmpty（判断栈是否为空）：检查栈是否为空。

1.2 栈的实现

在C语言中，栈可以通过数组或链表来实现。下面我们将分别介绍这两种实现方式。

1.2.1 使用数组实现栈

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

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

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

// 判断栈是否已满
bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈
void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("栈已满，无法入栈\n");
        return;
    }
    s->data[++s->top] = value;
}

// 出栈
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("栈为空，无法出栈\n");
        exit(EXIT_FLURE);
    }
    return s->data[s->top--];
}

// 查看栈顶元素
int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("栈为空，无法查看栈顶元素\n");
        exit(EXIT_FLURE);
    }
    return s->data[s->top];
}

int main() {
    Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    printf("栈顶元素: %d\n", peek(&s));

    printf("出栈元素: %d\n", pop(&s));
    printf("出栈元素: %d\n", pop(&s));

    printf("栈顶元素: %d\n", peek(&s));

    return 0;
}

1.2.2 使用链表实现栈

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *top;
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = NULL;
}

// 判断栈是否为空
bool isEmpty(Stack *s) {
    return s->top == NULL;
}

// 入栈
void push(Stack *s, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(EXIT_FLURE);
    }
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
}

// 出栈
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("栈为空，无法出栈\n");
        exit(EXIT_FLURE);
    }
    Node *temp = s->top;
    int value = temp->data;
    s->top = temp->next;
    free(temp);
    return value;
}

// 查看栈顶元素
int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("栈为空，无法查看栈顶元素\n");
        exit(EXIT_FLURE);
    }
    return s->top->data;
}

int main() {
    Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    printf("栈顶元素: %d\n", peek(&s));

    printf("出栈元素: %d\n", pop(&s));
    printf("出栈元素: %d\n", pop(&s));

    printf("栈顶元素: %d\n", peek(&s));

    return 0;
}

1.3 栈的应用

栈在计算机科学中有广泛的应用，例如：

• 函数调用：每次函数调用时，系统会将返回地址、局部变量等信息压入栈中，函数返回时再将这些信息弹出。
• 表达式求值：栈可以用于中缀表达式到后缀表达式的转换，以及后缀表达式的求值。
• 括号匹配：栈可以用于检查表达式中的括号是否匹配。

2. 队列（Queue）

2.1 队列的基本概念

队列是一种遵循先进先出（FIFO, First In First Out）原则的线性数据结构。这意味着最先进入队列的元素将最先被移除。队列的操作主要包括：

• Enqueue（入队）：将元素添加到队列的尾部。
• Dequeue（出队）：移除并返回队列头部的元素。
• Peek（查看队头元素）：返回队列头部的元素但不移除它。
• IsEmpty（判断队列是否为空）：检查队列是否为空。

2.2 队列的实现

在C语言中，队列可以通过数组或链表来实现。下面我们将分别介绍这两种实现方式。

2.2.1 使用数组实现队列

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

// 判断队列是否为空
bool isEmpty(Queue *q) {
    return q->front == -1 && q->rear == -1;
}

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

// 入队
void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("队列已满，无法入队\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->data[q->rear] = value;
}

// 出队
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("队列为空，无法出队\n");
        exit(EXIT_FLURE);
    }
    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 peek(Queue *q) {
    if (isEmpty(q)) {
        printf("队列为空，无法查看队头元素\n");
        exit(EXIT_FLURE);
    }
    return q->data[q->front];
}

int main() {
    Queue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("队头元素: %d\n", peek(&q));

    printf("出队元素: %d\n", dequeue(&q));
    printf("出队元素: %d\n", dequeue(&q));

    printf("队头元素: %d\n", peek(&q));

    return 0;
}

2.2.2 使用链表实现队列

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *front;
    Node *rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = NULL;
    q->rear = NULL;
}

// 判断队列是否为空
bool isEmpty(Queue *q) {
    return q->front == NULL;
}

// 入队
void enqueue(Queue *q, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(EXIT_FLURE);
    }
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 出队
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("队列为空，无法出队\n");
        exit(EXIT_FLURE);
    }
    Node *temp = q->front;
    int value = temp->data;
    q->front = temp->next;

    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp);
    return value;
}

// 查看队头元素
int peek(Queue *q) {
    if (isEmpty(q)) {
        printf("队列为空，无法查看队头元素\n");
        exit(EXIT_FLURE);
    }
    return q->front->data;
}

int main() {
    Queue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("队头元素: %d\n", peek(&q));

    printf("出队元素: %d\n", dequeue(&q));
    printf("出队元素: %d\n", dequeue(&q));

    printf("队头元素: %d\n", peek(&q));

    return 0;
}

2.3 队列的应用

队列在计算机科学中也有广泛的应用，例如：

• 任务调度：操作系统使用队列来管理进程的调度，确保先进入队列的任务先被执行。
• 缓冲区：队列可以用于实现缓冲区，如打印任务队列、网络数据包队列等。
• 广度优先搜索（BFS）：在图算法中，队列用于实现广度优先搜索。

3. 栈与队列的比较

栈和队列虽然都是线性数据结构，但它们的操作方式和应用场景有所不同：

• 操作方式：

  • 栈遵循后进先出（LIFO）原则，只能在一端（栈顶）进行插入和删除操作。
  • 队列遵循先进先出（FIFO）原则，插入操作在队尾进行，删除操作在队头进行。

• 应用场景：

  • 栈适用于需要回溯的场景，如函数调用、表达式求值、括号匹配等。
  • 队列适用于需要按顺序处理的场景，如任务调度、缓冲区管理等。

4. 总结

栈和队列是计算机科学中最基本的数据结构之一，理解它们的实现原理和应用场景对于编写高效的程序至关重要。本文通过C语言代码示例详细介绍了如何使用数组和链表实现栈和队列，并探讨了它们的应用场景。希望本文能帮助读者更好地理解和掌握这两种数据结构。