C语言怎么实现栈和队列

发布时间：2022-04-24 10:47:58 作者：iii
来源：亿速云阅读：177

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语言代码示例详细介绍了如何使用数组和链表实现栈和队列，并探讨了它们的应用场景。希望本文能帮助读者更好地理解和掌握这两种数据结构。

C语言怎么实现栈和队列

C语言怎么实现栈和队列

1. 栈（Stack）

1.1 栈的基本概念

1.2 栈的实现

1.2.1 使用数组实现栈

1.2.2 使用链表实现栈

1.3 栈的应用

2. 队列（Queue）

2.1 队列的基本概念

2.2 队列的实现

2.2.1 使用数组实现队列

2.2.2 使用链表实现队列

2.3 队列的应用

3. 栈与队列的比较

4. 总结

相关阅读