《数据结构与算法 C语言版》—— 3.5典型例题

本节书摘来自华章出版社《数据结构与算法 c语言版》一 书中的第3章，第3.5节，作者：徐凤生，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

例1设有两个栈s1、s2采用顺序栈方式，并且共享一个数组a［maxsize］，为了尽量利用空间，减少溢出的可能，采用栈顶相向、迎面增长的存储方式。设计s1、s2的有关初始化、入栈和出栈的操作算法。

解两栈共享数组空间，将两栈栈底设在数组的两端，初始时，top［0］=-1，top［1］=maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，两栈顶指针都指向栈顶元素。

初始化、入栈和出栈的操作算法如下。

(1)初始化操作

(2)进栈操作

(3)出栈操作

例2设从键盘输入一个整数序列:a1，a2，…，an。试编写一个算法实现:用栈结构存储输入的整数，当a≠－1时，进栈；当a=－1时，输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。

解算法描述如下：

例3设结点结构为(data,next)，试用一个全局指针p和某种链接结构实现一个队列，并给出入队和出队操作的算法，要求它们的时间复杂度都是o(1)(不计new和delete时间)。

解本题可采用链表结构来实现。但题目中仅给一个全局指针p，且入队和出队的时间复杂度都是o(1)，因此我们用只设尾指针的循环链表来实现，算法描述如下。

(1)入队操作

(2)出队操作

例4利用两个栈s1和s2来模拟一个队列。已知栈的三个操作如下：push(s,x)，元素x入栈；pop(s,x)，栈顶元素x出栈；stackempty(s)，判栈是否为空栈。利用栈的操作来实现该队列的三个操作：enqueue()，插入元素入队列；dequeue()，删除一个元素出队列；queueempty()，判队列是否为空队列。

解栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2来模拟一个队列时，s1作为输入栈，逐个元素入栈，以此模拟队列元素的入队。当需要出队时，将栈s1出栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。s2出栈，相当于队列的出队，实现了先进先出。显然，只有s2为空且s1也为空时，才算是空队列。算法如下。

void dequeue(stack s1,stack &s2){//s2是输出栈，将s2栈顶元素出栈，实现队头元素的出队

(3)判队列空