算法练习(50): 栈的可生成性(1.3.45)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 栈的可生成性

题目

1.3.45 栈的可生成性。假设我们的栈测试用例会进行一系列的入栈和出栈操作，序列中的整数 0, 1, ... , N - 1 （按此先后顺序排列）表示入栈操作，N个减号表示出栈操作。设计一个算法，判定给定的混合序列是否会使数组向下溢出（你使用的空间量与 N 无关，即不能用某种数据结构存储所有整数）。设计一个线性时间算法判定我们的测试用例能否产生某个给定的排列（这取决于出栈操作指令的出现位置）。

---

1.3.45 Stack generability. Suppose that we have a sequence of intermixed push and pop operations as with our test stack client, where the integers 0, 1, ..., N-1 in that order (push directives) are intermixed with N minus signs (pop directives). Devise an algorithm that determines whether the intermixed sequence causes the stack to under- flow. (You may use only an amount of space independent of N—you cannot store the integers in a data structure.) Devise a linear-time algorithm that determines whether a given permutation can be generated as output by our test client (depending on where the pop directives occur).
Solution: The stack does not overflow unless there exists an integer k such that the first k pop operations occur before the first k push operations. If a given permutation can be generated, it is uniquely generated as follows: if the next integer in the output permuta- tion is in the top of the stack, pop it; otherwise, push it onto the stack.

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。