试题详情
简答题设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是多少？
  • 出队序列是e2，e4，e3，e6，e5，e1的过程：
    （1）e1入栈（栈底到栈顶元素是e1）
    （2）e2入栈（栈底到栈顶元素是e1，e2）
    （3）e2出栈（栈底到栈顶元素是e1）
    （4）e3入栈（栈底到栈顶元素是e1，e3）
    （5）e4入栈（栈底到栈顶元素是e1，e3，e4）
    （6）e4出栈（栈底到栈顶元素是e1，e3）
    （7）e3出栈（栈底到栈顶元素是e1）
    （8）e5入栈（栈底到栈顶元素是e1，e5）
    （9）e6入栈（栈底到栈顶元素是e1，e5，e6）
    （10）e6出栈（栈底到栈顶元素是e1，e5）
    （11）e5出栈（栈底到栈顶元素是e1）
    （12）e1出栈（栈底到栈顶元素是空）
    栈中最多时有3个元素，所以栈S的容量至少是3。

  • 关注下方微信公众号，在线模考后查看

热门试题