1. Toy模板网首页
  2. > Toy博客

【C语言】数据结构——栈和队列实例探究

10月前 作者：流浪者与猴 分类：Toy博客 阅读(45) 违法举报

这篇具有很好参考价值的文章主要介绍了【C语言】数据结构——栈和队列实例探究。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

💗个人主页💗
⭐个人专栏——数据结构学习⭐
💫点击关注🤩一起学习C语言💯💫

导读：

我们在前面学习了单链表和顺序表，今天我们来学习栈和队列。
栈和队列相对于单链表和顺序表来说是较为简单的，之后我们再深入学习双链表。关注博主或是订阅专栏，掌握第一消息。

一、 栈

1. 栈的概念及结构

栈(Stack)是一种只能在一端进行插入和删除操作的线性数据结构，该端被称为栈顶(Top)，另一端被称为栈底(Bottom)。
栈的特点是后进先出(Last In First Out, LIFO)，即最后放入栈中的元素最先被弹出。栈中的元素可以是任意类型，但栈顶永远只能是一个元素。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

【C语言】数据结构——栈和队列实例探究,数据结构学习,c语言,数据结构
【C语言】数据结构——栈和队列实例探究,数据结构学习,c语言,数据结构

2. 栈的实现

栈可以用数组或链表来实现，常见应用场景包括函数调用、表达式求值、括号匹配、逆序输出等。

相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。
【C语言】数据结构——栈和队列实例探究,数据结构学习,c语言,数据结构

其基本操作包括：

push(x): 将元素x压入栈顶。
pop(): 弹出栈顶元素并返回其值。
top(): 返回栈顶元素的值，但不弹出。
empty():判断栈是否为空。

3. 实现代码

我们需要创建两个 C文件: study.c 和 Stack.c，以及一个 头文件： Stack.h。

头文件来声明函数，一个C文件来定义函数，另外一个C文件来用于主函数main（）进行测试。

3.1 定义结构体

typedef是类型定义的意思。typedef struct 是为了使用这个结构体方便。

若struct Stack {}这样来定义结构体的话。在申请Stack 的变量时，需要这样写，struct Stack n;
若用typedef，可以这样写，typedef struct Stack{}ST; 。在申请变量时就可以这样写，ST n;
区别就在于使用时，是否可以省去struct这个关键字。

Stack.h

typedef struct Stack
{
	STDataType* a;
	int top;		//标识栈顶的位置
	int capacity;
}ST;

3.2 初始化栈

Stack.h 声明函数

// 初始化栈 
void STInit(ST* pst);

Stack.c 定义函数

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

3.3 销毁栈

动态内存空间开辟，使用完之后需要进行销毁。
Stack.h 声明函数

// 销毁
void STDestroy(ST* pst);

Stack.c 定义函数

void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = 0;
}

3.4 入栈

我们在顺序表和单向链表里，都另定义一个函数来进行空间的开辟，这样我们在其它的函数中有开辟空间的需要只用调用即可，而无需再去写一次开辟空间的代码。但是在栈中我们只有在入栈的函数中需要进行空间的开辟，所有不用再单独写一个函数。
Stack.h 声明函数

// 入栈 
void STPush(ST* pst, STDataType x);

Stack.c 定义函数


void STPush(ST* pst, STDataType x)
{
	assert(pst);
	// 检查空间，如果满了，进行增容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		//如果开辟成功则重新赋给原来的数组指针
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//栈顶从0开始，可以作为数组的下标来进行插入数据
	pst->a[pst->top] = x;
	pst->top++;
}

3.5 出栈

后进先出原则，最后进来的数据先出。
Stack.h 声明函数

// 出栈 
void STPop(ST* pst);

Stack.c 定义函数

// 出栈 
void STPop(ST* pst)
{
	assert(pst);
	//top大于0，栈里面有数据才能删除数据
	assert(pst->top > 0);
	//直接让top--，不让访问即可
	pst->top--;
}

【C语言】数据结构——栈和队列实例探究,数据结构学习,c语言,数据结构

3.6 获取栈顶元素

栈并不能像打印数组那样把数据全部打印出来，只能获取到栈顶的元素，想要获取其它数据就只能先把其它的数据给删除，也就是出栈。
Stack.h 声明函数

// 获取栈顶元素 
STDataType STTop(ST* pst);

Stack.c 定义函数

// 获取栈顶元素 
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	//top-1即是栈顶元素
	return pst->a[pst->top - 1];
}

3.7 检测栈是否为空

Stack.h 声明函数

// 检测栈是否为空，如果为空返回true，如果不为空返回false 
bool STEmpty(ST* pst);

Stack.c 定义函数

// 检测栈是否为空，如果为空返回true，如果不为空返回false 
bool STEmpty(ST* pst)
{
	assert(pst);
	//如果表达式成立则为真
	return pst->top == 0;
}

3.8 获取栈中有效元素个数

Stack.h 声明函数

// 获取栈中有效元素个数 
int STSize(ST* pst);

Stack.c 定义函数

//获取栈中有效元素个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

4. 代码整理

4.1 Stack.h 

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;		//标识栈顶的位置
	int capacity;
}ST;

// 初始化栈 
void STInit(ST* pst);

// 销毁
void STDestroy(ST* pst);

// 入栈 
void STPush(ST* pst, STDataType x);

// 出栈 
void STPop(ST* pst);

// 获取栈顶元素 
STDataType STTop(ST* pst);

// 检测栈是否为空，如果为空返回true，如果不为空返回false 
bool STEmpty(ST* pst);

// 获取栈中有效元素个数 
int STSize(ST* pst);

4.2 Stack.c

#include "Stack.h"

//初始化栈
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

// 销毁栈
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = 0;
}

// 入栈 
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	// 检查空间，如果满了，进行增容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		//如果开辟成功则重新赋给原来的数组指针
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//栈顶从0开始，可以作为数组的下标来进行插入数据
	pst->a[pst->top] = x;
	pst->top++;
}

// 出栈 
void STPop(ST* pst)
{
	assert(pst);
	//top大于0，栈里面有数据才能删除数据
	assert(pst->top > 0);
	//直接让top--，有效数据减一即可
	pst->top--;
}

// 获取栈顶元素 
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	//top-1即是栈顶元素
	return pst->a[pst->top - 1];
}

// 检测栈是否为空，如果为空返回true，如果不为空返回false 
bool STEmpty(ST* pst)
{
	assert(pst);
	//如果表达式成立则为真
	return pst->top == 0;
}

//获取栈中有效元素个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

4.3 study.c

#include "Stack.h"

void TestST1()
{
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);
	printf("%d\n", STTop(&s));

	//一     对   多
	//入栈顺序 -- 出栈顺序
	while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}
	printf("\n");
	STDestroy(&s);
}
int main()
{
	TestST1();
	return 0;
}

二、队列

1. 队列的概念及结构

队列是一种线性的数据结构，它可以存储一系列数据，其中第一个添加的数据会被第一个删除，也就是先进先出（FIFO）的原则。

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

2. 队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

队列通常有两个指针，一个是front指针，指向队列的第一个元素，另一个是rear指针，指向队列的最后一个元素。当一个新元素进入队列时，它被插入到rear指针所指向的位置，当一个元素从队列中删除时，它会从front指针所指向的位置被删除。

【C语言】数据结构——栈和队列实例探究,数据结构学习,c语言,数据结构

3. 实现代码

我们需要创建两个 C文件: study.c 和 Queue.c，以及一个 头文件： Queue.h。

头文件来声明函数，一个C文件来定义函数，另外一个C文件来用于主函数main（）进行测试。

3.1 定义结构体

定义了一个链式队列的数据结构。
包含了两个结构体：

  1. QNode结构体表示队列中的一个节点，包含一个整数数据成员val和指向下一个节点的指针next。

  2. Queue结构体表示一个队列，包含指向队头和队尾节点的指针phead和ptail，以及队列的大小size。

这个队列是通过链式结构实现的，即每个节点都包含一个指向下一个节点的指针。队列的头指针phead指向队列的第一个节点，而队列的尾指针ptail指向队列的最后一个节点。
链式队列的优点是可以动态地增加和减少队列的大小，而不需要像顺序队列那样预留一定的空间。缺点是每个节点都需要额外的指针空间来指向下一个节点，因此相对于顺序队列会占用更多的存储空间。

Queue.h

// 链式结构：表示队列 
typedef int QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

3.2 初始化队列

Queue.h

// 初始化队列 
void QueueInit(Queue* pq);

Queue.c

void QueueInit(Queue* pq)
{
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

3.3 销毁队列

Queue.h

// 销毁队列 
void QueueDestroy(Queue* pq);

Queue.c

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead->next;
	while (cur)
	{
		free(pq->phead);
		pq->phead = cur;
		cur = cur->next;
	}
	cur = NULL;
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

3.4 队尾入队列

Queue.h

// 队尾入队列 
void QueuePush(Queue* pq, QDataType x);

Queue.c

void QueuePush(Queue* pq, QDataType x)
{
	//开辟新空间
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

3.5 队头出队列

Queue.h

// 队头出队列
void QueuePop(Queue* pq);

Queue.c

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	QNode* tmp = pq->phead;
	pq->phead = pq->phead->next;
	free(tmp);
	tmp = NULL;
	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
	}
	pq->size--;
}

3. 6 获取队列头部元素

Queue.h

// 获取队列头部元素 
QDataType QueueFront(Queue* pq);

Queue.c

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}

3.7 获取队列队尾元素

Queue.h

// 获取队列队尾元素
QDataType QueueBack(Queue* pq);

Queue.c

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}

3.8 检测队列是否为空

Queue.h

// 检测队列是否为空，如果为空返回true，如果非空返回false 
bool QueueEmpty(Queue* pq);

Queue.c

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

3.9 获取队列中有效元素个数

Queue.h

// 获取队列中有效元素个数 
int QueueSize(Queue* pq);

Queue.c文章来源地址https://www.toymoban.com/news/detail-752591.html

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

4. 代码整理

4.1 Queue.h 

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

// 链式结构：表示队列 
typedef int QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

// 初始化队列 
void QueueInit(Queue* pq);

// 销毁队列 
void QueueDestroy(Queue* pq);

// 队尾入队列 
void QueuePush(Queue* pq, QDataType x);

// 队头出队列
void QueuePop(Queue* pq);

// 获取队列头部元素 
QDataType QueueFront(Queue* pq);

// 获取队列队尾元素
QDataType QueueBack(Queue* pq);

// 检测队列是否为空，如果为空返回true，如果非空返回false 
bool QueueEmpty(Queue* pq);

// 获取队列中有效元素个数 
int QueueSize(Queue* pq);

4.2 Queue.c

#include "Queue.h"

// 初始化队列 
void QueueInit(Queue* pq)
{
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

// 销毁队列 
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead->next;
	while (cur)
	{
		free(pq->phead);
		pq->phead = cur;
		cur = cur->next;
	}
	cur = NULL;
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

// 队尾入队列 
void QueuePush(Queue* pq, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

// 队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	QNode* tmp = pq->phead;
	pq->phead = pq->phead->next;
	free(tmp);
	tmp = NULL;
	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
	}
	pq->size--;
}

// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}

// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}

// 检测队列是否为空，如果为空返回true，如果非空返回false 
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

4.3 study.c

#include "Queue.h"

void TestQ1()
{
	Queue s;
	QueueInit(&s);
	QueuePush(&s, 1);
	QueuePush(&s, 2);
	QueuePush(&s, 3);
	QueuePush(&s, 4);
	QueuePush(&s, 5);
	printf("%d ", QueueFront(&s));
	printf("%d ", QueueBack(&s));
	printf("%d\n", QueueSize(&s));
	QueuePop(&s);
	QueuePop(&s);
	printf("%d ", QueueFront(&s));
	printf("%d\n", QueueSize(&s));
	if (!QueueEmpty(&s))
	{
		QueuePop(&s);
		printf("%d ", QueueFront(&s));
		printf("%d\n", QueueSize(&s));
	}
	QueueDestroy(&s);
	printf("%d\n", QueueSize(&s));

}
int main()
{
	TestQ1();
	return 0;
}

到了这里，关于【C语言】数据结构——栈和队列实例探究的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【C语言】数据结构——带头双链表实例探究

    【C语言】数据结构——带头双链表实例探究

    💗个人主页💗 ⭐个人专栏——数据结构学习⭐ 💫点击关注🤩一起学习C语言💯💫 我们在前面学习了单链表和顺序表。 今天我们来学习双向循环链表。 在经过前面的一系列学习，我们已经掌握很多知识，相信今天的内容也是很容易理解的。 关注博主或是订阅专栏，掌握第

    2024年02月03日
    浏览(45)
  • 【C语言】数据结构——链式二叉树实例探究

    【C语言】数据结构——链式二叉树实例探究

    💗个人主页💗 ⭐个人专栏——数据结构学习⭐ 💫点击关注🤩一起学习C语言💯💫 我们在前面学习了单链表，顺序表，栈和队列，小堆。 今天我们来学习链式二叉树 关注博主或是订阅专栏，掌握第一消息。 链式二叉树（Linked Binary Tree）是一种基于链表实现的二叉树结构。

    2024年02月04日
    浏览(40)
  • 【数据结构】—手把手带你用C语言实现栈和队列（超详细！）

    【数据结构】—手把手带你用C语言实现栈和队列（超详细！）

                                       食用指南：本文在有C基础的情况下食用更佳                                     🔥 这就不得不推荐此专栏了：C语言                                   ♈️ 今日夜电波：Tell me —milet                    

    2024年02月14日
    浏览(118)

  • 数据结构（C语言实现）——栈和队列的介绍及基本操作的实现（动态顺序栈+链队）

    今天我们来学习另外两个线性结构——栈和队列，栈和队列是操作受限的线性表，因此，可称为限定性的数据结构。 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守

    2023年04月19日
    浏览(44)
  • 【数据结构】栈和队列(队列篇）

    【数据结构】栈和队列(队列篇）

    上期我们已经学习了数据结构中的栈，这期我们开始学习队列。 目录 1.队列的概念及结构 2.队列的实现 队列结构体定义 常用接口函数 初始化队列 队尾入队列 队头出队列 获取队列头部元素、 获取队列队尾元素 获取队列中有效元素个数 检测队列是否为空 销毁队列 3.循环队

    2024年02月13日
    浏览(42)
  • 栈和队列【数据结构】

    栈和队列【数据结构】

    2024年02月16日
    浏览(45)
  • [数据结构】栈和队列

    [数据结构】栈和队列

    目录 1.栈 1.1概念 1.2 栈的使用 1.3.栈的模拟实现 2.队列 2.1概念 2.2队列的使用 2.3队列的模拟实现 2.4 循环队列 2.5双端队列   栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素

    2024年02月07日
    浏览(42)
  • 数据结构：栈和队列

    数据结构：栈和队列

    朋友们、伙计们，我们又见面了，本期来给大家解读一下栈和队列方面的相关知识点，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！ C 语 言 专 栏：C语言：从入门到精通 数据结构专栏：数据结构 个 人 主 页 ：  stackY、 目录 前言：  1.栈 1.1栈的

    2024年02月06日
    浏览(43)
  • 数据结构【栈和队列】

    数据结构【栈和队列】

    一、栈 1.定义：只允许一端进行插入和删除的线性表，结构与手枪的弹夹差不多，可以作为实现递归函数（调用和返回都是后进先出）调用的一种数据结构； 栈顶：允许插入删除的那端； 栈底：固定的，不允许插入或删除； 空栈：不含元素； 2.特点：后进先出； 3.操作：入

    2024年02月15日
    浏览(49)
  • 数据结构 | 栈和队列

    数据结构 | 栈和队列

    … 📘📖📃本文已收录至：数据结构 | C语言 更多知识尽在此专栏中! 栈（Stack） 又名堆栈，它是一种运算受限的线性表，限定仅在表尾进行插入和删除操作的线性表。 队列（Queue） 也是一种特殊的线性表，特殊之处在于它只允许在表的前端（Front）进行删除操作，而在表的

    2024年01月23日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包