C语言实现栈和队列(动态)

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

目录

一:栈

(1)什么是栈

(2)栈的两种实现方式

(3)栈的一些基本接口实现

【1】栈的结构体和初始化

【2】入栈

【3】销毁

【4】出栈

【5】判断栈是否为空

【6】取顶部数据

【7】取栈中有效数据的个数

【8】栈的全部代码

二:队列

(1)什么是队列

(2)队列的两种实现方式

(3)队列的一些基本接口实现

【1】队列的结构体和初始化

【2】入队列

【3】销毁队列

【4】判断队列是否为空

【5】出队列(删除数据)

【6】查找队列的头尾数据

【7】查找队列的结点个数

【8】队列的全部代码

三:小结


一:栈

(1)什么是栈

【1】栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底 栈中的数据元素 遵守后进先出 LIFO Last In First Out )的原则。
【2】压栈:栈的插入操作叫做进栈 / 压栈 / 入栈, 入数据在栈顶
【3】出栈:栈的删除操作叫做出栈。 出数据也在栈顶
图解:
C语言实现栈和队列(动态)

(2)栈的两种实现方式

链式栈:用链表的结构来实现栈。

顺序栈:数组的结构来实现栈。

优劣对比:

【1】单向链式结构的出栈入栈(删除插入)效率比较低,因为我们要先找到尾结点再行插入删除,可以通过双向链表或者将单向链表的头结点当作栈顶来处理。

【2】顺序栈只需要记录栈顶位置(同时也是有效元素个数)进行出栈入栈(尾插尾删)十分方便,而且不需要多余的空间存储地址

综上所述:在栈的实现中数组的结构实现更优一些因为数组在尾上插入数据的代价比较小。

(3)栈的一些基本接口实现

【1】栈的结构体和初始化

结构体:

C语言实现栈和队列(动态)

注:改变结构体的变量只需要传入结构体指针。

初始化:

 C语言实现栈和队列(动态)

【2】入栈

基础思路:

①根据有效数据个数(top)和最大容量来判断是否扩容

存储数据

有效数据个数和最大容量进行更新

图解:

C语言实现栈和队列(动态)

代码:

C语言实现栈和队列(动态)

【3】销毁

思路:销毁很简单,因为空间是连续的,注意把栈顶位置(top)和最大容量置0就行。

代码:

C语言实现栈和队列(动态)

【4】出栈

思路:

  ①栈顶其实是我们数组的尾,我们直接将top(有效数据个数)减一就行(数据失联)

  ②注意如果栈为空就不能在减了,不然会是top=-1,造成越界访问

代码:

C语言实现栈和队列(动态)

【5】判断栈是否为空

思路:根据top判断,为0就是空栈,返回true,否则返回false。(注意包头文件stdbool.h)

代码:

C语言实现栈和队列(动态)

【6】取顶部数据

思路:

 ①我们现在有有效数据个数,将它减一就得到顶部数据的下标,直接用下标访问,然后返回这个数据就行。

 ②栈为空不能用下标访问,不然会越界

代码:

C语言实现栈和队列(动态)

【7】取栈中有效数据的个数

思路:很简单,直接返回top就行。

代码:

C语言实现栈和队列(动态)

【8】栈的全部代码

stack.h(头文件)

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

//重定义数据类型,方便更改
typedef int STDataType;

typedef struct stack {
	//存储数据
	STDataType* a;
	//栈顶(位置)
	int top;
	//容量
	int capacity;
}ST;

//初始化
void StackInit(ST* ps);

//销毁
void StackDestroy(ST* ps);

//入栈
void StackPush(ST* ps, STDataType x);

//出栈(销毁)
void StackPop(ST* ps);

//取栈顶的数据
STDataType StackTop(ST* ps);

//取栈中的有效数据个数
int StackSize(ST* ps);

//判断栈是否为空
bool StackEmpty(ST* ps);

stack.c(接口实现)

#define _CRT_SECURE_NO_WARNINGS 1
#include "stack.h"

//初始化
void StackInit(ST* ps)
{
	//断言,不能传空指针进来
	assert(ps );
	//一开始指向NULL
	ps->a = NULL;
	//把栈顶和容量都置为空
	ps->top = ps->capacity = 0;
}

//销毁
void StackDestroy(ST* ps)
{
	//断言,不能传空指针进来
	assert(ps );
	//栈顶和容量置为空
	ps->top = ps->capacity = 0;
	//释放空间
	free(ps->a);
	ps->a = NULL;
}

//入栈
void StackPush(ST* ps, STDataType x)
{
	//断言,不能传空指针进来
	assert(ps);
	//先判断是否扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;
		//扩容
		STDataType* tmp = 
		(STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		//扩容失败
		if (tmp == NULL)
		{
			printf("realloc error\n");
			exit(-1);
		}
		//更新
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
	//存储数据
	ps->a[ps->top] = x;
	ps->top++;
}


//出栈(删除)
void StackPop(ST* ps)
{
	//断言,不能传空指针进来
	assert(ps);
	//如果栈为空,不能出栈
	assert(!StackEmpty(ps));
	ps->top--;
}

//取顶部数据
STDataType StackTop(ST* ps)
{
	//断言,不能传空指针进来
	assert(ps);
	//如果栈为空,不能进行访问
	assert(!StackEmpty(ps));
	//返回栈顶数据
	return ps->a[ps->top-1];
}

//取栈中的有效数据个数
int StackSize(ST* ps)
{
	//断言,不能传空指针进来
	assert(ps);
	//直接返回top
	return ps->top;
}

//判断栈是否为空
bool StackEmpty(ST* ps)
{
	//断言,不能传空指针进来
	assert(ps);
	//依据top来判断
	/*if (ps->top == 0)
		return true;
	return false;*/
	//更简洁的写法,一个判断语句的值要么为true,要么false
	return ps->top == 0;
}

text.c(测试,写接口最好写一测一)

#define _CRT_SECURE_NO_WARNINGS 1
#include "stack.h"

void text1()
{
	ST s1;
	StackInit(&s1);
	StackPush(&s1, 89);
	StackPush(&s1, 109);
	while (!StackEmpty(&s1))
	{
		printf("%d ", StackTop(&s1));
		//出栈
		StackPop(&s1);
	}
	//测试结束,及时释放空间
	StackDestroy(&s1);
}

void text2()
{
	ST s;
	StackInit(&s);
	StackPush(&s, 5);
	StackPush(&s, 48);
	StackPush(&s, 88);
	StackPush(&s, 85);
	int a = StackSize(&s);
	printf("%d\n", a);
	StackPop(&s);
	StackPop(&s);
	StackPop(&s);
	StackPop(&s);
	bool t=StackEmpty(&s);
	if (t)
		printf("为空\n");
	else
		printf("不为空\n");
	//测试结束,及时释放空间
	StackDestroy(&s);
}

int main()
{
	//text2();
	text1();
	return 0;
}

二:队列

(1)什么是队列

【1】队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out)的特性。

【2】入队列:进行插入操作的一端称为队尾

【3】出队列:进行删除操作的一端称为队头

图解:

C语言实现栈和队列(动态)

(2)队列的两种实现方式

【1】和栈类似,队列也可以用数组和链表的结构实现。
【2】数组实现的队列每一次入队都要将数据前移一位,而链表实现的队列入队不需要大量的移动数据,效率更高。

(3)队列的一些基本接口实现

【1】队列的结构体和初始化

结构体:与原先我们实现的链表小有不同,我们要取到队列的最后一个结点的数据或者进行入队,都需要得到尾结点的地址,所以我们可以另外声明一个结构体,其中一个变量为我们熟悉的头指针,一个为记录尾结点地址的尾指针。(也可以不声明这个结构体,但要定义两个结构体指针,一个头和一个尾,函数传参要同时传入这两个指针)

C语言实现栈和队列(动态)

图解:

C语言实现栈和队列(动态)  

初始化:

C语言实现栈和队列(动态)

【2】入队列

思路:

申请新结点并存储数据(注意新结点指针域指空)。

扩容加链接加尾结点更新

③一定要对空队列进行单独处理,不然会对空指针解引用。

代码:

C语言实现栈和队列(动态)

【3】销毁队列

思路:

①和单链表类似,从头结点开始,一个个往后删除

②注意记录下一个结点位置再释放

③要把头和尾都进行置空(避免野指针)。

图解:

C语言实现栈和队列(动态)

代码:

C语言实现栈和队列(动态)

【4】判断队列是否为空

思路:根据头指针是否为空来进行判断

代码:

C语言实现栈和队列(动态)

【5】出队列(删除数据)

思路:

保存原头结点的下一个结点再释放,然后更新头指针

②注意队列为空的时候不能进行删除,不然会对空指针解引用。

③有一个比较隐性的bug,那就是进行了多次删除一直到把队列删空,头指针置空了但是尾指针没有置空,存在野指针的问题。

隐性bug图解:

C语言实现栈和队列(动态)

 代码:

C语言实现栈和队列(动态)

【6】查找队列的头尾数据

思路:

①很简单,直接返回头结点和尾结点的数据

注意队列为空时不能查找,不然会对空指针解引用。

代码:

C语言实现栈和队列(动态)

【7】查找队列的结点个数

一样有两种实现方法:

定义一个计数变量并遍历整个链表直至空。

②在队列结构体中多声明一个size变量来记录,初始化为0,每次出入队列都进行更新

本文采用第一种

代码:

C语言实现栈和队列(动态)

【8】队列的全部代码

Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
//重定义,方便更改存储类型
typedef int QDataType;
//结点的结构体
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;
//队列的结构体(头用来开辟链接,尾用来查找)
typedef struct Queue
{
	//头
	QNode* head;
	//尾
	QNode* tail;
}Queue;


//队列的初始化
void QueueInit(Queue* pq);
//入队列(队列只能从后入)
void QueuePush(Queue* pq, QDataType x);
//队列的销毁
void QueueDestroy(Queue* pq);
//出队列(删除)
void QueuePop(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//查找队列的头数据
QDataType QueueFront(Queue* pq);
//查找队列的尾数据
QDataType QueueBack(Queue* pq);
//查找队列的结点个数
int QueueSize(Queue* pq);

Queue.c(接口实现)

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
//初始化
void QueueInit(Queue* pq)
{
	//断言,不能传空的结构体指针
	assert(pq);
	//初始化,把头和尾都指向空
	pq->head = pq->tail = NULL;
}

//入队列
void QueuePush(Queue* pq,QDataType x)
{
	//断言,不能传空的结构体指针
	assert(pq);
	//申请新结点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	newnode->next = NULL;
	//如果队列为空,单独处理
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		//原尾指向新结点(链接)
		pq->tail->next = newnode;
		//更新尾
		pq->tail = newnode;
	}
}

//队列销毁
void QueueDestroy(Queue* pq)
{
	//断言,不能传空的结构体指针
	assert(pq);
	//先保存下一个,再释放
	QNode* cur = pq->head;
	while (cur)
	{
		//记录
		QNode* next = cur->next;
		//释放
		free(cur);
		//迭代
		cur = next;
	}
	//头尾都置空
	pq->head = pq->tail = NULL;
}


//出队列(删除)
void QueuePop(Queue* pq)
{
	//断言,不能传空的结构体指针
	assert(pq);
	//断言,队列为空不能删除
	assert(!QueueEmpty(pq));
	//保存原头的下一个结点位置
	QNode* newhead = pq->head->next;
	//释放
	free(pq->head);
	//迭代
	pq->head = newhead;
	//如果删除结束了,要把tail指向空(避免野指针)
	if (pq->head == NULL)
		pq->tail = NULL;
}

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	//断言,不能传空的结构体指针
	assert(pq);
	/*if (pq->head == NULL)
		return true;
	else
		return false;*/
	//依据判断语句的指直接返回
	return pq->head == NULL;
}

//查找队列的头数据
QDataType QueueFront(Queue* pq)
{
	//断言,不能传空的结构体指针
	assert(pq);
	//断言,队列为空不能查找
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

//查找队列的尾数据
QDataType QueueBack(Queue* pq)
{
	//断言,不能传空的结构体指针
	assert(pq);
	//断言,队列为空不能查找
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}


//查找队列的结点个数
int QueueSize(Queue* pq)
{
	//断言,不能传空的结构体指针
	assert(pq);
	//计数
	int size = 0;
	//遍历链表
	QNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

text.c(测试)

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
//测试
void text1()
{
	Queue Q;
	QueueInit(&Q);
	QueuePush(&Q, 80);
	QueuePush(&Q, 60);
	QueuePush(&Q, 40);
	QueuePush(&Q, 70);
	QueuePop(&Q);
	QueuePop(&Q);
	QueuePop(&Q);
	QueuePop(&Q);
	bool a = QueueEmpty(&Q);
	//QueueDestroy(&Q);
}

void text2()
{
	Queue Q2;
	QueueInit(&Q2);
	queuepush(&Q2, 80);
	queuepush(&Q2, 60);
	queuepush(&Q2, 100);
	queuepush(&Q2, 67);
	printf("%d ", queuefront(&Q2));
	printf("%d ", queueback(&Q2));
	int size=QueueSize(&Q2);
}

int main()
{
	//text1();
	text2();
	return 0;
}

三:小结

相较于链表,栈和队列的实现更加简单,但有关栈和队列的面试题还是比较难的,下一次我们就会在这一次的基础上完成一些比较经典的OJ题目

C语言实现栈和队列(动态)文章来源地址https://www.toymoban.com/news/detail-414125.html

到了这里,关于C语言实现栈和队列(动态)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 栈和队列OJ题思路分享之栈和队列互换(C语言实现)

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:刷题分享⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你刷更多C语言和数据结构的题!   🔝🔝 我们紧接上一章的刷题分享来把后面两个题给搞定,它们分别是: 1. 用队列实现栈: 力扣225题— 2. 用栈实现队列: 力扣232题.

    2024年02月03日
    浏览(40)
  • 数据结构入门(C语言版)栈和队列之队列的介绍及实现

    什么是队列呢?我们先看下面的图: 我们可以理解成高速公路上的隧道,根据这个图的描述 我们把需入队的元素看作一辆车,把队列看作隧道,由此我们可以看出 队列的特点是 只允许从一端进入,从另一端离开。 队列就是只允许在一端进行插入数据操作,在另一端进行删

    2023年04月15日
    浏览(44)
  • 数据结构初阶(用C语言实现简单数据结构)--栈和队列

    ✨✨欢迎来到T_X_Parallel的博客!!       🛰️博客主页:T_X_Parallel       🛰️专栏 : 数据结构初阶       🛰️欢迎关注:👍点赞🙌收藏✍️留言 这小猫真好看 言归正传,通过上篇有关顺序表和链表的博客,可以了解到线性表的一些大致特征,这篇博

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

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

    2024年02月14日
    浏览(119)
  • 【算法基础】栈和队列及常见变种与使用,双栈、动态栈、栈的迭代器,双端队列、优先队列、并发队列、延迟队列的使用

    目录 一、栈(Stack) 二、 队列(Queue) 三、栈和队列的常见变种与使用 3.1 栈的常见的变种与使用 3.1.1 最小栈(Min Stack) 3.1.2 双栈(Two Stacks) 3.1.3 固定大小栈(Fixed-Size Stack) 3.1.4 可变大小栈(Resizable Stack) 3.1.5 栈的迭代器  3.2 队列的常见变种与使用 3.2.1 双端队列(D

    2024年02月08日
    浏览(31)
  • 【C语言】数据结构——栈和队列实例探究

    💗个人主页💗 ⭐个人专栏——数据结构学习⭐ 💫点击关注🤩一起学习C语言💯💫 我们在前面学习了单链表和顺序表,今天我们来学习栈和队列。 栈和队列相对于单链表和顺序表来说是较为简单的,之后我们再深入学习双链表。关注博主或是订阅专栏,掌握第一消息。 栈

    2024年02月05日
    浏览(46)
  • 【LeetCode】栈和队列OJ题---C语言版

    点击链接 点击链接 解题思路: 此题可以用两个队列去实现一个栈,每次始终保持一个队列为空, 入栈操作相当于给非空队列进行入队操作 出栈操作相当于非空队列的队尾元素出队,此时需要把非空队列除最后一个元素之外的其余元素入队到空队列,然后出队最后一个队尾

    2024年02月05日
    浏览(39)
  • (C语言版)力扣(LeetCode)栈和队列面试题

    给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 题目链接: 有效的括号 代码如下:

    2024年02月05日
    浏览(39)
  • C语言数据结构——线性表之栈和队列

    为什么会定义栈和队列这两种数据结构呢? 原因在于: 之所以会定义栈和队列这样的数据结构 是因为他们有两大特性 : 第一: 他们可以保存程序运行路径中各个点的信息,以便用于回溯操作或其他需要访问已经访问过的节点信息的操作。 比如: 栈用于解决迷宫问题,就

    2023年04月11日
    浏览(113)
  • 用队列实现栈和用栈实现队列

    前面我们实现了栈和队列,其实栈和队列之间是可以相互实现的 下面我们来看一下 用 队列实现栈 和 用栈实现队列 使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty) 实现 MyStack 类: void push(int x) 将元素 x 压入栈顶。 int pop

    2023年04月09日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包