数据结构 | 每日一练（91）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1. 若元素的进栈序列为：A、B、C、D、E，运用栈操作，能否得到出栈序列 B、C、A、E、D 和 D、B、A、C、E？为什么？

2. 设输入序列为 a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。

3. 设输入序列为 2，3，4，5，6，利用一个栈能得到序列 2，5，3，4，6 吗？栈可以用单链表实现吗？

正确答案

PS：||代表注释

1、能得到出栈序列B、C、A、E、D，不能得到出栈序列D、B、A、C、E。其理由为：若出栈序列以D开头，说明在D之前的入栈元素是A、B和C，三个元素中C是栈顶元素，B和A不可能早于C出栈，故不可能得到D、B、A、C、

E出栈序列。

2、借助栈结构，n个入栈元素可得到1/(n+1)((2n）！/（n!*n!）)种出栈序列。本题4个元素，可有14种出栈序列，abcd和dcba就是其中两种。但dabc和adbc是不可能得到的两种。

3、不能得到序列2，5，3，4，6。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。

-end-

C语言入门到精通