把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表，简称LIFO结构。相对于线性表的头结点和尾部，栈顶相当于表尾，栈底相当于头结点。
栈的插入操作叫做进栈、压栈、入栈，删除操作叫做出栈、弹栈。
#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int SElemType;
typedef int Status;
//栈的定义
typedef struct {
SElemType data[MAXSIZE];
int top;
}SqStack;
//进栈
Status Push(SqStack *S, SElemType e) {
if (S->top == MAXSIZE - 1) { return ERROR; }
S->top++;
S->data[S->top] = e;
return OK;
}
//出栈
Status Pop(SqStack *S, SElemType *e) {
if (S->top == -1) { return ERROR; } //空栈
*e = S->data[S->top];
S->top--;
return OK;
}
两栈共享空间
typedef struct {
SElemType data[MAXSIZE];
int top1;
int top2;
}SqDoubleStack;
Status Push(SqDoubleStack *S, SElemType e, int stackNumber) {
if (S->top1 + 1 == S->top2) { return ERROR; } //满栈
if (stackNumber == 1) { //判断是栈1还是栈2
S->data[++S->top1] = e;
} else if (stackNumber == 2) {
S->data[--S->top2] = e;
}
return OK;
}
Status Pop(SqDoubleStack *S, SElemType *e, int stackNumber) {
if (S->top1 == -1 && S->top2 == MAXSIZE) { return ERROR; } //空栈
if (stackNumber == 1) {
*e = S->data[S->top1--];
} else if (stackNumber == 2) {
*e = S->data[S->top2++];
}
return OK;
}
适用于两个栈存放相同的数据类型，如果不相同，则会使问题变得更复杂。
栈的链式存储
栈的链式存储结构，简称为链栈。
链栈不存在栈满的情况。对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top = NULL的时候。
typedef struct StackNode {
SElemType data;
struct StackNode *next;
}StackNode, *LinkStackPtr;
typedef struct LinkStack {
LinkStackPtr top;
int count;
}LinkStack;
Status Push(LinkStack *S, SElemType e) {
LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
s->data = e;
s->next = S->top;
S->top = s;
S->count++;
return OK;
}
Status Pop(LinkStack *S, SElemType *e) {
if (S->count == -1) { return ERROR; }
LinkStackPtr p;
*e = S->top->data;
p = S->top;
S->top = p->next;
free(p);
S->count--;
return OK;
}
如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。
栈的应用 - 递归
斐波那契示例
int Fbi(int i) {
if (i < 2) {
return i == 0 ? 0 : i;
}
return Fbi(i - 1) + Fbi(i - 2);
}
队列
队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出的线性表，简称FIFO。允许插入的插入的一端称为队尾，允许删除的一端称为队头。
队列的顺序存储
队列元素的出列在队头，也就意味着，队列中的所有元素都得向前移动，时间复杂度为O(n)。为了解决就这个问题，所以引入两个指针，front指针指向队头元素(有数据值的元素，并不局限于下标为0的空闲元素)，rear指针指向队尾元素的下一个位置，当front等于rear时，此队列是空队列。
但假设这个队列的总个数不超过5个，继续往队列添加元素时，就会产生数组越界的错误，可实际上，队列在下标为0和1的位置还是空闲的，这种现象叫做"假溢出"。
解决"假溢出"的方式就是后面满了，就再从头开始，也就是头尾相接的循环，这种头尾相接的顺序结构存储称为循环队列。
其中，循环队列会出现当队列已满，rear与front相遇，按常理这队列就是空队列，但实际上则是满队列。解决方法就是使用队列满的条件: (rear + 1) % MAXSIZE == front
通用的计算队列长度公式: (rear - front + QueueSize) % QueueSize
typedef struct {
QElemType data[MAXSIZE];
int front;
int rear;
}SqQueue;
//初始化一个空队列
Status InitQueue(SqQueue *Q) {
Q->front = 0;
Q->rear = 0;
return OK;
}
int QueueLength(SqQueue Q) {
return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
//入队
Status EnQueue(SqQueue *Q, QElemType e) {
if ((Q->rear + 1) % MAXSIZE == Q->front) { return ERROR; }
Q->data[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAXSIZE;
return OK;
}
//出队
Status DeQueue(SqQueue *Q, QElemType *e) {
if (Q->front == Q->rear) { return ERROR; }
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZE;
return OK;
}
//判断队列是否为空
Status QueueEmpty(Queue Q) {
return Q.front == 0 && Q.rear == 0;
}
队列的链式存储
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，简称称为链队列。为了操作上的方便，将队头指针指向链队列的头结点，而队尾指针指向终端的结点。空队列时，front和rear都指向头结点。
typedef struct QNode {
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct {
QueuePtr front, rear;
}LinkQueue;
//入队
Status EnQueue(LinkQueue *Q, QElemType e) {
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
if (!s) { exit(OVERFLOW); }
s->data = e;
s->next = NULL;
Q->rear->next = s; //把拥有元素e新结点s赋值给原队尾结点的后面
Q->rear = s; //把当前的s设置为队尾结点
return OK;
}
//出队
Status DeQueue(LinkQueue *Q, QElemType *e) {
QueuePtr p;
if (Q->rear == Q->front) { return ERROR; }
p = Q->front->next;
*e = p->data;
Q->front->next = p->next;
if (Q->rear == p) {
Q->rear = Q->front;
}
free(p);
return OK;
}
网友评论