个人网站设计与开发,公司网站维护怎么做,杭州哪里可以做网站推广,毕业设计网站选题欢迎阅读新一期的c语言数据结构模块————栈和队列 ✒️个人主页#xff1a;-_Joker_- #x1f3f7;️专栏#xff1a;C语言 #x1f4dc;代码仓库#xff1a;c_code #x1f339;#x1f339;欢迎大佬们的阅读和三连关注#xff0c;顺着评论回访#x1f339;#… 欢迎阅读新一期的c语言数据结构模块————栈和队列 ✒️个人主页-_Joker_- ️专栏C语言 代码仓库c_code 欢迎大佬们的阅读和三连关注顺着评论回访 文章目录 栈 一、栈的概念 1.什么是栈2.栈的基本操作二、栈的实现 1.定义栈的结构2.栈的初始化3.栈的判空4.入栈5.出栈6.获取栈顶元素7.栈的销毁队列 一、队列的概念 1.什么是队列2.队列的基本操作二、队列的实现 1.定义队列的结构2.队列初始化3.队列判空4.入队5.出队6.获取队首元素7.队列的销毁 栈
一、栈的概念
1.什么是栈 栈stack又名堆栈它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶相对地把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈它是把新元素放到栈顶元素的上面使之成为新的栈顶元素从一个栈删除元素又称作出栈或退栈它是把栈顶元素删除掉使其相邻的元素成为新的栈顶元素。 栈顶(Top): 线性表允许进行插入删除的那一端。栈底(Bottom): 固定的不允许进行插入和删除的另一端。空栈: 不含任何元素的空表。 因为其后进先出Last In First Out的特性栈又称为的线性表简称LIFO结构 2.栈的基本操作 栈的基本操作通常都有以下几种 InitStack(Stack)初始化一个空栈S。StackEmpty(Stack)判断一个栈是否为空若栈为空则返回true否则返回false。StackPush(Stack, x)进栈栈的插入操作若栈S未满则将x加入使之成为新栈顶。StackPop(Stack)出栈栈的删除操作若栈S非空则返回一个提示.GetTop(Stack)读栈顶元素。DestroyStack(Stack)栈销毁并释放S占用的存储空间“”表示引用调用。 二、栈的实现
1.定义栈的结构 栈又分为顺序栈和链式栈这里我们以顺序栈为例 首先想要实现一个栈我们需要了解如何创建一个栈的结构这里我们可以用结构体来定义有两种方式 ①
#define N 10//定义栈的大小
struct Stack
{int a[N];int top;//栈顶
};
②
typedef int STDataType;
typedef struct Stack
{STDataType* a;//定义一个栈int top;//栈顶int capacity;//栈的大小
}ST; 第一种结构是用一个宏定义常量定义的栈的大小这种用静态开辟的空间存在一些瑕疵如果栈的空间大小太小需要成倍的扩容很容易造成空间的浪费所以我们优先采用方法②。 这种方法的好处在于我们可以动态开辟空间如果空间不够就多开一个空间这样就可以避免空间的浪费。 2.栈的初始化
void InitStack(ST* ps)
{assert(ps);//断言ps-a NULL;//将指针置为空ps-capacity 0;//初始化大小ps-top 0;
} 3.栈的判空
bool StackEmpty(ST* ps)
{assert(ps);//断言return ps-top 0;//栈顶为0则为空
} 4.入栈
入栈的具体流程如图 入栈首先判断空间大小若已满则需要扩容然后从栈底向上逐个插入 入栈操作如下
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)//判断空间是否开辟成功{perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;//插入元素ps-top;//栈顶移动
}5.出栈
出栈操作如图 出栈首先判断是否为空若为空则返回一个提示若不为空则只需要直接将栈顶向下移动即可达到出栈的效果。 出栈操作如下;
void StackPop(ST* ps)
{assert(ps);//断言assert(ps-top 0);//判断空--ps-top;//栈顶移动
} 6.获取栈顶元素 这里需要注意top的位置如果top的指向是栈顶元素的话则只需要return a[ps-top]即可由于我这里的top是指向栈顶元素的下一个位置所以需要top-1才可以获取到栈顶元素. STDataType StackTop(ST* ps)
{assert(ps);assert(ps-top 0);//判断为空return ps-a[ps-top - 1];//返回栈顶元素
} 7.栈的销毁
void StackDestroy(ST* ps)
{assert(ps);free(ps-a);//释放栈的空间ps-a NULL;//将指针置空防止野指针产生ps-top ps-capacity 0;
} 队列
一.队列的概念
1.什么是队列 队列是一种特殊的线性表特殊之处在于它只允许在表的前端front进行删除操作而在表的后端rear进行插入操作和栈一样队列是一种操作受限制的线性表。进行插入操作的端称为队尾进行删除操作的端称为队头。 队首(front): 线性表允许进行插入删除的那一端。队尾(rear): 固定的不允许进行插入和删除的另一端。空队列: 不含任何元素的空表。 因为其先进先出First In First Out的特性队列又称为的线性表简称FIFO结构 2.队列的基本操作 QueueInit(Q)初始化队列构造一个空队列Q。QueueEmpty(Q)判队列空若队列Q为空返回true否则返回false。QueuePush(Q, x)入队若队列Q未满将x加入使之成为新的队尾。QueuePop(Q)出队若队列Q非空删除队头元素。QueueFront(Q)读队头元素。QueueDestroy(Q): 队列销毁。 二.队列的实现 队列同样拥有两种实现方式顺序结构和链式结构但是用顺序结构实现队列在出列的情况比较复杂所以这里我们以链式结构来实现队列 1.定义队列的结构 和栈类似队列的结构可以这样定义 typedef int QDataType;
typedef struct QueueNode//队列节点
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue//队列结构
{QNode* head;//队首QNode* tail;//队尾int size;
}Que; 2.队列初始化
void QueueInit(Que* pq)
{assert(pq);//断言pq-head pq-tail NULL;//头尾指针置空pq-size 0;//大小初始化
} 3.队列判空
bool QueueEmpty(Que* pq)
{assert(pq);//断言return pq-head NULL;//头指针为空则为空
} 4.入队
入队操作如图 入队新开一个节点将元素插入新的节点然后判断尾指针是否指向空若为空则将头尾指针指向新的节点若不为空则将新的节点作为队尾。 入队实现:
void QueuePush(Que* pq, QDataType x)
{assert(pq);//断言QNode* newnode (QNode*)malloc(sizeof(QNode));//开一个新节点if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;//新节点赋值newnode-next NULL;if (pq-tail NULL)//空队列{pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
} 5.出队 出队操作和入队操作类似出队首先判空若队列为空则返回一个提示若不为空需要将队首节点指向下一个节点并释放第一个节点。若队首的下一个元素为空说明改队列只有一个节点所以需要将头尾指针置空防止野指针的产生。 出队操作如下
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));//判空if (pq-head-next NULL)//判断队首下一个节点是否为空{free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;//新开一个节点并将头指针下一个节点给新节点free(pq-head);//释放队首pq-head next;//将新开的节点赋给新队首}pq-size--;//队列大小-1
}6.读取队首元素
QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));//判空return pq-head-data;//取队首元素
} 7.队列销毁
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur pq-head;//创建一个节点存储队首while (cur)//{QNode* next cur-next;//创建一个中间节点free(cur);//从队首一个一个删除cur next;}pq-head pq-tail NULL;//删完所有节点将指针置空pq-size 0;//初始化大小
} 以上就是栈和队列的基本概念和基础操作实现如果文章存在错误请在评论区留言最后别忘了三连支持一下顺着评论回访
