若一个栈的输入序列为1,2,3,…,N,输出序列的第一个元素是i,则第j个输出元素是j−i−1。
时间: 2024-05-22 18:16:09 浏览: 859
栈的出栈顺序问题
4星 · 用户满意度95%
这个结论可以通过模拟栈的出栈过程得到。
假设栈的输入序列为1,2,3,…,N,栈的容量为N,栈顶元素为top。从左往右扫描输入序列,每次将当前元素压入栈中。如果当前元素等于栈顶元素,那么栈顶元素出栈,否则继续扫描输入序列并将元素压入栈中。在出栈过程中,每次出栈都会输出一个元素,输出的元素按照出栈的先后顺序排列。
假设第一个输出的元素是i,那么它一定是第i个元素入栈后出栈的。因为在i之前入栈的元素都会被压入栈中,而在i之后入栈的元素都还没有入栈,所以i一定是第i个元素入栈后出栈的。因此,在i之前入栈的元素都已经出栈了,而在i之后入栈的元素都还没有出栈。也就是说,第j个输出的元素一定是第j+i个元素入栈后出栈的。因为在j+i之前入栈的元素都会被压入栈中,而在j+i之后入栈的元素都还没有入栈,所以第j个输出的元素一定是第j+i个元素入栈后出栈的。因此,第j个输出元素是j−i−1。
阅读全文