一.栈

 关于内存中的栈和数据结构中的栈是不同的，本章着重讲的是数据结构的栈。

 这是一张关于栈的表达图。从图中可以看出栈很像是一副卡牌，发牌时只能从上取出，即出栈。

而入栈则是像你出牌后，要把你出的牌压在上一张出的牌上面。这是入栈。

栈可以用链表或者顺序表实现，这里采用的是顺序表的结构。

1.栈的头文件 

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int StackDatatype;
typedef struct Stack
{StackDatatype* data;int capacity;int Top;
}ST;
void STPush(ST* pst, StackDatatype x);
void StackInit(ST* pst);
void StackDestroy(ST* pst);
void Push(ST* pst, StackDatatype x);
void Pop(ST* pst);
StackDatatype StackTop(ST* pst);
int StackSize(ST* pst);
bool StackEmpty(ST* pst);

 2.栈的初始化

void StackInit(ST* pst)
{assert(pst);pst->capacity = 0;pst->data = NULL;pst->Top = -1;
}

这里的pst->Top可以用-1，或者0.用-1的话后续你的pst->Top 所代表的下标就是栈顶元素。

如果用0 那pst-Top 之后的下标就是栈顶元素的下一个位置。这里可以自己考虑，代码的多样性。 （本章采用的是-1 的写法）

3.栈的插入

void Push(ST* pst, StackDatatype x)
{assert(pst);pst->Top++;JudgeCapacity(pst);pst->data[pst->Top] = x;
}

栈的插入就是入栈，top++ 是pst->top 指向当前即将插入元素的位置（栈顶的位置）。

后面在判断pst中的容量，不够需要扩容。把x 插入栈顶位置。 

4.栈的取出

void Pop(ST* pst)
{assert(pst);assert(pst->Top > -1);pst->Top--;
}

和顺序表一样只要 top--即可，不用删除，因为top -- 以后，你下次在使用该位置的时候，其实就是把原来这个位置的元素更改就可以了，不需要删除。

5.栈的栈顶元素

StackDatatype StackTop(ST* pst)
{assert(pst);return pst->data[pst->Top];
}

 这个函数的存在意义就是取当前的栈顶元素的值。

6.栈的元素个数

int StackSize(ST* pst)
{assert(pst);return pst->Top+1;
}

因为我们的Top 用的是-1开头，所以,当它指向第一个元素的时候，这时候Top == 0， 所以加一。

7.栈的判空

bool StackEmpty(ST* pst)
{assert(pst);return pst->Top == -1;
}

判断栈此时是否为空，用pst- top == -1 的判断表达式返回即可。 

8.栈的销毁

void StackDestroy(ST* pst)
{assert(pst);free(pst->data);pst->data = NULL;pst->capacity = 0;pst->Top = -1;
}

因为栈是创建出来的一个空间。所以最后要将这段空间free，并将所有数据都置空 

栈的容量判断

void JudgeCapacity(ST* pst)
{assert(pst);if (pst->capacity == pst->Top){int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;StackDatatype* tmp = (StackDatatype*)realloc(pst->data, sizeof(StackDatatype) * newcapacity);if (tmp == NULL){perror("malloc failed!");return;}pst->data = tmp;pst->capacity = newcapacity;}
}

 和顺序表的容量判断一样，有兴趣的可以直接去看我的顺序表详解，这里给大家简单的说一下，用三目表达式判断并赋值newcapacity，然后扩容pst->data这一段空间。

最后把扩容好的空间地址给到tmp，newcapacity给到原来的capacity。

二.队列

 上图是队列的表达图，队列如字意就像是排队一样，先进入的人，就先获得服务。

所以 队列和 栈的不同点就是出栈和出队，队列出的是头元素，而栈出的是尾元素（栈顶）

对比入队和 入栈两者相似都是尾插。

，还有队列用的是链表，栈用的是顺序表。

1.队列的头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QeDataType;
typedef struct QueueNode
{struct QueueNode* next;QeDataType data;
}Qnode;
typedef struct Queue
{Qnode* head;Qnode* back;
}Qe;
void QueueInit(Qe* q);
void QueueDestroy(Qe* q);
void Queuepush(Qe* q, QeDataType x);
void QueuePop(Qe* q);
QeDataType QueueFront(Qe* q);
QeDataType QueueBack(Qe* q);
int QueueSize(Qe* q);
bool QueueEmpty(Qe* q);

 相比栈 队列多用了一个typedef 原因是，队列要记录头元素和尾元素。因为入队入的在尾部，出队出的是头部

2.队列的初始化

void QueueInit(Qe* q)
{assert(q);Qnode* newnode = CreateNode(-1);q->head = newnode;q->back = newnode;
}

 这里采用的是有头结点的队列，当然没有头结点（哨兵位）也是可以的，根据个人喜好选择。

初始化创立一个头结点（哨兵位）后，头指针和尾指针都指向头结点（哨兵位）

3.队列的插入

void Queuepush(Qe* q, QeDataType x)
{assert(q);Qnode* newnode = CreateNode(x);q->back->next = newnode;q->back = newnode;
}

 关于队列的插入，就是链表的尾插，如果链表还没明白的朋友，可以去看我之前关于单链表的博客。

4.队列的取出

void QueuePop(Qe* q)
{assert(q);assert(q->head->next);Qnode* next = q->head->next;q->head->next = next->next;free(next);next = NULL;if (q->head->next == NULL){q->back = q->head;q->back->next = NULL;}
}

关于队列的取出，实质上就是链表的头删。 

5.队列的头元素

QeDataType QueueFront(Qe* q)
{assert(q);assert(q->head->next);return q->head->next->data;
}

 队列的头元素返回就是返回哨兵位后的第一个节点的数据。因为要返回数值，所以这个第一个节点不能为空，用assert断言。

6.队列的尾元素

QeDataType QueueBack(Qe* q)
{assert(q);assert(q->head->next);return q->back->data;
}

 既然要返回尾元素的数据，那就是用到尾指针，当然链表第一个节点不能为空。

7.队列的元素个数

int QueueSize(Qe* q)
{Qnode* size = q->head->next;int num = 0;while (size){size = size->next;num++;}return num;
}

队列的元素个数，就把链表遍历一遍，用num记录遍历次数，就是元素个数。 

8.队列的判空

bool QueueEmpty(Qe* q)
{return q->head->next == NULL;
}

 队列的判空就是判断第一个节点是否为空，return 一个 表达式即可，也可以用if else 语句。因人而异。

创造一个节点

Qnode* CreateNode(QeDataType x)
{Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));newnode->data = x;newnode->next = NULL;return newnode;
}

 创造一个节点在链表的初始化和插入都会用到，在之前链表的那篇博客有讲到，偏简单。