【数据结构】——栈|队列（基本功能）
目录
栈
基本概念
栈的常见基本操作
栈的存储
✌栈的基本操作实现
栈的构建
栈的初始化
入栈
打印栈
出栈
获取栈顶元素
获取栈的有效元素个数
判断栈是否为空
销毁栈
队列
基本概念
队列的常见基本操作
✌队列的基本操作实现
队列的构建
初始化
入队列
出队列
获取头部元素
获取队尾元素
获取有效元素个数
判断是否为空
销毁队列
栈
基本概念
定义： 是只允许在一端进行插入或删除的线性表；
栈顶：线性表允许进行插入删除的那一端。
空栈：不含任何元素的空表。栈是先进后出的的线性表
栈的常见基本操作
InitStack(&S)： 初始化一个空栈S。
StackEmpty(S)： 判断一个栈是否为空，若栈为空则返回true，否则返回false。
Push(&S, x)： 进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶。
Pop(&S, &x)： 出栈（栈的删除操作），若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(S, &x)： 读栈顶元素，若栈S非空，则用x返回栈顶元素。
DestroyStack(&S)： 栈销毁，并释放S占用的存储空间（“&”表示引用调用）。
栈的存储
栈的存储方式有两种：顺序栈和链栈，即栈的顺序存储和链式存储。
采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的元素，同时附设一个指针（top）指示当前栈顶的位置。
✌栈的基本操作实现
栈的构建
因为使用的是顺序栈，所以可以定义动态增长的数组，既然是数组了，自然有空间是否足够的问题，所以要定义个容量 capacity，栈顶top
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
int top; // 栈顶
int capacity; // 容量
}Stack;栈的初始化
这里的top可以定义成0或者-1，不过后面的操作需要稍微变化；
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
assert(ps);
ps->arr = NULL;
ps->capacity = 0;
ps->top = -1; //表示栈顶元素
}入栈
这里注意top的不同，因为是顺序栈，所以要检查容量是否足够
// 入栈
void StackPush(Stack* ps, STDataType data)
{
//检查容量
if (ps->top + 1 == ps->capacity) //top表示的是栈顶元素，先++top,再插入的，所以检查+1位置是否可用
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* newnode = (STDataType*)realloc(ps->arr,sizeof(STDataType) * newcapacity);
assert(newnode); //七匹狼式检查是否开辟成功
ps->arr = newnode;
ps->capacity = newcapacity;
}
ps->top++;
ps->arr[ps->top] = data;
}打印栈
//打印
void StackPrint(Stack* ps)
{
assert(ps);
int i = ps->top;
while (i>=0)
{
printf("%d ", ps->arr[i]);
i--;
}
printf("\n");
}出栈
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top >= 0);
ps->top--;
}获取栈顶元素
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top >= 0);
return ps->arr[ps->top];
}获取栈的有效元素个数
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
assert(ps->top >= 0);
return ps->top + 1;
}判断栈是否为空
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps)
{
assert(ps);
if (ps->top < 0) //为空
{
return true;
}
else
{
return false;
}
}
销毁栈
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
ps->capacity = 0;
ps->top = -1;
free(ps->arr);
ps->arr = NULL;
}队列
基本概念
定义：队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
队列的常见基本操作
InitQueue(&Q)： 初始化队列，构造一个空队列Q。
QueueEmpty(Q)： 判队列空，若队列Q为空返回true，否则返回false。
EnQueue(&Q, x)： 入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q, &x)： 出队，若队列Q非空，删除队头元素，并用x返回。
GetHead(Q, &x)： 读队头元素，若队列Q非空，则将队头元素赋值给x。
✌队列的基本操作实现
队列的构建
typedef int QueueDataType;
// 链式结构：表示队列
typedef struct QueueNode
{
QueueDataType val;
struct QueueNode* next;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* head;
QNode* tail;
int size; //队列的长度大小
}Queue;初始化
// 初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
pq->size = 0;
}入队列
// 队尾入队列
void QueuePush(Queue* pq, QueueDataType data)
{
assert(pq);
//开辟空间
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL) //检查是否开辟成功
{
perror("malloc fail");
return;
}
newnode->val = data;
newnode->next = NULL;
if (pq->tail == NULL) //空队列情况
{
pq->tail = pq->head = newnode;
}
else
{
pq->tail->next = newnode; //链接新结点
pq->tail = newnode; //队尾 更新位置
}
pq->size++; //长度+
}出队列
// 队头出队列
void QueuePop(Queue* pq)
{
assert(pq);
QNode* tmp = pq->head;
pq->head = pq->head->next;
free(tmp);
tmp = NULL;
if (pq->head == NULL) //此时链表已经为空，队尾tail是野指针
{
pq->tail = NULL;
}
pq->size--;
}获取头部元素
// 获取队列头部元素
QueueDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head); //检查队头，不为空说明有数据存放
return pq->head->val;
}获取队尾元素
// 获取队列队尾元素
QueueDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail); //检查队尾，不为空说明有数据存放
return pq->tail->val;
}获取有效元素个数
// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}判断是否为空
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}销毁队列
// 销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* tmp = pq->head;
while (tmp)
{
QNode* next = tmp->next;
free(tmp);
tmp = NULL;
tmp = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
