C语言编程数据结构的栈和队列

什么是栈

栈（Stack） 是限定仅在表尾进行插入和删除操作的线性表。栈也称为后进先出（ Last In First Out）的线性表，简称 LIFO 结构。栈结构有两个最重要的操作：入栈和出栈。其中，入栈操作向栈中添加一个元素，出栈操作从栈中删除一个元素。

栈的基本操作

1. 初始化栈
2. 入栈
3. 出栈
4. 取栈顶元素
5. 判空
6. 判满

// 栈的结构体
typedef struct Stack {
    int top;
    int maxSize;
    int *data;
} Stack;

// 初始化栈
void initStack(Stack *stack, int size){
    stack->top = -1;
    stack->maxSize = size;
    stack->data = (int *)malloc(sizeof(int)*size);
}

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

// 出栈
int pop(Stack *stack){
    if(stack->top == -1){
        printf("栈已空，无法出栈！");
        return 0;
    }
    int value = stack->data[stack->top];
    stack->top--;
    return value;
}

// 取栈顶元素
int top(Stack *stack){
    if(stack->top == -1){
        printf("栈为空！");
        return 0;
    }
    return stack->data[stack->top];
}

// 判空
int isEmpty(Stack *stack){
    return stack->top==-1;
}

// 判满
int isFull(Stack *stack){
    return stack->top==stack->maxSize-1;
}

栈的应用

• 函数调用
• 表达式求值
• 四则运算转中缀表达式

什么是队列

队列（Queue）是限定仅在表的一端进行插入，而在另一端进行删除的线性表。队列也称为先进先出（ First In First Out）的线性表，简称 FIFO 结构。队列结构有两个最重要的操作：入队和出队。其中，入队操作向队列中添加一个元素，出队操作从队列中删除一个元素。

队列的基本操作

1. 初始化队列
2. 入队
3. 出队
4. 取队头元素
5. 判空
6. 判满

// 队列的结构体
typedef struct Queue {
    int front;  // 队头指针
    int rear;   // 队尾指针
    int maxSize;
    int *data;
} Queue;

// 初始化队列
void initQueue(Queue *queue, int size){
    queue->front = 0;
    queue->rear = -1;
    queue->maxSize = size;
    queue->data = (int *)malloc(sizeof(int)*size);
}

// 入队
void enqueue(Queue *queue, int value){
    if(queue->rear == queue->maxSize-1){
        printf("队列已满，无法入队！");
        return;
    }
    queue->rear++;
    queue->data[queue->rear] = value;
}

// 出队
int dequeue(Queue *queue){
    if(queue->front > queue->rear){
        printf("队列已空，无法出队！");
        return 0;
    }
    int value = queue->data[queue->front];
    queue->front++;
    return value;
}

// 取队头元素
int front(Queue *queue){
    if(queue->front > queue->rear){
        printf("队列为空！");
        return 0;
    }
    return queue->data[queue->front];
}

// 判空
int isEmpty(Queue *queue){
    return queue->front > queue->rear;
}

// 判满
int isFull(Queue *queue){
    return queue->rear==queue->maxSize-1;
}

队列的应用

• 广度优先搜索（BFS）
• 打印任务队列

示例

栈的示例

#include<stdio.h>
#include<stdlib.h>
#include"stack.h"

// 判断一个括号匹配表达式的正确性
int isBracketMatch(char *str){
    Stack stack;
    initStack(&stack, 50);
    int i = 0;
    while(str[i] != '\0'){
        if(str[i] == '('){
            push(&stack, '(');
        }else if(str[i] == ')'){
            if(isEmpty(&stack)){
                return 0;
            }else{
                pop(&stack);
            }
        }
        i++;
    }
    free(stack.data);
    return isEmpty(&stack);
}

// 测试函数
int main(){
    char *str = "()()((())))";
    int result = isBracketMatch(str);
    if(result){
        printf("括号匹配正确！");
    }else{
        printf("括号匹配不正确！");
    }
    return 0;
}

队列的示例

#include<stdio.h>
#include<stdlib.h>
#include"queue.h"

// 打印任务结构体
typedef struct Task {
    int id, priority;
} Task;

// 初始化任务队列
void initTaskQueue(Queue *queue){
    initQueue(queue, 50);
}

// 添加任务
void addTask(Queue *queue, Task task){
    enqueue(queue, task.id);
}

// 处理任务队列
void processTaskQueue(Queue *queue){
    while(!isEmpty(queue)){
        int taskId = dequeue(queue);
        printf("正在处理任务%d\n", taskId);
    }
}

// 测试函数
int main(){
    Queue queue;
    initTaskQueue(&queue);
    Task task1 = {1, 1};
    addTask(&queue, task1);
    Task task2 = {2, 2};
    addTask(&queue, task2);
    Task task3 = {3, 1};
    addTask(&queue, task3);
    Task task4 = {4, 3};
    addTask(&queue, task4);
    processTaskQueue(&queue);
    return 0;
}