栈和队列是我们数据结构中经常使用的数据结构,所以现在来了解一下栈和队列。
栈
特点:
栈是一种特殊的线性表,其中进行数据插入和弹出的部分叫做栈顶,另一端叫做栈底。
只允许数据从栈顶压入,从栈顶弹出即先进后出的特点,也称LIFO (Last In First Out)。
压栈:将数据从栈顶压入栈中。
弹栈:将栈顶的数据从栈中弹出。
实现:
接下来基于C语言来实现一个栈,及其增删查改功能:
栈的初始化:
对于栈,肯定要和链表一样进行数据结构定义,但是对于链表我们只需要开一个大小的空间即可,但是栈可能会压入多个数据,我们无法得知具体数目,所以我们一开始选择将栈的大小设置成为4,后续对栈容量进行动态扩容即可。
typedef struct stack { int* data; int size, top; }stack; stack* Stack_Init() { stack* p = (stack*)malloc(sizeof(stack)); p->data = (int*)malloc(sizeof(int) * 4); p->size = 4; p->top = -1; return p; }
栈的销毁:
既然我们使用malloc函数来分配了栈的内存,那么我们就需要设置一个函数来释放栈的内存空间:
void Stack_Free(stack* p) { if (p == NULL) { return; } free(p->data); free(p); return; }
栈的压入操作:
在上文,我们考虑到了由于栈要压入未知数据量,所以我们不能固定栈的大小,则需要动态内存开辟,实现栈的容量的增加。
但是又考虑到另外一个问题,我们要增加多少容量呢?当数据量很大时,只增加个位数或十位数级别的容量对栈的帮助不大,任然需要频繁增加栈的容量,那么我们每次改变栈的容量时,将栈的容量翻一倍即可,以达到减少扩容次数的需要。
在思考完栈的容量管理后,栈的压入就变得简单了,只需要将栈的size位置放入数据并且让size+1即可。
int Stack_Push(int val, stack* p) { if ( (p->top) + 1 == p->size || p == NULL) { p->data=(int*)realloc(p,p==NULL?sizeof(int)*4:2*p->size*sizeof(int)); } p->data[p->top + 1] = val; p->top += 1; return 1; }
查询栈顶元素:
由于栈后进先出的特性,我们只能查找到栈顶元素
int top(stack* p) { if (p->top == -1) { return NULL; } return p->data[p->top]; }
栈的判空:
当栈中不含有元素时,我们则不能继续弹出栈顶的元素,所以我们需要判断栈内此时是否存有元素。
int Empty(stack* p) { if (p == NULL) { return NULL; } return (p->top == -1); }
栈的弹出操作:
栈的弹出存在一种特殊情况即栈为空时弹出元素,此时弹出操作则为违法操作。
所以在弹出操作前,我们需要调用判空函数来判断弹出操作是否合法。
若栈内不为空,则弹出栈顶元素;若栈内为空,则返回NULL即可。
int Stack_Pop(stack* p) { if (Empty(p) ==0) { return 0; } p->top -= 1; return p->data[(p->top) + 1]; }
此外栈还可以由链表实现,由链表实现的栈则省去了栈的扩容操作,节约了时间。
队列:
特点:
队列也是一种特殊的线性表,其中进行数据插入的部分叫做队尾,弹出数据的部分叫做队首。
队列只允许数据从队尾压入,从队首弹出。
具有先进先出的特点,也称FIFO (First In First Out)。
实现:
接下来是基于C语言实现队列及其增删查改的操作:
队列的初始化:
队列与栈相似,我们都需要对其进行数据结构的定义。
在定义完数据结构后,我们任然需要与栈一样考虑队列的大小管理,所以我们将队列的大小初始化为4。
typedef struct queue { int* data; int size, count, head, tail; }queue; //初始化队列 queue* Init_Queue(int n) { queue* p = (queue*)malloc(sizeof(queue)); p->data = (int*)malloc(sizeof(int)*4); //让count,head,size,tail为0 p->count = p->head = p->size = p->tail = 0; //返回该队列的首地址 return p; }
队列的销毁:
由于队列使用了malloc函数分配了内存,所以我们需要手动销毁queue的内存。
//定义一个函数用于释放队列的空间 void Queue_Free(queue* head) { if (head == NULL) { return; } free(head->data); free(head); return; }
队列的插入操作:
队列与栈一样,当队列容量即将满时,我们将队列的大小翻一倍。
然后将数据插入到队列中即可:
void Queue_Insert(queue* p,int val){ if(p->data==NULL || (p->count+1==p->size)){ p->data=(int*)realloc(p->data,p->data==NULL?4:2*sizeof(int)*p->size); p->size*=2; } p->data[p->count++]=val; p->tail++; return; }
队列的判空:
队列与栈一致,当队列为空时,弹出队首元素为违法操作,所以我们需要对队列进行判空
int Empty(queue* p) { return (p->count == 0); }
队列的弹出操作:
与栈操作一致,当队列为空时,弹出元素为违法操作;队列不为空时,则弹出队首元素。
int Delete(queue* p) { //判断队列中是否为空 if (Empty(p)) { return 0; } //让队首向后一个,含有的数据-1 p->head += 1; p->count -= 1; return p->data[p->head-1]; }
查询队首元素:
对于队列,我们只能查询队首的元素。
//输出队首的数据 int Queue_Front(queue* p) { return p->data[p->head]; }
队列也可以由链表实现,你能构思并且设计一个由链表构成的队列吗?
至此,队列和栈的讲解到此结束。
如果我的文章对你有所帮助,不妨给我个关注何点赞吧。