C语言栈和队列如何实现

在C语言中，栈（Stack）和队列（Queue）是两种常用的数据结构，它们分别遵循“后进先出”（LIFO）和“先进先出”（FIFO）的原则。本文将介绍如何在C语言中实现栈和队列。

栈的实现

栈是一种线性数据结构，只允许在一端进行插入和删除操作，这一端称为栈顶。栈的基本操作包括压栈（Push）和弹栈（Pop）。

栈的结构定义

首先，我们需要定义一个栈的结构体，包含栈的容量、栈顶指针和存储数据的数组。

#define MAX_SIZE 100

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

初始化栈

在操作栈之前，需要初始化栈，将栈顶指针设置为-1，表示栈为空。

void initStack(Stack *s) {
    s->top = -1;
}

压栈操作

压栈操作将元素添加到栈顶。首先需要检查栈是否已满，如果栈未满，则将元素添加到栈顶，并更新栈顶指针。

void push(Stack *s, int value) {
    if (s->top >= MAX_SIZE - 1) {
        printf("Stack Overflow\n");
        return;
    }
    s->data[++(s->top)] = value;
}

弹栈操作

弹栈操作从栈顶移除元素。首先需要检查栈是否为空，如果栈不为空，则返回栈顶元素，并更新栈顶指针。

int pop(Stack *s) {
    if (s->top < 0) {
        printf("Stack Underflow\n");
        return -1;
    }
    return s->data[(s->top)--];
}

查看栈顶元素

查看栈顶元素操作返回栈顶元素，但不移除它。

int peek(Stack *s) {
    if (s->top < 0) {
        printf("Stack is empty\n");
        return -1;
    }
    return s->data[s->top];
}

队列的实现

队列是一种线性数据结构，允许在一端（队尾）进行插入操作，在另一端（队头）进行删除操作。队列的基本操作包括入队（Enqueue）和出队（Dequeue）。

队列的结构定义

首先，我们需要定义一个队列的结构体，包含队列的容量、队头指针、队尾指针和存储数据的数组。

#define MAX_SIZE 100

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

初始化队列

在操作队列之前，需要初始化队列，将队头指针和队尾指针都设置为0。

void initQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

入队操作

入队操作将元素添加到队尾。首先需要检查队列是否已满，如果队列未满，则将元素添加到队尾，并更新队尾指针。

void enqueue(Queue *q, int value) {
    if ((q->rear + 1) % MAX_SIZE == q->front) {
        printf("Queue is full\n");
        return;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
}

出队操作

出队操作从队头移除元素。首先需要检查队列是否为空，如果队列不为空，则返回队头元素，并更新队头指针。

int dequeue(Queue *q) {
    if (q->front == q->rear) {
        printf("Queue is empty\n");
        return -1;
    }
    int value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return value;
}

查看队头元素

查看队头元素操作返回队头元素，但不移除它。

int peekQueue(Queue *q) {
    if (q->front == q->rear) {
        printf("Queue is empty\n");
        return -1;
    }
    return q->data[q->front];
}

总结

本文介绍了如何在C语言中实现栈和队列这两种基本的数据结构。栈和队列在算法和程序设计中有着广泛的应用，理解它们的实现原理对于编写高效的程序至关重要。通过本文的示例代码，读者可以掌握栈和队列的基本操作，并能够在实际编程中灵活运用。