@TOC
一、栈
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; }
