赞
踩
个人主页:星纭-CSDN博客
系列文章专栏:数据结构
踏上取经路,比抵达灵山更重要!一起努力一起进步!
目录
栈是一种线性数据结构,它只能在固定的一端进行插入和删除操作,这一端被称为栈顶,另一端则称为栈底。栈的特点是后进先出(Last In First Out,LIFO),即最后插入的元素最先被删除,而最先插入的元素最后被删除。
栈的基本操作有两个:入栈(push)和出栈(pop)。入栈操作将元素插入到栈顶,出栈操作将栈顶元素删除并返回。
栈可以用来解决一些具有后效性的问题,例如表达式求值、括号匹配、函数调用等。它也可以用于实现一些常见的数据结构,例如递归函数、深度优先搜索等。
栈可以使用数组或链表来实现。使用数组实现的栈称为顺序栈,使用链表实现的栈称为链式栈。无论使用哪种实现方式,栈的空间复杂度都为O(n),其中n为栈中元素的个数。
栈还有一些常见的扩展操作,例如获取栈顶元素(top)、判断栈是否为空(isEmpty)、获取栈中元素个数(size)等。这些操作的时间复杂度都为O(1)。
对于顺序栈来说,又分两种情况:一种是定长的静态栈结构,一般情况下,实际中用的比较少,另一种是支持动态增长的栈。
以下的栈的实现,作者基于支持动态增长的顺序栈完成。
- typedef int STDatatype;
- typedef struct{
- STDatatype* a;
- int top;//栈顶
- int capacity;//栈的容量
- }Stack;
为了方便对存储的数据类型进行更改,我们对int重命名一下,如果以后要存储char类型的数据,只需要更改一下int为char就可以轻松完成。
- //初始化
- void STInit(Stack* pst);
- //销毁
- void STDestory(Stack* pst);
1.初始化
- void STInit(Stack* pst) {
- pst->a = NULL;
- pst->capacity = pst->top = 0;
- };
因为开始的时候,这个栈中并没有任何的元素,所以我们将其的a初始化为NULL,top和capacity为0.
其实对于top的初始化是有两种情况的:
如果top指向的是栈顶的元素:
比如这样的TOP就是指向栈顶的元素8,此时存放了3个数据,Top的值等于2.
可以是我们开始初始化为0,此时的TOP指向下标为0的位置,可是此时的位置上并没有元素,这里的top指向的是栈顶元素的下一个位置,并不是栈顶元素。
所以如果要使top指向栈顶元素,初始化应该为-1,而不是0.
本文采用top指向栈顶元素的下一个位置。
2.销毁
销毁其实和初始化很类似。
因为a是我们使用malloc函数动态开辟的空间,所以我们需要free释放掉a。
- //初始化
- void STInit(Stack* pst) {
- assert(pst);
- pst->a = NULL;
- pst->capacity = pst->top = 0;
- };
- //销毁
- void STDestory(Stack* pst) {
- assert(pst);
- free(pst->a);
- pst->a = NULL;
- pst->capacity = pst->top = 0;
- };
为了防止pst->a时造成野指针,需要对pst进行断言一下,避免pst是NULL.
1.入栈
在入栈之前,我们需要对栈判断空间是否足够。因为top指向的是栈顶元素的下一个位置,所以当满了的条件是top等于capacity,而对于top指向的是栈顶元素而言,判满的条件是capacity = top + 1.
可是对于这个条件来说,当容量为0的时候,这个条件也成立,所以这里需要使用三目操作符,更改容量,以免乘以2后还是0.用tmp接收开辟的空间是为了避免开辟失败,返回NULL,导致a变成了NULL,使数据丢失。realloc函数当第一个 参数的值为NULL的时候,它的功能和malloc函数一模一样。所以我们不需要单独判断a是否为NULL.
- void STPush(Stack * 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,newcapacity * sizeof(STDatatype));
- if (tmp == NULL)
- {
- perror("malloc fail");
- exit(1);
- }
- pst->a = tmp;
- pst->capacity = newcapacity;
- }
- pst->a[pst->top++] = x;
- };
注意:最后记得top+1,不要忘了。
2.出栈
对于数组而言,出栈的时候,并不需要把这个数据真的移除掉,只需要top--即可,因为这样这个元素实际上就不在这个栈中了,我们再入栈的时候,就会覆盖掉这个元素。
- void STPop(Stack* pst) {
- assert(pst);
- assert(pst->top>0);
- pst->top--;
- };
出栈要注意,栈空了就不能出栈了。否则top就变成负数了。
- //栈顶元素
- STDatatype STTop(Stack* pst) {
- assert(pst);
- assert(pst->top>0);
- return pst->a[pst->top - 1];
- };
- //判空
- bool IsEmpty(Stack* pst) {
- assert(pst);
- return pst->top == 0;
- }
- //求元素个数
- int STSize(Stack* pst) {
- assert(pst);
- return pst->top;
- };
这三个函数非常简单:栈定元素需要保证这个栈不能为空,也就是top要大于0,否则不对。
判空,当栈空的时候top就0,所以只需要判断top等不等于0即可。
求元素个数:因为top指向栈顶元素的下一个位置,又因为数组下标从0开始,所以top就代表元素的个数。
- #define _CRT_SECURE_NO_WARNINGS
- #include"stack.h"
- int main()
- {
- Stack s;
- STInit(&s);
- STPush(&s,1);
- printf("%d->", STTop(&s));
- STPush(&s,2);
- printf("%d->", STTop(&s));
- STPush(&s,3);
- printf("%d->", STTop(&s));
- STPush(&s,4);
- printf("%d->", STTop(&s));
- STPush(&s,5);
- printf("%d->", STTop(&s));
- STPush(&s,6);
- printf("%d->", STTop(&s));
- printf("\n栈总共有%d个元素\n",STSize(&s));
- //打印整个栈的元素
- while (!IsEmpty(&s)) {
- printf("%d->",STTop(&s));
- STPop(&s);
- }
- printf("\n栈总共有%d个元素\n", STSize(&s));
- STDestory(&s);
- return 0;
- }
输出结果:
- #pragma once
- #include<stdio.h>
- #include<stdlib.h>
- #include<assert.h>
- #include<stdbool.h>
- //#include<>
- typedef int STDatatype;
- typedef struct{
- STDatatype* a;
- int top;//栈顶
- int capacity;//栈的容量
- }Stack;
-
- //初始化
- void STInit(Stack* pst);
- //销毁
- void STDestory(Stack* pst);
- //入栈
- void STPush(Stack* pst, STDatatype x);
- //出栈
- void STPop(Stack* pst);
- //栈顶元素
- STDatatype STTop(Stack* pst);
- //判空
- bool IsEmpty(Stack* pst);
- //求元素个数
- int STSize(Stack* pst);
- #define _CRT_SECURE_NO_WARNINGS
- #include"stack.h"
- //初始化
- void STInit(Stack* pst) {
- assert(pst);
- pst->a = NULL;
- pst->capacity = pst->top = 0;
- };
- //销毁
- void STDestory(Stack* pst) {
- assert(pst);
- free(pst->a);
- pst->a = NULL;
- pst->capacity = pst->top = 0;
- };
- //入栈
- void STPush(Stack * 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,newcapacity * sizeof(STDatatype));
- if (tmp == NULL)
- {
- perror("malloc fail");
- exit(1);
- }
- pst->a = tmp;
- pst->capacity = newcapacity;
- }
- pst->a[pst->top++] = x;
- };
- //出栈
- void STPop(Stack* pst) {
- assert(pst);
- assert(pst->top>0);
- pst->top--;
- };
- //栈顶元素
- STDatatype STTop(Stack* pst) {
- assert(pst);
- assert(pst->top>0);
- return pst->a[pst->top - 1];
- };
- //判空
- bool IsEmpty(Stack* pst) {
- assert(pst);
- return pst->top == 0;
- }
- //求元素个数
- int STSize(Stack* pst) {
- assert(pst);
- return pst->top;
- };
队列是一种常见的数据结构,它遵循先进先出(FIFO)的原则,只允许在一端(队尾)进行插入数据,在另一端(队头)进行删除数据。队列有两个主要操作:入队(enqueue)和出队(dequeue)。入队将元素添加到队列的末尾,出队将队列的第一个元素删除并返回。
队列与排队类似,有素质的人,不会插队,会从排到队尾,完成事情后,从队头离开。
所以我们,是不能访问中间元素的。
队列通常用于存储需要按照顺序处理的数据。例如,在计算机科学中,可以使用队列来实现广度优先搜索算法(BFS)。
在实现队列时,可以使用数组或链表来存储队列中的元素。数组实现的队列被称为顺序队列,链表实现的队列被称为链式队列。
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。
本文,作者采用链式队列。
队列的时间复杂度如下:
队列的空间复杂度为O(n),其中n是队列中的元素数量。
- typedef int QDatatype;
- typedef struct QueueNode {
- struct QueueNode* next;
- QDatatype val;
- }QNode;
- typedef struct Queue {
- QNode* phead;
- QNode* ptail;
- int size;//节点个数
- }Queue;
这里采用两个指针分别指向队头与队尾,为了方便,把两个指针与size存放在一个结构体中,这样传参更加的方便。
1.初始化
最开始时,队列中是没有任何元素的。
- //初始化
- void QueueInit(Queue* pq) {
- assert(pq);
- pq->phead = pq->ptail = NULL;
- pq->size = 0;
- };
注意观察此处的参数,如果不放在一个结构体 中,那么传参的时候,就需要传递三个指针,大大地增加了使用者的操作难度。开始要断言一下,以免pq为NULL。
2.销毁
- //销毁
- void QueueDestory(Queue* pq) {
- assert(pq);
- QNode* cur = pq->phead;
- while (cur) {
- QNode* next = cur->next;
- free(cur);
- cur = next;
- }
- pq->phead = pq->ptail = NULL;
- pq->size = 0;
- };
队列的销毁与单链表的销毁很相似,这里不过多介绍。
1.插入
插入数据,先malloc动态申请内存来存放这个数据。
然后考虑当这个队列没有元素的时候,phead和ptail指针均指向NULL,这个新插入的节点,即是头节点又是尾节点,所以需要分开讨论。
- //队尾插入数据
- void QueuePush(Queue* pq, QDatatype x)
- {
- QNode* newnode = (QNode*)malloc(sizeof(QNode));
- if (newnode == NULL)
- {
- perror("malloc fail");
- exit(1);
- }
- newnode->val = x;
- newnode->next = NULL;
- if (pq->phead == NULL) {
- pq->phead = pq->ptail = newnode;
- pq->size++;
- }
- else {
- pq->ptail->next = newnode;
- pq->ptail = newnode;
- pq->size++;
- }
- }
当队列为空的时候,就直接将phead与ptail指针指向newnode既可。如果队列不为空就尾插。
2.删除
删除数据,需要释放第一个节点即可,然后让phead指针指向下一个节点。
可是这样写有一个问题,如果此时队列只有一个节点,如果只改变phead的话,ptail仍然指向原来的节点,这样的就会造成野指针了,所以仍然分开讨论。
- //队头删除数据
- void QueuePop(Queue* pq)
- {
- assert(pq);
- assert(pq->phead);
- //一个节点
- if (pq->phead == pq->ptail) {
- free(pq->phead);
- pq->phead = pq->ptail = NULL;
- }//多个节点
- else {
- QNode* del = pq->phead;
- pq->phead = pq->phead->next;
- free(del);
- del = NULL;
- }
- --pq->size;
- }
第二个断言是为了防止队列为空仍然删除数据。
- // 取队头和队尾的数据
- QDatatype QueueFront(Queue* pq) {
- assert(pq);
- assert(pq->size);
- return pq->phead->val;
- };
- QDatatype QueueBack(Queue* pq) {
- assert(pq);
- assert(pq->size);
- return pq->ptail->val;
- };
在查看之前,首先要确定这个队列中有元素,否则不能查看
- int QueueSize(Queue* pq) {
- assert(pq);
- return pq->size;
- };
- bool QueueEmpty(Queue* pq) {
- assert(pq);
- return pq->size == 0;
- };
判空与队列大小很简单这里就不过多讲解。
Queue.h:
- #pragma once
- #include<stdio.h>
- #include<stdlib.h>
- #include<assert.h>
- #include<stdbool.h>
- typedef int QDatatype;
- typedef struct QueueNode {
- struct QueueNode* next;
- QDatatype val;
- }QNode;
- typedef struct Queue {
- QNode* phead;
- QNode* ptail;
- int size;
- }Queue;
- //初始化与销毁
- void QueueInit(Queue* pq);
- void QueueDestory(Queue* pq);
-
- //队尾插入数据/队头删除数据
- void QueuePush(Queue* pq,QDatatype x);
- void QueuePop(Queue* pq);
-
- // 取队头和队尾的数据
- QDatatype QueueFront(Queue* pq);
- QDatatype QueueBack(Queue* pq);
- //判空与队列大小
- int QueueSize(Queue* pq);
- bool QueueEmpty(Queue* pq);
Queue.c:
- #define _CRT_SECURE_NO_WARNINGS
- #include"queue.h"
- //初始化
- void QueueInit(Queue* pq) {
- assert(pq);
- pq->phead = pq->ptail = NULL;
- pq->size = 0;
- };
- //销毁
- void QueueDestory(Queue* pq) {
- assert(pq);
- QNode* cur = pq->phead;
- while (cur) {
- QNode* next = cur->next;
- free(cur);
- cur = next;
- }
- pq->phead = pq->ptail = NULL;
- pq->size = 0;
- };
- //队尾插入数据
- void QueuePush(Queue* pq, QDatatype x)
- {
- QNode* newnode = (QNode*)malloc(sizeof(QNode));
- if (newnode == NULL)
- {
- perror("malloc fail");
- exit(1);
- }
- newnode->val = x;
- newnode->next = NULL;
- if (pq->phead == NULL) {
- pq->phead = pq->ptail = newnode;
- pq->size++;
- }
- else {
- pq->ptail->next = newnode;
- pq->ptail = newnode;
- pq->size++;
- }
- }
- //队头删除数据
- void QueuePop(Queue* pq)
- {
- assert(pq);
- assert(pq->phead);
- //一个节点
- if (pq->phead == pq->ptail) {
- free(pq->phead);
- pq->phead = pq->ptail = NULL;
- }//多个节点
- else {
- QNode* del = pq->phead;
- pq->phead = pq->phead->next;
- free(del);
- del = NULL;
-
- }
- --pq->size;
- }
- // 取队头和队尾的数据
- QDatatype QueueFront(Queue* pq) {
- assert(pq);
- assert(pq->size);
- return pq->phead->val;
- };
- QDatatype QueueBack(Queue* pq) {
- assert(pq);
- assert(pq->size);
- return pq->ptail->val;
- };
-
- int QueueSize(Queue* pq) {
- assert(pq);
- return pq->size;
- };
- bool QueueEmpty(Queue* pq) {
- assert(pq);
- return pq->size == 0;
- };
循环队列与双端队列,下一篇文章讲解。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。