数据结构——第三章 栈与队列（5）

1.共用栈

在实际应用中，有时一个应用程序需要多个栈，但这些栈的数据元素类型相同。假设每个栈都采用顺序栈，由于每个栈的使用情况不尽相同，势必会造成存储空间的浪费。若让多个栈共用一个足够大的连续存储空间，则可利用的动态特性使它们的存储空间互补。这时的操作必须同时记住多个栈的栈顶。

为使操作更加方便，可采用多个单链表，将它们的栈顶存放到一个指针数组中。
顺序栈的共享最常见的两栈的共享。假设两个栈共享一维数组s[MAXNUM]，其中一个栈的栈顶用topl指示，另一个栈的栈顶用top2指示。

共享栈的数据类型描述如下：

typedef int SElemType;
typedef struct ShareStack
{SElemType data[MAXNUM];int top1, top2;int stackSize;
}ShareStack;

栈空：栈1空，top1==-1为真；栈2空，top2MAXNUM为真。
栈满：top1+1top2为真。
进栈操作：必须区分是对哪一个栈进操作。

int EnShareStack(ShareStack* S, SElemType x, int stacknum)
{if (S->top1 + 1 == S->top2)return 0;if (stacknum == 1)S->data[++S->top1] = x;else if (stacknum == 2)S->data[++S->top2] = x;else return 0;return 1;
}

出栈操作：必须区分是对哪一个栈进行操作。

int DeShareStack(ShareStack* S, SElemType* x, int stacknum)
{if (stacknum == 1){if (S->top1 == -1)return 0;else *x = S->data[S->top1--];}else if (stacknum == 2){if (S->top1 == S->stackSize)return 0;else *x = S->data[S->top2++];}else return 0;return 1;

2.双端队列

如果限定插入和删除操作均可以在线性表的两端进行，则称位双端队列。
这样的结构常用于计算机的CPU的调度，所谓“CPU调度”是指在多人使用一个CPU的情况下，由于CPU在同一时间只能执行一项任务，所以将每个人的工作任务事先存放在队列中，待CPU闲置时，再从队列中取出一项待执行的工作进行处理。双端队列的两端均可输出和输入，使CPU处理不同任务的请求更具灵活性。
双端队列与共用栈是不相同的。共用栈的每个栈都各自有一个栈顶都各自有一个栈顶指针，两个栈顶指针是向中间扩展；而两端队列可以看成是两个栈底连在一起的栈，在两个端点都分别设有队头和队尾两个指针，也可以对双端队列做出如下限制。
（1）只允许在一端进行插入，两端进行删除。
（2）只允许在一端进行删除，两端进行插入。

栈与队列的本章小节

栈和队列同属于线性表，但它们与第2章的线性表数不同。一般线性的插入和删除操作，只要位置合理，都可以进行操作。栈的插入与删除操作只能在一端进行；队列的插入与删除操作分别在两端进行。因此常常称栈与队列是插入与删除受限的线性表。
栈的常用存储空间结构有顺序栈和链栈。顺序栈除了要考虑一片连续的存储空间用于存放栈中元素之外，还必须考虑指示栈顶的位置和总容量，所以常用的顺序栈和顺序表一样有两种不同的定义方法。由于进栈和出栈操作只能在栈顶进行，因此链表通常不是带头结点的单向链表。
队列的常用存储结构有循环队列和队列。循环队列一定要哦保证一片连续存储空间的循环使用，因此循环队列的类型考虑给定的数据成员能否正确表达队头、队尾的位置以及队空、队满的条件和队列元素个数的计算。本章给出了循环队列的两种描述方法，特别需要注意的是；在第一种循环队列的定义中，队头指针指向队头，队尾指针指向队尾的下一个元素；在第2种循环队列的定义中，只有队尾指针，队头指针并不在类型中，而是计算出来的。
链队列的重点在于队头指针和队尾指针的确定。本章给出了两种链队列的类型定义：一种是单链表实现，将队头指针和队尾指针组成一个结构体类型，让队头指针指向头结点，队尾指针指向队尾；另一种是循环链表实现，只用一个队尾指针指向尾结点，让尾结点的指针域指向头结点。