数据结构——队列和栈
目录
一、栈
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;
//初始栈的容量为4
stack->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;
//初始队列中元素个数为0
queue->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) 全球极客挚爱的技术成长平台