大学专业网站,如何自己开发软件app,查域名ip地址查询,广告设计共用栈和双队列1.共用栈2.双端队列栈与队列的本章小节1.共用栈
在实际应用中#xff0c;有时一个应用程序需要多个栈#xff0c;但这些栈的数据元素类型相同。假设每个栈都采用顺序栈#xff0c;由于每个栈的使用情况不尽相同#xff0c;势必会造成存储空间的浪费。若让多…
共用栈和双队列1.共用栈2.双端队列栈与队列的本章小节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为真。 栈满top11top2为真。 进栈操作必须区分是对哪一个栈进操作。
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种循环队列的定义中只有队尾指针队头指针并不在类型中而是计算出来的。 链队列的重点在于队头指针和队尾指针的确定。本章给出了两种链队列的类型定义一种是单链表实现将队头指针和队尾指针组成一个结构体类型让队头指针指向头结点队尾指针指向队尾另一种是循环链表实现只用一个队尾指针指向尾结点让尾结点的指针域指向头结点。
