栈和队列实现：C语言中栈与队列数据结构详解

# 1. 栈与队列数据结构概述

栈（Stack）和队列（Queue）是常用的数据结构，在计算机科学中有着重要的应用。它们都是线性数据结构，但在元素访问的方式上有明显的区别。

## 1.1 栈的定义与特性

栈是一种后进先出（Last In First Out, LIFO）的数据结构。栈具有两个主要操作：压入（Push）和弹出（Pop）。压入操作将元素添加到栈的顶部，而弹出操作则将顶部元素移除并返回。除了压入和弹出，栈还支持查看栈顶元素（Top）以及判断栈是否为空等操作。

## 1.2 队列的定义与特性

队列是一种先进先出（First In First Out, FIFO）的数据结构。队列有两个主要操作：入队（Enqueue）和出队（Dequeue）。入队操作在队列的末尾添加新元素，而出队操作则从队列头部移除元素并返回。队列还支持查看队头元素（Front）和队尾元素（Rear）等操作。

## 1.3 栈与队列的应用场景

栈和队列在计算机领域有广泛的应用，其中栈常用于处理函数调用、表达式求值、括号匹配等场景；队列常用于实现缓冲区、任务调度、广度优先搜索等应用中。它们可以帮助我们解决各种实际问题，提高程序效率和可靠性。

# 2. C语言中的栈数据结构

栈（Stack）是一种特殊的线性表，具有“先进后出”（FILO，First In Last Out）的特点。在C语言中，可以使用数组或链表来实现栈数据结构。栈常用于实现函数调用、表达式求值、内存管理等场景。

### 2.1 栈的基本实现原理

在C语言中，可以使用数组或链表来表示栈。数组实现的栈通常需要指定一个固定的容量，而链表实现的栈可以动态地分配内存空间。栈的基本操作包括入栈（push）和出栈（pop），以及获取栈顶元素（peek）等。

// 以数组实现的栈
#define MAX_SIZE 100

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

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

int isEmpty(Stack *stack) {
    return stack->top == -1 ? 1 : 0;
}

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

int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return -1;
    } else {
        int value = stack->data[stack->top];
        stack->top--;
        return value;
    }
}

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

### 2.2 栈的操作及相关函数

上述代码中，initStack用于初始化栈，isEmpty用于判断栈是否为空，push用于入栈，pop用于出栈，peek用于获取栈顶元素。这些操作是栈的基本功能，可以通过这些函数实现栈的各种操作。

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

    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);

    printf("Top element: %d\n", peek(&stack));  // 输出：Top element: 3

    printf("Pop element: %d\n", pop(&stack));  // 输出：Pop element: 3
    printf("Pop element: %d\n", pop(&stack));  // 输出：Pop element: 2
    printf("Pop element: %d\n", pop(&stack));  // 输出：Pop element: 1

    printf("Is stack empty? %s\n", isEmpty(&stack) ? "Yes" : "No");  // 输出：Is stack empty? Yes

    return 0;
}

### 2.3 栈的应用实例

栈在C语言中有着广泛的应用，其中一个常见的应用是实现函数的递归调用。下面是一个简单的递归函数实例：

int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * f