栈是一种特性的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈：栈的插入操作也可叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。
总结：从上面的入栈、出栈可以看出栈的“后进先出”的特点，也就是后面进栈的元素会先出栈，而先进栈的元素会后出栈。
栈的实现方式有两种，一种是采用单链表的方式，另一种是采用顺序表的方式（数组），若采用单链表的方式，入栈、出栈的操作采用单链表的头插、头删的方式即可满足栈的后进先出的要求。若采用顺序表（数组）的方式，数组的尾插、尾删操作也可以满足栈的后进先出要求。相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小。
typedef int STDataType;//栈内的数据类型为int类型
typedef struct Stack
{
STDataType* _a;//定义一个动态数组
int _top;//栈顶下标
int _capacity;//数组的容量
}Stack;//1、初始化栈
void StackInit(Stack* pst)
{
assert(pst);
pst->_a = NULL;
//若栈顶初始化为0，则top指向的是栈顶的下一个元素，入栈时先插入元素，再++top;
//若栈顶初始化为-1，则top指向的是栈顶的元素，入栈时先++top，再插入元素；
pst->_capacity = pst->_top = 0;
}//2、销毁栈
void StackDestroy(Stack* pst)
{
assert(pst);
free(pst->_a);
pst->_a = NULL;
pst->_capacity = pst->_top = 0;
}入栈即往栈中插入元素，在插入元素之前要考虑是否需要扩容，当top==capacity时，表明栈的空间已经满了，此时需要扩容；如果不需要扩容，将元素插入到栈顶位置即可。
//3、入栈
void StackPush(Stack* pst, STDataType val)
{
assert(pst);
//插入数据前，先判断空间是否足够
if (pst->_capacity == pst->_top)
{
//先判断数组的容量是否为0，如果容量为0，则初始空间为4个大小；
//如果不为0，将空间扩容为原来的2倍
int newCapacity = pst->_capacity == 0 ? 4 : 2 * pst->_capacity;
STDataType* tmp = (STDataType*)realloc(pst->_a, sizeof(STDataType) * newCapacity);
//扩容失败，打印错误信息
if (tmp == NULL)
{
perror("StackCreateCapacity:realloc");
exit(-1);
}
pst->_a = tmp;
pst->_capacity = newCapacity;
}
pst->_a[pst->_top] = val;//向栈顶插入元素
++pst->_top;
}出栈即删除栈顶元素，只需要将top--即可（后面再插入的数据会覆盖原来的数据），但是在删除栈顶元素时还需要考虑栈内是否有数据，通过判断top的值即可；top==0表示无数据。
//4、出栈
void StackPop(Stack* pst)
{
assert(pst);
//判断栈内是否有元素
assert(pst->_top != 0);
--pst->_top;
}栈内的数据个数即是 top 的值，返回即可。
//5、获取栈内数据的个数
int StackSize(Stack* pst)
{
assert(pst);
return pst->_top;
}栈为空就返回 true，否则返回 false。
//6、判断栈是否为空，返回1是空，返回0是非空
bool StackIsEmpty(Stack* pst)
{
assert(pst);
//若栈为空则pst->_top == 0,此时pst->_top == 0为true
//若栈不为空则pst->_top != 0,此时pst->_top == 0为false
return pst->_top == 0;
}top指向的是栈顶元素的下一个位置，故top-1就是栈顶元素的下标。
//7、获取栈顶的数据
STDataType StackTop(Stack* pst)
{
assert(pst);
assert(pst->_top != 0);//当栈里没有数据时，访问pst->_a[pst->_top-1]的元素时会越界访问
return pst->_a[pst->_top - 1];
}队列也是一种线性表，队列只允许在一端进行插入操作，而在另一端进行删除操作，队列具有先进先出的特征；进行插入操作的一端叫做队尾，即入队列；进行删除操作的一端叫做队头，即出队列。
队列的实现方式也有两种，一种是采用顺序表（数组）的方式；另外一种是采用链表的方式。使用链表的结构实现更优一些，因为如果使用数组的结构，出队列是在数组头上出数据，效率会比较底。队列是在队头和队尾进行元素的删除和插入操作，所以定义队列时需要记录头指针(head)和尾指针(tail)。
与链表的结构一样，队列也是由一个一个的节点构成，所以队列需要定义两个结构体；一个结构体用来表示队列中的每一个节点；另外一个结构体用来记录队列的队头指针、队尾指针以及队列中节点的个数。
//队列结构的构建
typedef int QDataType;//将数据类型重定义方便以后修改
//队列的节点
typedef struct QueueNode
{
QDataType _data;
struct QueueNode* _next;
}QueueNode;
//队列的队头和队尾指针
typedef struct Queue
{
QueueNode* _head;//指向队头的指针
QueueNode* _tail;//指向队尾的指针
int _size;//记录队列中节点的个数
}Queue;队列的初始化，将队列结构体中的队头、队尾指针置为空，队列中节点的个数置为0即可。
//1、队列的初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->_head = NULL;
pq->_tail = NULL;
pq->_size = 0;
}
//2、销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
while (pq->_head)
{
QueueNode* cur = pq->_head;
pq->_head = pq->_head->_next;
free(cur);
cur = NULL;
}
pq->_tail = NULL;
pq->_size = 0;
}往队列中插入数据相当于链表中的尾插，在往队列中插入第一个元素时需要单独考虑，入下图所示。
当插入第一个元素时，队头指针_head和队尾指针_tail都指向第一个元素。
向队列中连续插入节点1、2、3、4，并观察队头指针_head和队尾指针_tail以及_size的变化。
代码实现：
//3、进队列
void QueuePush(Queue* pq, QDataType val)
{
assert(pq);
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
if (newNode == NULL)
{
perror("QueuePush:malloc");
exit(-1);
}
newNode->_data = val;
newNode->_next = NULL;
//在队列的队尾插入数据分两种情况：1、队列为空；2、队列不为空
if (pq->_head == NULL)
{
//若队列为空，则队头指针和队尾指针均指向新插入的节点
pq->_head = pq->_tail = newNode;
}
else
{
//若队列不为空，直接将节点插入的队尾指针的next位置
pq->_tail->_next = newNode;
pq->_tail = newNode;
}
++pq->_size;//每插入一个节点_size都要++
}队列删除数据对应到链表上来说，就是链表的头删，当_size==0时（即队列中没有数据了）不能进行删除操作。
从上面的顺序可以看出队列的入队可出队顺序：
入队顺序：1、2、3、4；出队顺序：1、2、3、4。
//4、出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->_head);//队头指针不为空，即队列中有节点
QueueNode* cur = pq->_head;//记录当前要删除的节点
pq->_head = pq->_head->_next;//头节点往后走
//如果队列中只有一个节点，头节点完后走便指向了NULL
//此时队尾节点_tail还指向原来的节点，所以将_tail也置为空，
//否则_tail指针便成为了野指针
if (pq->_head == NULL)
{
pq->_tail = NULL;
}
free(cur);
cur = NULL;
--pq->_size;
}//5、获取队头的数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->_head);//队头指针不为空，即队列中有节点
return pq->_head->_data;
}
//6、获取队尾的数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->_tail);
return pq->_tail->_data;
}//7、检测队列是否为空，为空返回true，不为空返回false
bool QueueIsEmpty(Queue* pq)
{
assert(pq);
return pq->_size == 0;
}//8、获取队列中有效元素的个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->_size;
}栈和队列实现的完整代码如下：栈的实现、队列的实现。