目录

栈（Stack）

栈的结构体

初始化

销毁

入栈

判空

出栈

取栈顶元素

获取栈个数

测试：

队列（Queue）

队列的结构体

单个结点

队列

初始化

销毁

入队列，队尾

判空

出队列，队头

取队头数据

取队尾数据（非标准操作）

获取队列个数

测试：

---

栈（Stack）

栈是一种特殊的线性表，其只允许在特定的一端进行插入和删除操作。

进行插入和删除操作的一端叫做栈顶

另一端称为栈底

栈中的数据元素遵循后进先出LIFO（Last In First Out ）的原则

压栈：栈的插入操作也被称为进栈、入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈，出数据也在栈顶。

因为栈只在一端进行操作，所以栈的实现使用数组更加优越。

---

栈的结构体

<code>//重命名，方便统一修改

typedef int STDataType;

typedef struct stack {

STDataType* arr;

int capacity;//栈的容量

int top;//栈顶位置（有效元素个数）

}ST;

---

初始化

//初始化

void STInit(ST* ps) {

assert(ps);//不能传入NULL

ps->;arr = NULL;

ps->capacity = ps->top = 0;

}

---

销毁

//销毁

void STDestory(ST* ps) {

assert(ps);//不能传入NULL

if (ps->arr) {//防止对NULL指针的引用（即栈为空的情况）

free(ps->arr);

}

ps->arr = NULL;

ps->capacity = ps->top = 0;

}

---

入栈

//入栈

void STPush(ST* ps, STDataType x) {

assert(ps);

if (ps->capacity == ps->top) {//若空间不足

int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

//若栈容量为0，给定初始值，否则以两倍大小增长

STDataType* p = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));

if (!p) {//申请失败，直接返回

perror("realloc fail!");

exit(1);

}

ps->arr = p;

ps->capacity = newcapacity;//改变原容量大小

}

ps->arr[ps->top++] = x;//先给栈顶赋值，在加加

}

---

判空

//判空

bool STEmpty(ST* ps) {

assert(ps);

return ps->top == 0;//返回bool值，直接返回比较运算符的返回值

}

---

出栈

//出栈

void STPop(ST* ps) {

assert(ps && !STEmpty(ps));//不能传入NULL && 栈为空

ps->top--;//出栈,让栈顶减减

}

---

取栈顶元素

//取栈顶元素

STDataType STTop(ST* ps) {

assert(ps && !STEmpty(ps));//不能传入NULL && 栈为空

return ps->arr[ps->top - 1];//返回栈顶元素，让栈顶减减

}

---

获取栈个数

//获取栈有多少元素

int STSize(ST* ps) {

assert(ps);

return ps->top;//直接返回栈顶下标（即元素个数）

}

---

测试：

---

队列（Queue）

队列也是一种特殊的线性表，其在一端进行插入操作，另一端进行删除操作。

进行插入操作的一端叫做队尾（rear）。

进行删除操作的一端叫做队头（front）。

队列中的数据元素遵循后进先出FIFO（Frist In First Out ）的原则

入队：队列的插入操作，一般发生在队尾

出队：队列的删除操作，一般发生在队头

因为队列在头部删除数据，使用数组，移动数据的时间复杂比较高，所以使用链表更优越。

---

队列的结构体

单个结点

<code>//重命名，方便统一修改

typedef int QDataType;

//队列单个结点结构

typedef struct QueueNode {

QDataType data;//数据

struct QueueNode* next;//下一个结点

}QN;

队列

//队列结构

typedef struct queue {

QN* front;//队头

QN* rear;//队尾

int size;//结点数

}Q;

---

初始化

//初始化队列

void QueueInit(Q* pq) {

assert(pq);

pq->;front = pq->rear = NULL;

pq->size = 0;

}

---

销毁

//销毁

void QueueDestory(Q* pq) {

assert(pq);

assert(!QueueEmpty(pq));//队列为空，不用销毁

QN* pcur = pq->front;

while (pcur) {

QN* next = pcur->next;

free(pcur);//依次释放每一个结点

pcur= next;

}

pq->rear = pq->front = NULL;//置队头队尾

pq->size = 0;

}

---

入队列，队尾

//入队列，队尾

void QueuePush(Q* pq, QDataType x) {

assert(pq);

QN* node = (QN*)malloc(sizeof(QN));//开辟一个新结点

if (!node) {//防止为空

perror("malloc fail!");

exit(1);

}

node->data = x;//data元素

node->next = NULL;//next指针

if (pq->front == NULL) {//若队列为空，队头队尾都要改变

pq->front = pq->rear = node;

}

else {//若不为空,则改变尾结点指向

pq->rear->next = node;

pq->rear = node;

}

pq->size++;//队列元素++

}

---

判空

//判空

bool QueueEmpty(Q* pq) {

assert(pq);

return pq->size == 0;

}

---

出队列，队头

//出队列，队头

void QueuePop(Q* pq) {

assert(pq);

assert(!QueueEmpty(pq));//不能为空

if (pq->front->next == NULL) {//若只有一个元素，队尾的指向也要发生改变

free(pq->front);

pq->front = pq->rear = NULL;

}

else {//若有多个元素，只用改变队头指向

QN* del = pq->front;

pq->front = pq->front->next;

free(del);

del = NULL;

}

pq->size--;

}

---

取队头数据

//取队头数据

QDataType QueueFront(Q* pq) {

assert(pq);

assert(!QueueEmpty(pq));

return pq->front->data;

}

---

取队尾数据（非标准操作）

//取队尾数据

QDataType QueueRear(Q* pq) {

assert(pq);

assert(!QueueEmpty(pq));

return pq->rear->data;

}

---

获取队列个数

//队列有效个数

int QueueSize(Q* pq) {

assert(pq);

return pq->size;

}

---

测试：