我们在学习完顺序表和链表之后，进一步学习其他更复杂的数据结构。这一章我们来学习栈和队列以及他们的实现，因为结构上的相似，我们会用到上一章讲到的顺序表和链表的部分思想。
目录
一、栈
1、栈的概念和结构
出栈演示图：
栈严格符合先进后出的原则。
2、C语言实现栈
我们可以使用顺序表实现栈，也可以使用链表实现栈。对比两种结构，我们发现顺序表尾插尾删所付出的代价更小。
第一步我们要创建一个栈的结构，这里我们创建一个可以动态增长的栈：
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;如果我们需要改变数据类型，改STDataType所再定义的类型即可，capacity代表容量以便我们后面动态增长容量。
第二步我们站在大局观上考虑我们要实现什么功能：
//初始化
void StackInit(ST* ps);
//销毁
void StackDestory(ST* ps);
//数据入栈
void StackPush(ST* ps, STDataType x);
//数据出栈
void StackPop(ST* ps);
//栈顶的数据
STDataType StackTop(ST* ps);
//栈的大小
int StackSize(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);第三步我们根据上面为依据，来一一实现：
栈的初始化：
void StackInit(ST* ps)
{
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}栈的销毁：
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}上面是最基本的栈的创建和销毁。
数据入栈：
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 :ps->capacity*2;
STDataType* tmp = realloc(ps->a,sizeof(STDataType) * newcapacity);
if(tmp==NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}入栈我们先要判断栈的容量是否够，用if语句判断，如果不够就开辟空间，然后新的数据存放在顺序表尾。
数据出栈：
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}出栈我们只需要删除顺序表最后一个元素，也就是数组下标减去1，这样数组的容量大小减1，这样原本的最后一个元素所占有的空间自然就还给内存了。
返回栈顶的数据：
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top-1];
}
由于我们初始化的top的值为0，每存放一个top就加1.比如我们此时只存放一个数据，这是顺序表中最后一个数据就是a[0]，而top从0加到1了，所以我们要找最后一个元素所在的下标就是top-1.
栈的大小：
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}大小比最后顺序表的下标要大1，所以直接返回top就行。
判断栈是否为空：
bool StackEmpty(ST* ps)
{
assert(ps);
/*if (ps->top == 0)
{
return true;
}
else
{
return false;
}*/
return ps->top == 0;
}我们可以用if语句判断，也可以直接用ps->top==0这个表达式返回的值进行判断。
二、队列
1、队列的概念和结构
队列演示图：
从队尾进，队头出，先进先出。
2、C语言实现队列
同样我们可以使用顺序表和链表来实现队列。对比之后，我们发现出队列要头删，顺序表不适用头删，而链表实现头删付出的代价很小，所以我们利用链表的结构来实现队列。
第一步我们也是创建队列的结构：
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct Queue* next;
}QueueNode;
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;队列的结点我们创建一个data存放数据，next存放下一个结点的地址。我们再创建Queue结构体存放这个链表的头和尾，这样便于我们找到队列的头数据和尾数据。
第二步我们也整体来看我们需要实现什么标准：
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//返回队头数据
QDataType QueueFront(Queue* pq);
//返回队尾数据
QDataType QueueBack(Queue* pq);
//返回队列长度
int QueueSize(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);第三步我们根据上述的总体规划来一一实现：
队列的初始化：
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}队列的初始化我们只需要将头尾结点初始化为NULL。
队列的销毁：
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* next = pq->head->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
我们用next存放cur下一个结点的位置，然后free掉cur结点，然后把next赋给cur，next再往下找下一个结点，以此类推，释放掉整个链表。
数据入队：
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
newnode->data = x;
newnode->next = NULL;
if(pq->head==NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}数据入队我们按照链表结构我们首先要找到队尾，但是我们对队列初始化时设置了tail来存放队尾的位置，所以直接开辟空间把新结点尾插到链表尾就可以了。
数据出队：
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
if (pq->head == NULL)
{
pq->tail = NULL;
}
}出队只需要头删即可，注意考虑一些特殊情况。
返回队头和队尾数据：
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
返回队列长度：
int QueueSize(Queue* pq)
{
assert(pq);
int n = 0;
QueueNode* cur = pq->head;
while (cur)
{
n++;
cur = cur->next;
}
return n;
}判断队列是否为空：
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}只需要判断pq->head==NULL这个式子的返回值即可。
本篇文章就介绍到这，下篇我们会详解栈和队列的OJ题。