栈和队列在计算机科学中或许是最基本的两个数据结构，在实际中有着广泛的用途。
栈和队列各有不同的性质，又各自有不同的实现方法，下面对栈和队列的性质、实现和常见应用做详细说明。
栈
栈模型
栈(stack)是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶(top)。
栈具有后进先出(LIFO)的性质。对栈的基本操作有进栈(Push)和出栈(Pop)，前者在栈顶插入一个元素，后者从栈顶删除一个元素。栈顶元素可以通过使用Top()函数进行观察，栈顶的元素是唯一可见的元素。
栈的实现
由于栈是一个表，所以任何实现表的方法都能实现栈。
基于链表实现
栈的第一种实现方法是使用单链表。考虑到单链表找尾的效率较低，这里将表的前端作为栈顶，通过头插来实现栈的Push，通过头删来实现栈的Pop。由于要频繁地进行头插、头删操作，所以要创建一个哑结点(dummy node)以避免频繁修改单链表的头指针。
链表实现不需要考虑空间扩容时效率变低的问题，但这种实现方法的缺点在于对malloc和free的频繁调用的开销是昂贵的，因而效率不如数组。链表实现的栈可以提供更加稳定的效率表现。
基于数组实现
栈的数组实现是较常见的一种做法。将数组的尾部作为栈顶，每个栈有一个topOfStack，用以记录栈顶元素的位置，入栈时，topOfStack自增 1，出栈时，topOfStack自减 1。
需要注意的是 topOfStack的初始值，若将空栈的 topOfStack 初始化为0，则此时topOfStack指向栈顶元素的下一个位置；若将空栈的topOfStack初始化为-1，则此时topOfStack直接指向栈顶元素的位置，无论选择哪一种初始化方式，在实现对应的接口时都要根据自己的选择进行调整。
数组实现中，栈的操作都是在一块连续的内存空间中进行，内存命中率较高。当容量不足时，数组栈就会触发扩容机制，考虑最坏情况(realloc对另外的空间的开辟和原空间的内容拷贝)，此时的Push操作效率为O(N)，此外，数组栈会不可避免的造成一定的空间浪费现象。但是由于扩容是低频操作，所以数组栈的整体效率较高。
栈的数组实现：
typedef int StackDataType;
typedef struct Stack
{
StackDataType* data;
int capacity;
int top;
}Stack;
void StackInit(Stack* ps);
void StackDestroy(Stack* ps);
void StackPush(Stack* ps, StackDataType x);
void StackPop(Stack* ps);
int StackSize(Stack* ps);
bool StackEmpty(Stack* ps);
StackDataType StackTop(Stack* ps);
void StackInit(Stack* ps)
{
assert(ps);
ps->data = (StackDataType*)malloc(sizeof(StackDataType) * 20);
assert(ps->data);
ps->capacity = 20;
ps->top = 0;
}
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->data);
ps->data = NULL;
ps->capacity = 0;
ps->top = 0;
}
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
void StackPush(Stack* ps, StackDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
StackDataType* tmp = NULL;
tmp = (StackDataType*)realloc(ps->data,
sizeof(StackDataType) * (2 * ps->capacity));
if (tmp != NULL) {
ps->data = tmp;
ps->capacity *= 2;
}
else {
perror("StackPush::realloc");
}
}
(ps->data)[ps->top] = x;
ps->top++;
}
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
int StackSize(Stack* ps)
{
return ps->top;
}
StackDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return (ps->data)[ps->top - 1];
}栈的应用
平衡符号
在现实中，很多事物是成对存在的，常见的一个例子就是括号的匹配，每一个右花括号、右圆括号、右方括号都必然对应着相应的左括号，例如序列"[()]{}"是合法的，而序列"{(]}"是非法的。
利用栈可以检测类似的符号平衡问题，编译器检测某些语法错误时就是这个原理。
用栈检测括号匹配：
bool isValid(char * s)
{
Stack ST;
StackInit(&ST);
for(int i = 0; s[i] != '\0'; i++)
{
if(s[i] == '(' || s[i] == '[' || s[i] == '{') {
StackPush(&ST, s[i]);
}
else
{
if(StackEmpty(&ST)) {
StackDestroy(&ST); //注意销毁以避免内存泄漏!!!
return false;
}
char top = StackTop(&ST);
if(s[i] == ')' && top != '(' ||
s[i] == ']' && top != '[' ||
s[i] == '}' && top != '{') {
StackDestroy(&ST); //注意销毁以避免内存泄漏!!!
return false;
}
else {
StackPop(&ST);
}
}
}
// "([](){}"
bool ret = StackEmpty(&ST);
StackDestroy(&ST); //注意销毁以避免内存泄漏
return ret;
}中缀表达式转逆波兰式
首先对前缀表达式、中缀表达式和后缀表达式进行一个简要的说明。
如上面的算数二叉树，对其中序遍历得到的式子为：(3 + 5) * 2，即最常见的中缀表达式，这种式子是对人来说最易理解和计算，是日常生活中最常见的形式；
对其前序遍历得到的式子为：( * + 3 5 2 )，描述的是前缀表达式，即波兰式；
对其后序遍历得到的式子为：( 3 5 + 2 * )，描述的是后缀表达式，即逆波兰表达式。这种形式对人来说不易理解，但是对计算机来说是最易进行计算的。
利用一个运算符栈可以将中缀表达式转化为逆波兰式：
构建栈st，遍历中缀表达式：
若为数字，则直接输出(放入容器)；
若为左括号，则直接入栈；
若为右括号，则出栈st，将元素输出，直到st栈顶为左括号，此时丢弃左、右括号；
若为运算符，如果该运算符优先级严格大于st栈顶运算符，则将该运算符入栈st；否则出栈st，将st元素输出，直到st栈顶运算符优先级严格小于该运算符或st为空，此时将该运算符入栈st；
结束后，输出容器中的存储的即为逆波兰式。
逆波兰式的计算
利用栈可以对逆波兰式进行计算：
构建栈sT，遍历逆波兰式：
若为数字，则直接入栈；
若为运算符，则取栈顶两个元素进行相应计算，将栈顶两个元素替换为计算的中间结果。
计算逆波兰表达式：
int evalRPN(char ** tokens, int tokensSize)
{
Stack St;
StackInit(&St);
for(int i = 0; i < tokensSize; i++)
{
char* str = tokens[i];
int len = strlen(str);
//如果len为1，则为数字或运算符
if(len == 1)
{
char token = str[0];
//是数字，入栈
if(isdigit(token)) {
StackPush(&St, token - '0');
}
//是运算符，连续取两个栈顶数字作为临时运算数
else
{
int num1 = 0;
int num2 = 0;
int tmp = 0;
num1 = StackTop(&St);
StackPop(&St);
num2 = StackTop(&St);
StackPop(&St);
//判断运算符以对临时运算数进行运算
switch (token)
{
case '+':
tmp = num2 + num1;
break;
case '-':
tmp = num2 - num1;
break;
case '*':
tmp = num2 * num1;
break;
case '/':
tmp = num2 / num1;
break;
default:
break;
};
//将临时结果入栈
StackPush(&St, tmp);
}
}
//len大于1，一定是数字
else {
StackPush(&St, atoi(str));
}
}
int res = StackTop(&St);
StackDestroy(&St);
return res;
}表达式求值
用栈可以直接对中缀表达式进行求值，具体步骤为：
- 构建数字栈numSt和运算符栈operSt，遍历中缀表达式；
- 如果为数字，则直接入栈numSt；
- 如果为左括号，则直接入栈operSt；
- 如果为右括号，则不断出栈numSt栈顶的两个值，以及operSt作为运算符进行计算(先出的为右值)，直到operSt的栈顶元素为左括号，此时出栈丢弃左括号；
- 如果为运算符，且运算符优先级严格大于operSt栈顶运算符的优先级，则直接入栈operSt；
- 如果为运算符，且运算符优先级小于或等于operSt栈顶运算符的优先级，则不断出栈numSt栈顶的两个值，以及operSt作为运算符进行计算(先出的为右值)，直到operSt的栈顶运算符的优先级严格小于当前运算符的优先级，然后入栈operSt
队列
队列模型
队列是只允许在一端进行插入数据操作(Enqueue)，在另一端进行删除数据操作(Dequeue)的线性表，入数据的一端称为队尾(Rear)，出数据的一端称为队头(Front)。
队列具有先进先出(FIFO)的性质，对队列的基本操作有Push和Pop，前者在队尾插入一个数据，后者从队头删除一个数据。队头元素可以通过Top()进行观察，队尾元素可以通过Back()进行观察。
队列的实现
同栈一样，任何实现表的方法都能实现队列。
基于链表实现
使用链表实现队列是一个较简单和常见的做法。将链表前端作为队头，将链表后端作为队尾，对队列的Push和Pop其实就是对单链表的尾插和头删操作。为了保证单链表尾插的效率，需要一个指针维护链表的尾节点。
队列的链表实现：
typedef int QueueDataType;
typedef struct QueueNode
{
QueueDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
QueueNode* front;
QueueNode* back;
int size;
}Queue;
void QueueInit(Queue* pQ);
void QueueDestory(Queue* pQ);
void QueuePush(Queue* pQ, QueueDataType x);
void QueuePop(Queue* pQ);
bool QueueEmpty(Queue* pQ);
int QueueSize(Queue* pQ);
QueueDataType QueueFront(Queue* pQ);
QueueDataType QueueBack(Queue* pQ);
void QueueInit(Queue* pQ)
{
assert(pQ);
pQ->front = NULL;
pQ->back = NULL;
pQ->size = 0;
}
void QueueDestory(Queue* pQ)
{
assert(pQ);
while (pQ->front)
{
QueueNode* nextNode = pQ->front->next;
free(pQ->front);
pQ->front = nextNode;
}
pQ->front = NULL;
pQ->back = NULL;
pQ->size = 0;
}
void QueuePush(Queue* pQ, QueueDataType x)
{
assert(pQ);
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
assert(newNode);
newNode->data = x;
newNode->next = NULL;
if (pQ->front == NULL)
{
assert(pQ->back == NULL);
pQ->front = newNode;
pQ->back = newNode;
}
else
{
pQ->back->next = newNode;
pQ->back = newNode;
}
pQ->size++;
}
bool QueueEmpty(Queue* pQ)
{
return pQ->size == 0;
}
void QueuePop(Queue* pQ)
{
assert(pQ);
assert(!QueueEmpty(pQ));
QueueNode* nextNode = pQ->front->next;
free(pQ->front);
pQ->front = nextNode;
if (pQ->front == NULL) {
pQ->back = NULL;
}
pQ->size--;
}
int QueueSize(Queue* pQ)
{
assert(pQ);
return pQ->size;
}
QueueDataType QueueFront(Queue* pQ)
{
assert(pQ);
return pQ->front->data;
}
QueueDataType QueueBack(Queue* pQ)
{
assert(pQ);
return pQ->back->data;
}循环数组
利用数组可以实现出一个队列，用Front维护有效数据的起始位置，Rear维护有效数据位置的下一个位置。为了使一个元素 x 入队，将Rear位置的元素置为 x，Rear后移一个位置；为了使一个元素出队，直接将Front右移一个位置。当Front和Rear到达数组的末尾时，利用取模运算将Front和Rear绕回到开头。这就叫做循环数组(circular array)实现。
为了便于判断队列为空/为满的情况，需要额外开一个数据空间，利用Front和Rear之间的关系隐式判断队列当前的状态。
可以将循环数组想象成下面的结构：
循环数组实现队列：
typedef struct
{
int* data; //存储数据
int size; //记录最大容量
int front;
int rear;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* newCircularQueue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
assert(newCircularQueue);
newCircularQueue->data = (int*)malloc(sizeof(int) * (k + 1));
newCircularQueue->size = k;
newCircularQueue->front = 0;
newCircularQueue->rear = 0;
return newCircularQueue;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->front == obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
return (obj->rear + 1) % (obj->size + 1) == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if(myCircularQueueIsFull(obj)) {
return false;
}
else
{
(obj->data)[obj->rear++] = value;
obj->rear %= (obj->size + 1);
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj)) {
return false;
}
else
{
obj->front++;
obj->front %= (obj->size + 1);
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj)) {
return -1;
}
else {
return (obj->data)[obj->front];
}
}
int myCircularQueueRear(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj)) {
return -1;
}
else {
return (obj->data)[(obj->rear - 1 + obj->size + 1) % (obj->size + 1)];
}
}
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->data);
free(obj);
}队列的应用
队列往往应用于排队情境中。比如当有较多计算机用户访问文件服务器中的文件时，用户往往会被放到一个队列中，以达到先到者先得的原则。此外，网购订单、某些待办事项管理也遵循这个逻辑。
