目录
一、栈
1、概念与结构
2、栈的结构与初始化
3、入栈
4、出栈
5、取栈顶元素
6、取栈中有效元素个数
7、栈是否为空
二、队列
1、概念与结构
2、队列的结构与初始化
3、入队列
4、出队列
5、取队头数据
6、取队尾数据
7、队列判空
8、队列中有效元素个数
练习题目链
一、栈
1、概念与结构
栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作，进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。
栈的底层逻辑实现，可以是使用顺序表实现也可以使用链表表实现，我这里采用的是动态顺序表实现
栈的实现⼀般可以使⽤数组或者链表实现，相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊数据的代价⽐较⼩
2、栈的结构与初始化
// 栈——后进先出
struct stack
{int* data;//栈int top;//栈顶元素位置int capacity;//栈的容量
};//栈初始化
void stackinit(struct stack* stack)
{//设置栈顶位置stack->top = 0;//初始栈的容量为4stack->capacity = 4;//创建数组stack->data = (int*)malloc(sizeof(int) * stack->capacity);
}3、入栈
时间复杂度：O（ 1 ）
在栈的结构中 top 时刻记录着栈顶的位置，直接插入即可，因此时间复杂度为O（ 1 ）
注意在插入前要检查栈是否已经满了，如果满了要扩容
//栈顶插入元素
void stackpush(struct stack* stack, int x)
{//判断是否需要扩容if (stack->top == stack->capacity){//扩容至当前栈容量的两倍stack->capacity = stack->capacity * 2;//更新栈int* newstack = (int*)realloc(stack->data, sizeof(int) * stack->capacity);//创建失败if (newstack){assert("error");}stack->data = newstack;}//栈顶插入元素stack->data[stack->top] = x;//栈顶加一stack->top++;
}4、出栈
时间复杂度：O（ 1 ）
在栈的结构中 top 时刻记录着栈顶的位置，直接减少栈中有效元素即可，因此时间复杂度为O（ 1 ）
//栈顶删除元素
void stackpop(struct stack* arr)
{//栈不能为空if (arr->top == 0){return;}//出栈arr->top--;
}5、取栈顶元素
时间复杂度：O（ 1 ）
在栈的结构中 top 时刻记录着栈顶的位置，直接返回即可，因此时间复杂度为O（ 1 ）
//查找栈顶元素
int stacktop(struct stack* arr)
{//栈不能为空if (arr->top != 0){assert("stack is NULL");}//返回栈顶元素return arr->data[(arr->top) - 1];
}6、取栈中有效元素个数
时间复杂度：O（ 1 ）
在栈的结构中 top 时刻记录着栈顶的位置，也是栈中有效元素个数直接返回即可，因此时间复杂度为O（ 1 ）
//查找栈中元素个数
int stacksize(struct stack* arr)
{//查找栈中元素个数return arr->top;
}7、栈是否为空
时间复杂度：O（ 1 ）
判断栈中元素个数是否为零
//判断栈是否为空
int stackempty(struct stack* arr)
{//判断栈是否为空if (arr->top != 0){return 1;}else{return 0;}
}二、队列
1、概念与结构
队列：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
⼊队列：进⾏插⼊操作的⼀端称为队尾
队列也可以数组和链表的结构实现，使⽤链表的结构实现更优⼀些，因为如果使⽤数组的结构，出队列在数组头上出数据，效率会⽐较低，这里我使用链表实现
2、队列的结构与初始化
//队列节点
struct queuenode
{int data;//存储数据struct queuenode* next;//下一个元素的地址
};
//队列，维护队列的队尾和对头
struct queue
{struct queuenode* head;//队头struct queuenode* tail;//队尾int size;//队列有效元素个数
};
//队列初始化
void queueinit(struct queue* queue)
{//初始为空queue->head = NULL;queue->tail = NULL;//初始队列中元素个数为0queue->size = 0;
}3、入队列
时间复杂度：O（ 1 ）
我们有维护队列的尾节点，创建一个新节点在尾节点后插入同时更新尾节点的指向 ，因此时间复杂度为O（ 1 ）
//队列——插入
void queuepush(struct queue* list, int x)
{//创建队列节点，并初始化struct queuenode* node = calloc(1, sizeof(struct queuenode));node->data = x;node->next = NULL;//队列中没有元素时，对头和队尾都为新创建的节点if (list->head == NULL){list->head = node;list->tail = node;}else{//队尾的下一个节点为新创建的节点list->tail->next = node;//更改队尾节点的指向list->tail = node;}//队列有效元素个数加一list->size++;
}4、出队列
时间复杂度：O（ 1 ）
删除头节点，并更新头节点为头节点的下一个节点， 因此时间复杂度为O（ 1 ）
//队列——删除
void queuepop(struct queue* list)
{//队列不能为空if (list->head == NULL){assert(list->head);}//保存对头的下一个节点struct queuenode* cur = list->head->next;//删除队头free(list->head);//更改对头的指向list->head = cur;//当对头为空时，队尾也要为空if (cur == NULL){list->tail = NULL;}//队列有效元素减一list->size--;
}5、取队头数据
时间复杂度：O（ 1 ）
这里有维护头节点，直接返回头节点数据，因此时间复杂度为O（ 1 ）
//队列——返回对头数据
int queuefront(struct queue* list)
{//队列不能为空if (list->head == NULL){assert(list->head);}//返回对头数据return list->head->data;
}6、取队尾数据
时间复杂度：O（ 1 ）
这里有维护尾节点，直接返回头节点数据，因此时间复杂度为O（ 1 ）
//队列——返回队尾数据
int queueback(struct queue* list)
{//队列不能为空if (list->tail == NULL){assert(list->tail);}//返回队尾数据return list->tail->data;
}7、队列判空
时间复杂度：O（ 1 ）
判断队列中的有效元素个数是否为0
//队列——判断队列是否为空
int queueempty(struct queue* list)
{//队列——判断队列是否为空if (list->head == NULL){return 0;}else{return 1;}
}8、队列中有效元素个数
时间复杂度：O（ 1 ）
这里有维护队列中有效元素个数，直接返回，因此时间复杂度为O（ 1 ）
//队列——返回队列有效元素个数
int queuesize(struct queue* list)
{//返回答案return list->size;
}练习题目链
数据结构最好的巩固就是写算法题目也是最好的体现，学习了不代表学会了，一定要加以实践
20. 有效的括号 - 力扣（LeetCode）
225. 用队列实现栈 - 力扣（LeetCode）
232. 用栈实现队列 - 力扣（LeetCode）
155. 最小栈 - 力扣（LeetCode）
更多的可以在力扣上写： 力扣 (LeetCode) 全球极客挚爱的技术成长平台
![[C++进阶数据结构]红黑树(半成品)](https://i-blog.csdnimg.cn/direct/1cdb43948d674a4a85f864b7f90b9b6e.png)
