数据结构学习笔记（特殊的线性表：栈与队列）

栈与队列

栈是限定仅在表尾（栈顶）进行插入和删除操作的线性表（后进先出）。 队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表（先进先出）。

栈（Stack）：

1.下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以让它作为栈底。 定义一个top变量来指示栈顶元素在数组中的位置。栈顶位置top必须小于存储栈长度StackSize，把空栈的判定条件定位top等于-1。

2.进栈与出栈操作（顺序存储结构）：

进栈操作push： /*插入元素e为新的栈顶元素*/ Status Push(SqStack *S, SElemType e) { if (S->top == MAXSIZE - 1) /*栈满*/ return ERROR; S->top++; /*栈顶指针增加一*/ S->data[S->top] = e; /*将新插入元素赋值给栈顶空间*/ return OK; }

出栈操作pop： /*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/ Status Pop(SqStack *S, SElemType *e) { if (S->top == -1) return ERROR; *e = S->data[S->top]; /*将要删除的栈顶元素赋值给e*/ S->top--; /*栈顶指针减一*/ return OK; }

*进栈与出栈两者的时间复杂度均是O(1)。

3.两栈共享空间： 数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处。这样，两个栈如果增加元素，就是两端点向中间延伸。 栈1为空时，就是top1等于-1时；而当top2等于n时，即是栈2为空时。 两个栈见面知识，也就是两个指针之间相差1时，即top1 + 1 == top2 为栈满。

4.栈的链式存储结构： 栈顶放在单链表的头部。 对于链栈来说，是不需要头结点的。 对于链栈来说，基本不存在栈满的情况。 链栈的空其实就是top=NULL。

5.进栈与出栈操作（链式存储结构）：

进栈操作： /*插入元素e为新的栈顶元素*/ Status Push(LinkStack *S, SElemType e) { LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode)); s->data=e; s->next=S->top; /*把当前的栈顶元素赋值给新结点的直接后继*/ S->top=s; /*将新的结点s赋值给栈顶指针*/ S->count++; return OK; }

出栈操作： /*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR*/ Status Pop(LinkStack *S, SElemType *e) { LinkStackPtr P; if (StackEmpty(*S)) return ERROR; *e=S->top->data; p=S->top; /*将栈顶结点赋值给p*/ S->top=S->top->next; /*使得栈顶指针下移一位，指向后一结点*/ free(p); /*释放结点p*/ S->count--; return OK; }

*链栈的出栈push和出栈pop操作没有任何循环操作，时间负责度均为O(1)。 *顺序栈和链栈，它们在时间复杂度上是一样的，均为O(1)。 *如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈；反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

6.栈的应用：递归 递归定义：把一个直接调用自己或者通过一系列的调用语句间接地调用自己的函数，称作递归函数。 每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身二十返回值退出。 *迭代和递归的区别是：迭代使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更清晰，更简洁，更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。 递归过程退回的顺序是它前行顺序的逆袭。

7.栈的应用：四则运算表达式求值 后缀表达式：所有的符号都是在要运算数字的后面出现。 中缀表达式：标准四则运算表达式。 *后缀表达式运算规则：从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算（后出栈的那个数字是“被”的，比如“被减数”，前面那个比如“减数”，运算结果出栈，一直到最终获得结果。

*中缀表达式转后缀表达式： 规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号出栈，一直到最终输出后缀表达式为止。

队列（Queue）： 1.队列定义：队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列是一种先进先出的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。

2.把队列的这种头尾相接的顺序存储结构称为循环对列。

3.判断队列究竟是空还是满？ *办法一是设置一个标志变量flag，当front == rear，且flag = 0 时为队列空，当front == rear，且 flag = 1时为队列满。 *办法二是当队列空时，条件就是front = rear，当队列满时，我们修改其条件，保留一个元素空间： 设队列的最大尺寸为QueueSize，队列满的条件是（rear+1）% QueueSize == front（取模“%”的目的就是为了整合rear与front大小为一个问题）。 通用的计算队列长度公式为： （rear - front + QueueSize) % QueueSize

4.循环队列操作（队列的顺序存储结构）：

循环队列的顺序存储结构代码如下： typedef int QElemType; /*QElemType类型根据实际情况而定，这里假设为int*/ /*循环队列的顺序存储结构*/ typedef struct { QElemType data[MAXSIZE]; int front; /*头指针*/ int rear; /*尾指针，若队列不空，指向队列尾元素的下一位置*/ }SqQueue;

循环队列的初始化代码如下： /*初始化一个空队列Q*/ Status InitQueue(SqQueue *Q) { Q->front = 0; Q->rear = 0; return OK; }

循环队列求队列长度代码如下： /*返回Q的元素个数，也就是队列的当前长度*/ int QueueLength(SqQueue Q) { return (Q.rear - Q.front + MAXSIZE) % MAXSIZE; }

循环队列的入队列操作代码如下： /*若队列未满，则插入元素e为Q新的队尾元素*/ Status EnQueue(SqQueue *Q, QElemType e) { if((Q->rear+1)%MAXSIZE == Q->front) /*队列满的判断*/ return ERROR; Q->data[Q->rear]=e; /*将元素e赋值给队尾*/ Q->rear=(Q->rear+1)%MAXSIZE; /*rear指针后移一位置*/ return OK; }

循环队列的出队列操作代码如下： /*若队列不空，则删除Q中队头元素，用e返回其值*/ Status DeQueue(SqQueue *Q, QElemType *e) { if (Q->front == Q->rear) /*队列空的判断*/ return ERROR; *e = Q->data[Q->front]; /*将队头元素赋值给e*/ Q->front = (Q->front + 1) % MAXSIZE; /*front指针向后移一位置*/ /*若到最后则转到数组头部*/ return OK; }

5.队列的链式存储结构—-尾进头出。 队头指针指向链队列的头结点。队尾指针指向终端结点。空队列时，front和rear都指向头结点。

链队列的结构为： typedef int QElemType; /*QElemType类型根据实际情况而定，这里假设为int*/ typedef struct QNode; /*结点结构*/ { QElemType data; struct QNode *next; }QNode, *QueuePtr;

typedef struct /*队列的链表结构*/ { QueuePtr front, rear; /*队头，队尾指针*/ }LinkQueue;

6.队列的链式存储结构—-入队与出队操作： 入队操作：其实就是在链表尾部插入结点。 /*插入元素e为Q的新的队尾元素*/ 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=e; /*把拥有元素e的新结点s赋值给原队尾结点的后继，*/ Q->rear=s; /*把当前s设置为队尾结点，rear指向s*/ return OK; }

出队操作：就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点。 /*若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR*/ Status DeQueue(LinkQueue *Q, QElemType *e) { QueuePtr p; if(Q->front==Q->rear) return ERROR; p=Q->front->next; /*将欲删除的队头结点暂存给p*/ *e=p->data; /*将欲删除的队头结点的值赋值给e*/ Q->front->next=p->next; /*将原队头结点后继p->next赋值给头结点后继*/ if(Q->rear==p) /*若队头是队尾，则删除后将rear指向头结点*/ Q->rear=Q->front; free(p); return OK; }

*循环队列与链队列比较： 时间上：时间复杂度都为O（1）； 空间上：循环队列需要事先申请好空间，使用期间不释放，在空间上，链队列更加灵活。 *建议：在可以确定队列长度最大值的情况下，建议用循环队列，如果无法预估队列的长度时，则用链队列。

#总结：栈分为顺序栈和链栈，其中顺序栈可以通过使用“两栈共享空间”的方法解决顺序栈的弊端；            队列分为顺序队列和链队列，其中顺序队列可以通过使用“循环队列”的方法解决顺序队列的弊端。