设有一顺序栈S，初始状态为空，元素abcdefgh依次进入栈S。若出栈顺序为cbeghfda，则栈S的容量至少是（ ）。

根据出栈序列cbeghfda，可以得到进栈序列的一种可能为：

push a
push b
push c
pop c
push e
push d
pop d
pop e
pop g
push f
pop f
pop h
pop b
pop a

因此，栈S的最大深度为6，即容量为6。因为，栈的容量是指栈中最多可以存放的元素个数，而最大深度就是这个元素个数。

因此，栈S的容量至少为6。

相关问题

定义“圆桌”函数，实现以下功能：有8个人，分别为abcdefgh，编号为别为1~8，按顺序围绕圆桌坐下，从第一个人按顺序报数1,2,3,数到3的倍数的人退出，再从下一个人重新开始数，请输出依次退出人的姓名。（约瑟夫环） Eg.8个人abcdefgh，则输出cfaebhdg

圆桌函数的定义如下：

def round_table(names: List[str], m: int) -> List[str]:
    """
    names: 代表人的姓名列表
    m: 每次报数的倍数
    """
    result = []
    # 初始化环状链表
    circle = CircleList(names)
    # 循环报数
    while circle.size > 0:
        # 每次移动m-1步，再取出元素
        for i in range(m-1):
            circle.move_next()
        result.append(circle.pop_current())
    return result

其中，`CircleList`是一个环状链表的数据结构，具体实现可以参考下面的代码：

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class CircleList:
    def __init__(self, values):
        self.size = len(values)
        self.current = None
        if self.size > 0:
            self.current = Node(values[0])
            p = self.current
            for value in values[1:]:
                p.next = Node(value)
                p = p.next
            p.next = self.current
    
    def move_next(self):
        """移动到下一个元素"""
        if self.current is not None:
            self.current = self.current.next
    
    def pop_current(self):
        """取出当前元素，并将当前指针指向下一个元素"""
        if self.current is None:
            return None
        value = self.current.value
        if self.current.next == self.current:
            self.current = None
        else:
            self.current.value = self.current.next.value
            self.current.next = self.current.next.next
        self.size -= 1
        return value

最后，你可以这样调用圆桌函数：

names = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
result = round_table(names, 3)
print(result)  # 输出 ['c', 'f', 'a', 'e', 'b', 'h', 'd', 'g']

若某棵完全二叉树采用顺序存储，结点的存放次序为ABCDEFGH，画出该二叉树图，并给出中根遍历序列。

根据完全二叉树的性质，结点存放的次序应该是按照层次遍历的顺序，也就是：

A B C D E F G H

将这些结点按照完全二叉树的形式排列，可以得到下面的图：

       A
     /   \
    B     C
   / \   / \
  D   E F   G
 / \
H   -       

其中，- 表示空结点。

中根遍历的顺序是：H D B E A F C G。