【数据结构 C 语言实现】栈和队列

ops/2025/2/10 20:47:47/

目录

  • 栈和队列
    • 1 栈
      • 1.1 栈的结构体定义
      • 1.2 基本功能实现
        • 1.2.1 创建栈
        • 1.2.2 销毁栈
        • 1.2.3 入栈
        • 1.2.4 出栈
        • 1.2.5 判断栈是否为空
        • 1.2.6 获取栈顶元素（不弹出）
        • 1.2.7 获取栈的当前大小
      • 1.3 代码实现
    • 2 队列
      • 2.1 循环队列的结构体定义
      • 2.2 基本功能实现
        • 2.2.1 创建循环队列
        • 2.2.2 销毁循环队列
        • 2.2.3 入队
        • 2.2.4 出队
        • 2.2.5 判断队列是否为空
        • 2.2.6 获取队头元素（不删除）
        • 2.2.7 获取队列的当前大小
      • 2.3 代码实现
    • 3 总结

栈和队列

1 栈

1.1 栈的结构体定义

typedef struct {ElemType *data;int top; int capacity;
} Stack;

data：指向动态数组的指针，用于存储栈中的元素。
top：栈顶指针，表示当前栈中元素的数量，同时也指向下一个入栈的位置。
capacity：栈的当前容量，当栈满时会动态扩容。

1.2 基本功能实现

1.2.1 创建栈
Stack *create_stack(int size) {Stack *stk = (Stack *)malloc(sizeof(Stack));stk->capacity = size;stk->top = 0;stk->data = (ElemType *)malloc(stk->capacity * sizeof(ElemType));return stk;
}

功能：初始化一个栈，分配指定大小的内存空间。
参数：size 表示栈的初始容量。
返回值：指向新创建的栈的指针。

1.2.2 销毁栈
void destroy_stack(Stack *stk) {if (stk) {free(stk->data);  // 释放动态数组free(stk);        // 释放栈结构体stk = NULL;       // 将指针置为 NULL，避免野指针}
}

功能：释放栈占用的内存，防止内存泄漏。
注意：在释放内存后，将栈指针置为 NULL，避免野指针问题。

1.2.3 入栈
void push(Stack *stk, ElemType b) {if (stk->top >= stk->capacity) {// 栈满扩展容量stk->capacity <<= 1;  // 容量翻倍stk->data = (ElemType *)realloc(stk->data, stk->capacity * sizeof(ElemType));}stk->data[stk->top++] = b;  // 将元素放入栈顶，并更新栈顶指针
}

功能：将元素压入栈顶。
动态扩容：当栈满时，容量翻倍，并通过 realloc 重新分配内存。

1.2.4 出栈
ElemType pop(Stack *stk) {if (stk->top <= 0) {return ERROR;  // 栈为空时返回错误值}return stk->data[--stk->top];  // 返回栈顶元素，并更新栈顶指针
}

功能：弹出栈顶元素。
返回值：栈顶元素；如果栈为空，返回预定义的错误值 ERROR。

1.2.5 判断栈是否为空
int is_empty(Stack *stk) {return stk->top == 0;
}

功能：判断栈是否为空。
返回值：如果栈为空，返回 1；否则返回 0。

1.2.6 获取栈顶元素（不弹出）
ElemType peek(Stack *stk) {if (stk->top <= 0) {return ERROR;  // 栈为空时返回错误值}return stk->data[stk->top - 1];  // 返回栈顶元素
}

功能：获取栈顶元素，但不弹出。
返回值：栈顶元素；如果栈为空，返回预定义的错误值 ERROR。

1.2.7 获取栈的当前大小
int get_stack_size(Stack *stk) {return stk->top;
}

功能：获取栈中当前元素的数量。
返回值：栈的大小。

1.3 代码实现

注意，代码省略了头文件和主函数，只包含和栈相关的代码，其中 ERROR 是需要用户自定义的错误值，其类型由 ElemType 决定，这里只是示例，将 ElemType 设为 int。

#define ERROR -114514
typedef int ElemType;typedef struct {ElemType *data;int top;int capacity;
} Stack;// 创建栈
Stack *create_stack(int size) {Stack *stk = (Stack *)malloc(sizeof(Stack));// 注意这里并没有添加内存分配失败的处理stk->capacity = size;stk->top = 0;stk->data = (ElemType *)malloc(stk->capacity * sizeof(ElemType));return stk;
}// 销毁栈
void destroy_stack(Stack *stk) {if (stk) {free(stk->data);free(stk);stk = NULL;}
}// 入栈
void push(Stack *stk, ElemType b) {if (stk->top >= stk->capacity) {// 栈满扩展容量，这里并没有考虑整数溢出stk->capacity <<= 1;// 注意这里并没有添加内存分配失败的处理stk->data = (ElemType *)realloc(stk->data, stk->capacity * sizeof(ElemType));}stk->data[stk->top++] = b;
}// 出栈
ElemType pop(Stack *stk) {if (stk->top <= 0) {return ERROR;}return stk->data[--stk->top];
}// 判断栈是否为空
int is_empty(Stack *stk) { return stk->top == 0; }// 获取栈顶元素（不弹出）
ElemType peek(Stack *stk) {if (stk->top <= 0) {return ERROR;}return stk->data[stk->top - 1];
}// 获取栈的当前大小
int get_stack_size(Stack *stk) { return stk->top; }

2 队列

这里实现一个循环队列

2.1 循环队列的结构体定义

typedef struct {ElemType *data;int front;int rear;int capacity;
} CircularQueue;

data：指向动态数组的指针，用于存储队列中的元素。
front：队头指针，指向队列的第一个元素。
rear：队尾指针，指向队列的最后一个元素的下一个位置。
capacity：队列的当前容量，队列的实际可用容量为 capacity - 1，因为需要区分队列满和队列空的情况。

2.2 基本功能实现

2.2.1 创建循环队列
CircularQueue *create_circular_queue(int size) {CircularQueue *queue = (CircularQueue *)malloc(sizeof(CircularQueue));queue->capacity = size + 1;  // 多分配一个空间用于区分队列满和队列空queue->front = 0;queue->rear = 0;queue->data = (ElemType *)malloc(queue->capacity * sizeof(ElemType));return queue;
}

功能：初始化一个循环队列，分配指定大小的内存空间。
参数：size 表示队列的初始容量。
返回值：指向新创建的循环队列的指针。

2.2.2 销毁循环队列
void destroy_circular_queue(CircularQueue *queue) {if (queue) {free(queue->data);  // 释放动态数组free(queue);        // 释放队列结构体queue = NULL;       // 将指针置为 NULL，避免野指针}
}

功能：释放循环队列占用的内存，防止内存泄漏。
注意：在释放内存后，将队列指针置为 NULL，避免野指针问题。

2.2.3 入队
void enqueue(CircularQueue *queue, ElemType b) {if ((queue->rear + 1) % queue->capacity == queue->front) {// 队列满，扩展容量int new_capacity = queue->capacity * 2;ElemType *new_data = (ElemType *)malloc(new_capacity * sizeof(ElemType));int i = 0;while (queue->front != queue->rear) {new_data[i++] = queue->data[queue->front];queue->front = (queue->front + 1) % queue->capacity;}free(queue->data);queue->data = new_data;queue->front = 0;queue->rear = i;queue->capacity = new_capacity;}queue->data[queue->rear] = b;queue->rear = (queue->rear + 1) % queue->capacity;
}

功能：将元素插入队尾。
动态扩容：当队列满时，容量翻倍，并重新分配内存。

2.2.4 出队
ElemType dequeue(CircularQueue *queue) {if (queue->front == queue->rear) {return ERROR;  // 队列为空时返回错误值}ElemType elem = queue->data[queue->front];queue->front = (queue->front + 1) % queue->capacity;return elem;
}

功能：删除队头元素并返回。
返回值：队头元素；如果队列为空，返回预定义的错误值 ERROR。

2.2.5 判断队列是否为空
int is_empty(CircularQueue *queue) {return queue->front == queue->rear;
}

功能：判断队列是否为空。
返回值：如果队列为空，返回 1；否则返回 0。

2.2.6 获取队头元素（不删除）
ElemType peek_front(CircularQueue *queue) {if (queue->front == queue->rear) {return ERROR;  // 队列为空时返回错误值}return queue->data[queue->front];
}

功能：获取队头元素，但不删除。
返回值：队头元素；如果队列为空，返回预定义的错误值 ERROR。

2.2.7 获取队列的当前大小
int get_queue_size(CircularQueue *queue) {return (queue->rear - queue->front + queue->capacity) % queue->capacity;
}

功能：获取队列中当前元素的数量。
返回值：队列的大小。

2.3 代码实现

注意，代码省略了头文件和主函数，只包含和循环队列相关的代码，其中 ERROR 是需要用户自定义的错误值，其类型由 ElemType 决定，这里只是示例，将 ElemType 设为 int。

#define ERROR -114514
typedef int ElemType;typedef struct {ElemType *data;int front;int rear;int capacity;
} CircularQueue;// 创建循环队列
CircularQueue *create_circular_queue(int size) {CircularQueue *queue = (CircularQueue *)malloc(sizeof(CircularQueue));queue->capacity = size + 1;  // 多分配一个空间用于区分队列满和队列空queue->front = 0;queue->rear = 0;queue->data = (ElemType *)malloc(queue->capacity * sizeof(ElemType));return queue;
}// 销毁循环队列
void destroy_circular_queue(CircularQueue *queue) {if (queue) {free(queue->data);free(queue);queue = NULL;}
}// 入队
void enqueue(CircularQueue *queue, ElemType b) {if ((queue->rear + 1) % queue->capacity == queue->front) {// 队列满，扩展容量int new_capacity = queue->capacity * 2;ElemType *new_data = (ElemType *)malloc(new_capacity * sizeof(ElemType));int i = 0;while (queue->front != queue->rear) {new_data[i++] = queue->data[queue->front];queue->front = (queue->front + 1) % queue->capacity;}free(queue->data);queue->data = new_data;queue->front = 0;queue->rear = i;queue->capacity = new_capacity;}queue->data[queue->rear] = b;queue->rear = (queue->rear + 1) % queue->capacity;
}// 出队
ElemType dequeue(CircularQueue *queue) {if (queue->front == queue->rear) {return ERROR;  // 队列为空时返回错误值}ElemType elem = queue->data[queue->front];queue->front = (queue->front + 1) % queue->capacity;return elem;
}// 判断队列是否为空
int is_empty(CircularQueue *queue) {return queue->front == queue->rear;
}// 获取队头元素（不删除）
ElemType peek_front(CircularQueue *queue) {if (queue->front == queue->rear) {return ERROR;  // 队列为空时返回错误值}return queue->data[queue->front];
}// 获取队列的当前大小
int get_queue_size(CircularQueue *queue) {return (queue->rear - queue->front + queue->capacity) % queue->capacity;
}

3 总结

实际上，如果是算法题用纯 C 语言的话，根本不需要将这些数据结构提出来封装，都是直接使用数组在逻辑上模拟的而且谁在做题的时候用纯 C 语言啊。以上作为使用 C 语言实现栈和队列的参考。


http://www.ppmy.cn/ops/157353.html

相关文章

视觉硬件选型和算法选择(CNN)

视觉硬件选型和算法选择(CNN)

基础知识 什么是机械视觉: 机械视觉是一种利用机器代替人眼来进行测量和判断的技术&#xff0c;通过光学系统、图像传感器等设备获取图像&#xff0c;并运用图像处理和分析算法来提取信息&#xff0c;以实现对目标物体的识别、检测、测量和定位等功能。 机械视觉与人类视觉有什…
阅读更多...
idea插件开发dom4j报错:SAXParser cannot be cast to class org.xml.sax.XMLReader

idea插件开发dom4j报错:SAXParser cannot be cast to class org.xml.sax.XMLReader

手打不易&#xff0c;如果转摘&#xff0c;请注明出处&#xff01; 注明原文&#xff1a;https://blog.csdn.net/q258523454/article/details/145512328 dom4j报错 idea插件使用到了dom4j依赖&#xff0c;但是报错&#xff1a; I will print the stack trace then carry on…
阅读更多...
软件测试之单元测试

软件测试之单元测试

&#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 一、什么是单元测试&#xff1f; 单元测试是指&#xff0c;对软件中的最小可测试单元在与程序其他部分相隔离的情况下进行检查和验证的工作&#xff0c;这里的最…
阅读更多...
Vue全流程--Vue2路由

Vue全流程--Vue2路由

引入路由的原因&#xff1a; 实现单页面应用&#xff08;SPA&#xff09; 什么是单页面应用&#xff1a; 1、点击跳转链接后直接在原本的页面展示。路径发生相应改变 2、整个应用只有一个完整页面 3、数据需要通过ajax获取 Vue2中的路由是什么&#xff1a; Vue2路由是一…
阅读更多...
IDEA中Resolving Maven dependencies卡着不动解决方案

IDEA中Resolving Maven dependencies卡着不动解决方案

一、修改settings.xml Maven配置阿里云仓库主要通过修改Maven的settings.xml文件来实现‌。以下是具体步骤： ‌1、找到settings.xml文件‌： 通常位于Maven安装目录下的conf文件夹中，或者在用户目录下的.m2文件夹中（如果用户自定义了settings.xml的位置）。 2、‌编辑se…
阅读更多...
体验 DeepSeek-R1：解密 1.5B、7B、8B 版本的强大性能与应用

体验 DeepSeek-R1：解密 1.5B、7B、8B 版本的强大性能与应用

文章目录 &#x1f34b;引言&#x1f34b;DeepSeek 模型简介&#x1f34b;版本更新&#xff1a;1.5B、7B、8B 的区别与特点&#x1f34b;模型评估&#x1f34b;体验 DeepSeek 的过程&#x1f34b;总结 &#x1f34b;引言 随着大规模语言模型的持续发展&#xff0c;许多模型在性…
阅读更多...
web第二次作业

web第二次作业

一.后台管理系统首页代码 1.html代码 <!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <title>实验&l…
阅读更多...
DNS域名服务器的安装及配置

DNS域名服务器的安装及配置

1.安装DNS域名服务器 sudo apt-get install bind9 2.安装完成后进入/etc/bind目录 cd /etc/bind 进入目录后修改named.conf.local文件 sudo vim named.conf.local 创建test.com文件 sudo touch test.com 修改test.com文件 sudo vim test.com 保存后启动bind9 # servic…
阅读更多...
最新文章

Copyright @ 2022~2023