目录
一、栈
1.栈的定义
2.栈的初始化
3.入栈
4.出栈
5.获取栈顶元素
6.获取栈元素的个数
7.判断栈是否为空
8.销毁栈
二、队列
1.队列的定义
2.入队
3.出队
4.获取队头元素
5.获取队尾元素
6.判断队列是否为空
7.获取队列的元素个数
8.销毁队列
前言：
栈和队列也是一种常见的线性表
一、栈
1.栈的定义
栈：仅限在一端进行插入和删除元素操作。数据插入删除的一端称为栈顶，而另一端称为栈底。
压栈：数据的插入操作。出栈：数据的删除操作。
栈中的数据遵循后进先出(Last In First Out,简称LIFO)的原则。
如图：
栈的存储定义 ：
这里采用的是顺序栈，以动态数组的形式进行存放栈的元素，当栈满时，可以动态的增加栈的容量。
定义一个指针负责指向动态数组，用top来表示栈底，还有就是栈的容量capacity。
代码：
typedef int STDataType;
typedef struct StackNode
{
STDataType* a;
int top; //栈底
int capacity; //栈的容量
}Stack;2.栈的初始化
当栈的存储定义完成后，就开始对栈进行初始化。
代码：
//初始化栈
/*这里采用动态数组来进行模拟栈*/
void InitStack(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0; //指向栈顶的下一个元素
}注意：这里定义的top 是指当top == 0 时 指向栈顶的下一个元素，当然top也可以是-1。这里采用的是top = 0。
3.入栈
当元素入栈时，我们需要先考虑一下栈的容量的问题，例如：栈满或者初次使用栈的情况。
代码：
//入栈
void PushStack(Stack* ps, STDataType x)
{
assert(ps);
//入栈前先检查一下栈的容量
if (ps->capacity == ps->top)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//使用realloc直接为动态数组分配空间
STDataType* tmp = (STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType));
if (tmp == NULL)
{
perror("PushStack->realloc");//出错时提示
return;
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
}
}
//数据压栈
ps->a[ps->top] = x;
ps->top++; //同时指向下个一个栈顶元素
}- 这里当初次入栈时，使用realloc进行动态分配空间，初次使用realloc 时,说明ps->a == NULL，那么这里就相当于malloc进行分配空间。
- 栈满时，不是初次入栈就让原来的栈的容量增加二倍 (2 * ps->capacity）。
- 栈没有满时，就直接入栈，同时top指向下一个栈顶元素。
这里多说一下，如果对于realloc不是很理解，可以转到 realloc详细解析
注意：还有就是作者刚学realloc时，总是忘记对realloc使用sizeof(),直接给出元素个数，却忘记给出其元素的大小了。 所以不要忘记sizeof()
4.出栈
出栈需要注意的就是：当栈空了，就不能进行出栈了，这里采用断言assert来避免
代码：
//出栈
void PopStack(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--; //栈顶减一即可
}5.获取栈顶元素
这里也要注意栈为空的情况
代码：
//获取栈顶元素
STDataType TopStack(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}如图：
6.获取栈元素的个数
因为top是从0开始的，下标：0 到 top-1，就相当于有top个元素。
代码：
//获取栈元素的个数
int SizeStack(Stack* ps)
{
assert(ps);
return ps->top;
}
7.判断栈是否为空
这里采用bool 返回类型，如果为空就返回的是true ，不为空就返回false。
//判断栈是否为空,空返回true,非空返回false
bool EmptyStack(Stack* ps)
{
assert(ps);
return ps->top == 0;
}8.销毁栈
为避免内存泄漏，我们应该养成及时释放内存的好习惯。
代码：
//销毁栈
void DestroyStack(Stack* ps)
{
assert(ps);
free(ps->a); //释放指向的动态数组
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}二、队列
1.队列的定义
队列：只允许一端进行插入元素(队尾)，另一端机进行删除元素(队头)的线性表。
进队：数据的插入操作 出队：数据的删除操作
队列中的数据遵循先进先出(First In First Out,简称FIFO)的原则。
如图：
队列的存储定义： 这里是通过单链表的形式来进行模拟队列。同时定义两个指针来进行控制，一个指向队头，另一个指向队尾。这样就可以避免再从头开始遍历链表来找尾了。
代码：
typedef int QDataType;
//通过单链表来模拟队列
typedef struct QueueNode
{
QDataType val;
struct QueueNode* next; //记录下一个结点的地址
}QueueNode;
typedef struct Queue
{
QueueNode* phead; //指向队头的指针
QueueNode* tail; //指向队尾的指针
int size; //同时记录栈元素的个数
}Queue;2.入队
元素入队，通过单链表进行尾插来模拟队列的入队。
在入队的操作中，采取使用malloc动态内存函数来开辟内存空间存放元素。因为是尾插，所以这里我们就要提前判断一下是否为第一次入队(尾插)，当然这里也可以不用判断(前提就是要有头结点)。 因为这里没有用头结点，所以需要判断一下。
代码：
//入队
void PushQueue(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL )
{
perror("PushQueue->malloc");
return;
}
newnode->val = x;
newnode->next = NULL;
//判断是否为第一次进行入队
if (pq->phead == NULL)
{
//第一次入队
pq->phead = pq->tail = newnode;
}
else
{
//不是第一次入队直接进行尾插
pq->tail->next = newnode;
}
pq->size++;//队列元素加一
}3.出队
元素出队，这里通过单链表的头删进行模拟出队。出队需要注意的是队列不能为空那个，所以这里使用assert来断言进行避免
代码：
//出队
void PopQueue(Queue* pq)
{
assert(pq);
assert(pq->phead);
QueueNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
//当出队最后一个元素时
//出完队后，headz指向空，而tail却变成了访问野指了
//所以这里要对删的是最后一个元素进行单独处理
if (pq->phead == NULL)
{
pq->tail = NULL;
}
pq->size--;
}4.获取队头元素
需要注意的是：队为空的情况。使用assert断言来避免
代码：
//获取队头元素
QDataType TopQueue(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}5.获取队尾元素
当然这里也要避免队尾为空的情况
代码：
//获取队尾元素
QDataType TailQueue(Queue* pq)
{
assert(pq);
assert(pq->tail);
return pq->tail->val;
}6.判断队列是否为空
队列为空就返回true,否则返回false
代码：
//判断队列是否为空
bool EmptyQueue(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}7.获取队列的元素个数
返回size
代码：
//获取队列元素的个数
int SizeQueue(Queue* pq)
{
assert(pq);
return pq->size;
}8.销毁队列
代码：
//销毁队列
void DestroyQueue(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->phead;
while (cur)
{
QueueNode* next = cur->next; //记录下一个结点
free(cur);
cur = next;
}
pq->phead = pq->tail = 0;
pq->size = 0;
}
