【数据结构】栈和队列
文章目录
栈
一、栈的概念及结构
栈一种特殊的线性表，它只允许在固定的一端进行插入和删除元素操作；进行数据插入和删除操作的一端称为栈顶，另一端称为栈底；栈中的数据元素遵守后进先出 LIFO（Last In First Out）的原则；
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶；出栈：栈的删除操作叫做出栈，出数据也在栈顶；
注意：不要把栈区和栈混为一谈：栈区是内存划分的一块区域，属于操作系统学科；而栈是用于管理数据的一种结构，它在堆区上申请空间，属于数据结构学科。
栈的概念相关选择题
1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出 栈的顺序是（ ）
A 12345ABCDE B EDCBA54321 C ABCDE12345 D 54321EDCBA
答案：B 这道题很简单，根据栈的后进先出原则，直接就可以得出答案。
2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A 1,4,3,2 B 2,3,4,1 C 3,1,4,2 D 3,4,2,1
答案：C 这道题就需要我们仔细分析了，题目中明确说明了在进栈过程中可以出栈，基于这个原则，我们来对选项进行分析：
A：
B：
C：对于C来说，想要取出3，就必须先push 1 2 3，然后它紧接着取出了1，这是办不到的，想要取出1，必须先取出2；
D：
二、栈的实现
1、栈的结构
栈可以用顺序表实现，也可以用链表实现，我们这里选用顺序表实现，原因如下：
1、栈的插入和删除操作都在栈顶，即在数据的尾部进行，而顺序表在尾部插入和删除数据的效率为O(1)，完美的避开了顺序表的缺陷； 2、顺序表扩容和链表频繁 malloc 在整体上的效率是差不多的，只是顺序表会存在一定的空间浪费； 3、顺序表支持随机访问，且其缓存利用率更高；
综合考虑以上几种因数，我们采用顺序表实现栈；
结构的定义
//结构和符号的定义
#define DEF_SIZE 5 //默认初始化大小
#define CRE_SIZE 2 //默认一次扩容的倍数
typedef int STDataType;//重命名数据类型
typedef struct Stack
{
STDataType* data; //指向动态开辟的数组
int top; //记录栈顶
int capacity; //记录容量，容量满时扩容
}ST;2、初始化栈
//初始化栈
void StackInit(ST* ps)
{
assert(ps);
ps->data = (STDataType*)malloc(sizeof(STDataType) * DEF_SIZE);
if (ps->data == NULL)
{
perror("malloc fail");
return;
}
ps->top = 0;
ps->capacity = CRE_SIZE;
}3、入栈
由于栈只能在栈顶插入元素，所以我们只需要在 push 函数中进行检查容量并扩容的操作，而不需要把 CheckCapacity 单独封装成一个函数。
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//检查是否需要扩容
if (ps->top == ps->capacity)
{
STDataType* ptr = (STDataType*)realloc(ps->data, sizeof(STDataType) * ps->capacity * CRE_SIZE);
if (ptr == NULL)
{
perror("realloc fail");
return;
}
ps->data = ptr;
ps->capacity *= DEF_SIZE;
}
//入栈
ps->data[ps->top] = x;
ps->top++;
}4、出栈
出栈之前我们需要检查栈的容量是否为空。
//出栈
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}5、获取栈顶元素
获取栈顶元素时我们也需要检查栈是否为空，避免造成对空指针的解引用。
//获取栈顶元素
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->data[ps->top - 1]; //数组下标从0开始
}6、获取栈的长度
//获取栈的长度
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}7、判断栈是否为空
//判断栈是否为空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}8、销毁栈
//销毁栈
void StackDestory(ST* ps)
{
assert(ps);
free(ps->data);
ps->data = NULL;
ps->capacity = 0;
ps->top = 0;
}需要注意的是，我们不需要定义栈的打印函数，因为栈不能遍历，如果我们想得到栈顶的前一个元素，我们就必须先把栈顶的元素给删除掉，让后面一个元素变成栈顶。
三、完整代码
1、Stack.h
#pragma once //防止头文件重复包含
//头文件的声明
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
//结构和符号的定义
#define DEF_SIZE 5 //默认初始化大小
#define CRE_SIZE 2 //默认一次扩容的倍数
typedef int STDataType;//重命名数据类型
typedef struct Stack
{
STDataType* data; //指向动态开辟的数组
int top; //记录栈顶
int capacity; //记录容量，容量满时扩容
}ST;
//函数的声明
//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestory(ST* ps);
//入栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//获取栈顶元素
STDataType StackTop(ST* ps);
//获取栈的长度
int StackSize(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);2、Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
//初始化栈
void StackInit(ST* ps)
{
assert(ps);
ps->data = (STDataType*)malloc(sizeof(STDataType) * DEF_SIZE);
if (ps->data == NULL)
{
perror("malloc fail");
return;
}
ps->top = 0;
ps->capacity = CRE_SIZE;
}
//销毁栈
void StackDestory(ST* ps)
{
assert(ps);
free(ps->data);
ps->data = NULL;
ps->capacity = 0;
ps->top = 0;
}
//入栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//检查是否需要扩容
if (ps->top == ps->capacity)
{
STDataType* ptr = (STDataType*)realloc(ps->data, sizeof(STDataType) * ps->capacity * CRE_SIZE);
if (ptr == NULL)
{
perror("realloc fail");
return;
}
ps->data = ptr;
ps->capacity *= DEF_SIZE;
}
//入栈
ps->data[ps->top] = x;
ps->top++;
}
//出栈
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
//获取栈顶元素
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->data[ps->top - 1]; //数组下标从0开始
}
//获取栈的长度
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
//判断栈是否为空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}3、test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
int main()
{
ST st;
//初始化栈
StackInit(&st);
//入栈
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
//栈不能遍历，只能取出；取出一个就pop一个
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
//销毁栈
StackDestory(&st);
return 0;
}大家也可以去我的 Gitee 仓库中获取完整代码：Stack/Stack · 野猪佩奇/日常学习 - 码云 - 开源中国 (gitee.com)
队列
一、队列的概念和结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表；队列中的数据元素遵守先进先出 FIFO（First In First Out）的原则；
入队列：进行插入操作的一端称为队尾；出队列：进行删除操作的一端称为队头。
队列概念相关选择题
以下( )不是队列的基本运算？
A 从队尾插入一个新元素 B 从队列中删除第i个元素 C 判断一个队列是否为空 D 读取队头元素的值
答案：B 队列只能删除队头的数据。
二、队列的实现
1、队列的结构
和栈一样，队列既可以使用顺序表实现，也可以使用链表实现，这里我们使用单链表实现，原因如下：
1、队列需要删除头部的元素，单链表头删的效率为O(1)； 2、使用链表可以按需申请空间，避免了空间的浪费；
但是我们发现使用单链表实现队列存在一个问题，那就是单链表尾插以及计算链表长度的效率都为O(N)，不符合我们的预期，那么我们需要把单链表改造为循环链表吗？可以是可以，但是这样又把队列的结构搞复杂了；所以综合考虑，这里我们增加三个变量，一个用于记录队尾，一个用于记录队头，还有一个用于记录队列的长度。
结构的定义
//符号和结构的定义
typedef int QEDataType;
typedef struct QueueNode //队列的一个节点
{
QEDataType data;
struct QueueNode* next;
}QENode;
typedef struct Queue //队列
{
QENode* head; //记录队列的头
QENode* tail; //记录队列的尾
int size; //记录队列的长度
}Queue;2、初始化队列
//初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}3、从队尾入队列
由于我们使用了一个结构体来记录队列的头和尾，那么这里我们改变队列的头和尾时只需要改变结构体即可，所以只需要传递一级指针；
另外，队列也只能从队尾入数据，所以我们也没有必要单独封装一个 BuyNode 函数。
//队尾入队列
void QueuePush(Queue* pq, QEDataType x)
{
assert(pq);
//创建一个新节点
QENode* newnode = (QENode*)malloc(sizeof(QENode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
//当入第一个元素时，需要改变队列的头
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = pq->tail->next;
}
pq->size++;
}4、从队头出队列
这里我们除了正常的对队列进行判空之外，还有一个需要特别注意的地方：当队列只有一个元素时，我们再次头删虽然会让head指向NULL，但是tail仍然指向头删之前的那个节点，会形成野指针，所以我们这里需要单独判断。
//队头出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//当队列只有一个元素时，我们再次头删虽然会让head指向NULL，但是tail仍然指向头删之前的那个节点，形成野指针，所以我们这里要单独判断
if (pq->head == pq->tail)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QENode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size--;
}5、获取队头元素
//返回队头元素
QEDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}6、获取队尾元素
//返回队尾元素
QEDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}7、获取队列长度
//返回队列长度
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}8、判断队列是否为空
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}9、销毁队列
//销毁队列
void QueueDestory(Queue* pq)
{
assert(pq);
QENode* cur = pq->head;
while (cur)
{
QENode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}注意：和栈一样，队列也不需要定义 print 函数，因为队列也不能遍历，要想取出队头后面的元素，我们必须先 pop 掉之前的元素，让该元素成为队头。
三、完整代码
1、Queue.h
#pragma once //防止头文件重复包含
//头文件的包含
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
//符号和结构的定义
typedef int QEDataType;
typedef struct QueueNode //队列的一个节点
{
QEDataType data;
struct QueueNode* next;
}QENode;
typedef struct Queue //队列
{
QENode* head; //记录队列的头
QENode* tail; //记录队列的尾
int size; //记录队列的长度
}Queue;
//函数的声明
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QEDataType x);
//队头出队列
void QueuePop(Queue* pq);
//返回队头元素
QEDataType QueueFront(Queue* pq);
//返回队尾元素
QEDataType QueueBack(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//返回队列长度
int QueueSize(Queue* pq);2、Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
//初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
//销毁队列
void QueueDestory(Queue* pq)
{
assert(pq);
QENode* cur = pq->head;
while (cur)
{
QENode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
//队尾入队列
void QueuePush(Queue* pq, QEDataType x)
{
assert(pq);
//创建一个新节点
QENode* newnode = (QENode*)malloc(sizeof(QENode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
//当入第一个元素时，需要改变队列的头
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = pq->tail->next;
}
pq->size++;
}
//队头出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//当队列只有一个元素时，我们再次头删虽然会让head指向NULL，但是tail仍然指向头删之前的那个节点，形成野指针，所以我们这里要单独判断
if (pq->head == pq->tail)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QENode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size--;
}
//返回队头元素
QEDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
//返回队尾元素
QEDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
//返回队列长度
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}3、test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
int main()
{
Queue q;
//初始化队列
QueueInit(&q);
//队尾入队列
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
//队列也不能遍历，取出一个元素即代表从队头出一个元素
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
//销毁队列
QueueDestory(&q);
return 0;
}大家也可以去我的 Gitee 仓库中获取完整代码：Queue/Queue · 野猪佩奇/日常学习 - 码云 - 开源中国 (gitee.com)
腾讯云开发者
