填空题

实现一个动态调整大小的数组

Question

我们知道C++的数组需要在编译时决定大小，但很多时候，我们往往不能提前预估数组的大小，为此我们设计一个动态数组，即：当向数组中添加新元素时，如果数组空间不够，那么自动对数组进行扩容；如果从数组中删除了较多元素，那么也可以自动对数组进行缩容。

请实现一个简化的动态数组，该数组存储整数（int），只提供三个操作：

1. 向数组尾部追加一个新元素，如果空间不够，那么自动扩容，同时要求该追加操作的均摊时间复杂度为O(1)：void push(int num)

2. 从数组尾部删除一个元素，如果数组不为空，返回被删除的元素，如果数组为空，返回-1，不执行删除操作。当删除较多元素后，可以对数组进行缩容，但要求从尾部删除元素的操作，均摊时间复杂度为O(1): int pop()

3. 根据数组下标获取对应的整数，如果下标越界，返回-1，时间复杂度O(1)：int get(int idx)

输入描述：

输入为一系列的操作，一行一个操作，操作分为三类：

1. 从尾部追加新元素，格式为：push + 空格 + 整数

2. 删除尾部元素，格式为：pop

3. 根据下标获取元素，格式为：get + 空格 + 下标索引

输入样例： push 1 push 3 pop push 4 get 0 get 4 输出描述：

每个操作对应一行输出：

1. 对于push操作，输出push之后数组的大小

2. 对于pop操作，输出pop()函数的返回值，即：删除的整数

3. 对于get操作，输出get()函数的返回值，即：该下标对应的整数

输出样例 1 2 3 2 1 -1