数据结构——队列和栈

一、栈

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、入栈

在栈的结构中 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、出栈

在栈的结构中 top 时刻记录着栈顶的位置，直接减少栈中有效元素即可，因此时间复杂度为O（ 1 ）

//栈顶删除元素
void stackpop(struct stack* arr)
{//栈不能为空if (arr->top == 0){return;}//出栈arr->top--;
}

5、取栈顶元素

在栈的结构中 top 时刻记录着栈顶的位置，直接返回即可，因此时间复杂度为O（ 1 ）

//查找栈顶元素
int stacktop(struct stack* arr)
{//栈不能为空if (arr->top != 0){assert("stack is NULL");}//返回栈顶元素return arr->data[(arr->top) - 1];
}

6、取栈中有效元素个数

在栈的结构中 top 时刻记录着栈顶的位置，也是栈中有效元素个数直接返回即可，因此时间复杂度为O（ 1 ）

//查找栈中元素个数
int stacksize(struct stack* arr)
{//查找栈中元素个数return arr->top;
}

7、栈是否为空

判断栈中元素个数是否为零

//判断栈是否为空
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 ）

//队列——插入
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 ）

//队列——删除
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 ）

//队列——返回对头数据
int queuefront(struct queue* list)
{//队列不能为空if (list->head == NULL){assert(list->head);}//返回对头数据return list->head->data;
}

6、取队尾数据

这里有维护尾节点，直接返回头节点数据，因此时间复杂度为O（ 1 ）

//队列——返回队尾数据
int queueback(struct queue* list)
{//队列不能为空if (list->tail == NULL){assert(list->tail);}//返回队尾数据return list->tail->data;
}

7、队列判空

判断队列中的有效元素个数是否为0

//队列——判断队列是否为空
int queueempty(struct queue* list)
{//队列——判断队列是否为空if (list->head == NULL){return 0;}else{return 1;}
}

8、队列中有效元素个数

这里有维护队列中有效元素个数，直接返回，因此时间复杂度为O（ 1 ）

//队列——返回队列有效元素个数
int queuesize(struct queue* list)
{//返回答案return list->size;
}

练习题目链

数据结构最好的巩固就是写算法题目也是最好的体现，学习了不代表学会了，一定要加以实践

20. 有效的括号 - 力扣（LeetCode）

225. 用队列实现栈 - 力扣（LeetCode）

232. 用栈实现队列 - 力扣（LeetCode）

155. 最小栈 - 力扣（LeetCode）

更多的可以在力扣上写：力扣 (LeetCode) 全球极客挚爱的技术成长平台