Skip to main content

moregeek program

栈和队列的实现_萌新的日常的博客-多极客编程

(文章目录)


一、栈


1.概念



一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作,进行数据插入和删除操作的一端称为栈顶,另一端称为栈底,栈中的数据元素遵循后进先出的原则。
注意从栈顶入,栈顶出在这里插入图片描述



二 、栈的实现(顺序表)


1.函数的定义和结构体的创建——stack.h


#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int datatype;
typedef struct stack
{
datatype* a;
int top;
int capacity;
}ST;
void stackinit(ST* p);
void stackpush(ST* p, datatype x);
int stacktop(ST* p);
void stackpop(ST* p);
int stacksize(ST* p);
bool stackempty(ST* p);
void stackdestroy(ST* p);

2.函数的调用——test.c


#include"stack.h"
int main()
{
ST st;
stackinit(&st);
stackpush(&st, 1);
stackpush(&st, 2);
stackpush(&st, 3);
stackpush(&st, 4);
while (!stackempty(&st))//判断是否为空
{
printf("%d ", stacktop(&st));//出栈
stackpop(&st);//移除栈顶元素
}
stackdestroy(&st);//内存销毁
return 0;
}

3.栈的接口


1.初始化


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

2.入栈


void stackpush(ST* p, datatype x)//入栈
{
assert(p);
if (p->top == p->capacity)//扩容
{
int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity;
datatype* tmp = (datatype*)realloc(p->a, sizeof(datatype) * newcapacity);
if (tmp != NULL)
{
p->a = tmp;
p->capacity = newcapacity;//扩容成原来的2倍
}
}
p->a[p->top] = x;
p->top++;
}

在这里插入图片描述


3.移除栈顶元素


void stackpop(ST* p)//移除栈顶元素
{
assert(p);
assert(p->top > 0);
p->top--;
}

4.出栈


int  stacktop(ST* p)//出栈
{
assert(p);
assert(p->top > 0);
return p->a[p->top - 1];//top从0开始,每次入栈top都向后移,所以top-1是实际储存的元素
}

在这里插入图片描述


5.判断为空


bool  stackempty(ST* p)//是否为空
{
return p->top == 0;//当栈中没有数据时,则为空,为真, 否则为假。
}

6.栈中元素个数


int stacksize(ST* p)//栈中元素个数
{
assert(p);
return p->top;//虽然top是指向下一个,但是top从0开始,top正好是元素个数
}

7.内存销毁


void stackdestroy(ST* p)//内存销毁
{
assert(p);
free(p->a);//销毁动态开辟数组
p->a = NULL;
p->top = 0;
p->capacity = 0;
}

三、队列


1.概念



只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的原则。
入队列:进行插入操作的一段称为队尾
出队列:进行删除操作的一端称为对头
注意 :对尾入,对头出
在这里插入图片描述



四、队列的实现(链表)


1.函数的定义和结构体的创建——queue.h


#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int datatype;
typedef struct queuenode
{
datatype data;
struct queuenode* next;
}queuenode;
typedef struct queue
{
queuenode * head;
queuenode * tail;
}queue;
void queueinit(queue*p);
void queuedestroy(queue* p);
void queuepush(queue* p,datatype x);
void queuepop(queue* p);
datatype queuefront(queue* p);
datatype queueback(queue* p);
int queuesize(queue* p);
bool queueempty(queue* p);


2.函数的调用——test.c


#include"queue.h"
int main()
{
queue p;
queueinit(&p);
queuepush(&p, 1);
queuepush(&p, 2);
queuepush(&p, 3);
queuepush(&p, 4);
while (!queueempty(&p))//判断为空
{
datatype front = queuefront(&p);
printf("%d ", front);
queuepop(&p);
}
queuedestroy(&p);//内存销毁
return 0;
}

3.取一级指针的原因



正常来说,如果将head与tail放在queuenode内部,应该取二级指针,
但是由于此时定义的是结构体为queue 的变量,改变的是该变量的内部。
所以只取一级指针就可以。



4.队列的接口的实现


1.初始化


void queueinit(queue* p)//初始化队列
{
assert(p);
p->head = NULL;
p->tail = NULL;
}

2.入队列


void queuepush(queue* p,datatype x)//入队列 (队尾入)
{
assert(p);
queuenode* newnode = (queuenode*)malloc(sizeof(queuenode));
newnode->data = x;
newnode->next = NULL;
if (p->tail == NULL)
{
p->tail = newnode;
p->head = newnode;
}
else
{
p->tail->next = newnode;
p->tail = newnode;
}
}

在这里插入图片描述


3.删除数据


void queuepop(queue* p)//删除数据
{
assert(p);
assert(!queueempty(p));//断言队列是否为空
queuenode* next = p->head->next;
free(p->head);
p->head = next;
if (p->head == NULL)//当删除只剩下最后一个节点时 head与tail都指向,free(head) ,tail就变成了野指针
{
p->tail = NULL;
}
}

4.取对头数据


datatype queuefront(queue* p)//取队头数据
{
assert(p->head);
assert(!queueempty(p));
return p->head->data;
}

在这里插入图片描述


5.取队尾数据


datatype queueback(queue* p)//取队尾数据
{
assert(p->head);
assert(!queueempty(p));
return p->tail->data;
}

在这里插入图片描述


6.取队的元素个数


int queuesize(queue* p)//队的数量
{
assert(p);
int sum = 0;
queuenode* cur = p->head;
while (cur != NULL)
{
sum++;
cur= cur->next;
}
return sum;
}

7.判断为空


bool queueempty(queue* p)//判断队列是否为空
{
assert(p);
return p->head == NULL;
}

8.内存销毁


void queuedestroy(queue* p)//内存销毁
{
assert(p);
queuenode* cur = p->head;
while (cur != NULL)
{
queuenode* next = cur->next;
free(cur);
cur = next;
}
p->head = NULL;
p->tail = NULL;
}

©著作权归作者所有:来自51CTO博客作者萌新的日常的原创作品,请联系作者获取转载授权,否则将追究法律责任

qt小结1_五个板栗的博客-多极客编程

1.在设计界面时,只需要在UI设计器里进行可视化设计操作,不需要.ui文件是怎么生成的,会自动生成。2.信号和槽(signal & slot):使QT各个组件之间的交互更加简单和直观。信号函数无需实现,只需要在某些条件下发射信号。3.添加资源文件。资源文件最主要的功能是存储图标和图片文件。在Qt Creator里面单击File ——New File or Project 菜单项,在新建文件

二叉排序树_wx619474981d7fe的博客-多极客编程

1 二叉排序树的定义果查找的数据集是有序线性表,并且是顺序存储的,查找可以用折半查找算法来实现,因为有序,在插入和删除操作上,就需要耗费大量的时间。假设现在我们的数据只有一个数{62,88,58,47,35,73,51,99,37,93}做查找,建立好的二叉排序树如图所示,62、88、58创建好后,下一个数47因比58小,是它的左子树,35是47的左子树,73比62大,但比88小,是88的左子树,

单链表的(增删查改)的实现_萌新的日常的博客-多极客编程

(文章目录) 一、链表 1.链表的概念 一种物理存储结构上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针连接次序实现的。 2.链表优点 1.空间上按需所给空间 2.在头部和中间插入时,不需要挪动数据 二、单链表的实现 1.函数的定义和结构体的创建——list.h #include<stdio.h> #include<stdlib.h> #includ

散列表查找(哈希算法)的定义与实现_wx619474981d7fe的博客-多极客编程

1 散列表查找定义散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系,使得每个关键字key对应一个存储位置。存储位置=f(关键字)对应关系称为散列函数,又称为哈希(Hash)函数。采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表。散列技术既是一种存储方法,也是一种查找方法。散列函数可能会把两个或两个以上的不同关键字映射到同一地址,称这些情况为冲突,这些

c++ "链链"不忘@必有回响之双向链表_一枚大果壳的博客-多极客编程

C++ "链链"不忘@必有回响之双向链表 1. 前言 写过一篇与单链表相关的博文(https://blog.51cto.com/gkcode/5681771),实际应用中,双向循环链表的功能更强大。 单链表中,查询一个已知结点的后驱结点的时间复杂度为O(1)。因结点本身不存储与前驱结点相关的地址信息,查询前驱结点需要从头结点扫描一次,所以时间复杂度是O(n)。 双向链表在结点类型中增加了可以存储前

操作符详解(2)_hanwang的博客-多极客编程

一、按位取反的应用场景1、如何将一个二进制数其中的某一位改为1可以进行按位或(若有一个为真1,输出结果就为真),或上一个1TIP:如何定位二进制中的某一位数?可以左移n个字符。2、将第一题的数再还原还回去可以按位与,但如何获得按位与这个二进制数,需要将原来的二进制进行按位取反!二、前置++与后置++的区别第一个输出结果为11,第二个10三、sizeof易错题输出结果40 10 4 4第三个和第四个

harmonyos - 基于arkui(js)实现信件弹出效果_鸿蒙社区的博客-多极客编程

作者:罗晓纯 前言 自从大家使用QQ、微信、邮件等网络平台交流以后,大家对纸这种介质和书信这种通讯方式可能都比较陌生了。可别觉得书信是一个过时的东西,它可是80后的情怀,90后的回忆,00后的新宠,是经典的代名词。今天就想实现把这些古老的元素融入到新时代的产物当中。 项目说明 工具:DevEc Studio 3.0 Beta3 主要用到知识:animation,Options,keyframes

java中容器设计的进化史:从白盒到黑盒,再到跻身为设计模式之一的迭代器_架构悟道的博客-多极客编程

大家好,又见面了。 在我们的项目编码中,不可避免的会用到一些容器类,我们可以直接使用List、Map、Set、Array等类型。当然,为了体现业务层面的含义,我们也会根据实际需要自行封装一些专门的Bean类,并在其中封装集合数据来使用。 看下面的一个场景: 在一个企业级的研发项目事务管理系统里面,包含很多的项目,每个项目下面又包含很多的具体需求,而每个需求下面又会被拆分出若干的具体事项。 上面

qt小结1_五个板栗的博客-多极客编程

1.在设计界面时,只需要在UI设计器里进行可视化设计操作,不需要.ui文件是怎么生成的,会自动生成。2.信号和槽(signal & slot):使QT各个组件之间的交互更加简单和直观。信号函数无需实现,只需要在某些条件下发射信号。3.添加资源文件。资源文件最主要的功能是存储图标和图片文件。在Qt Creator里面单击File ——New File or Project 菜单项,在新建文件

消息中间件activemq常见问题解析_浅羽技术的博客-多极客编程

1.什么是 ActiveMQ? activeMQ 是一种开源的,实现了 JMS1.1 规范的,面向消息(MOM)的中间件,为应用程序提供高效的、 可扩展的、稳定的和安全的企业级消息通信 2. ActiveMQ 服务器宕机怎么办? 这得从 ActiveMQ 的储存机制说起。在通常的情况下,非持久化消息是存储在内存中的,持久化消息是存 储在文件中的,它们的最大限制在配置文件的<systemUsa

30天python入门到进阶——第5天:流程控制_freestu的博客-多极客编程

已经进行了四天的Python学习体验。到目前为止,已经能够涵盖 Python 的一些基本语法以及数据类型,以及如何使用内置函数和方法以及一些最佳实践对它们执行操作。这可能是 Python 的枯燥部分。今天短期目标是理解逻辑和条件编程,以及在 Python 中使用循环重复任务。这可是很有意思的!流程控制流程控制指的是代码运行逻辑、分支走向、循环控制,是真正体现我们程序执行顺序的操作。流程控制一般分为

【操作系统】计算机操作系统r复习大纲——汤子瀛版_灵彧universe的博客-多极客编程

操作系统的定义          一组能有效地组织和管理计算机硬件和软件资源,合理地对各类作业进行调度,以及方便用户使用的程序的集合 操作系统的基本类型及特征         基本类型:单道批处理系统、多道批处理系统、分时系统、实时系统、微机操作系统、嵌入式操作系统、网络操作系统、分布式操作系统 特征:   (1)单道批处理:自动性、顺序性、单道性   (2)多道批处理:多道、成批处理、无