可自動擴充的陣列堆疊

題目敘述

圖書館還書櫃的書是一本疊一本，最後放上去的書最先被拿走。請你用一個會自動變大的陣列，寫出這種「後進先出」的整數堆疊。

陣列用完時，把容量加倍再繼續放，這樣每次 push 平均下來仍只花常數時間。

請提交 stack.h 與 stack.c：在標頭檔定義 stack 結構，並在 .c 檔實作下面的介面。

typedef struct stack stack; /* define the struct in stack.h */

void stack_init(stack *s); /* (re)initialize to empty */
void stack_push(stack *s, int x);
int stack_pop(stack *s); /* remove and return the top (only when non-empty) */
int stack_top(stack *s); /* return the top without removing (only when non-empty) */
int stack_size(stack *s);
int stack_empty(stack *s); /* 1 if empty, else 0 */

測試程式

評測用的 driver 先讀入操作數 Q，再依序處理 Q 個操作：push x、pop、top、size、empty。除了 push 以外，每個操作都會印出一行結果。

driver 在執行 pop 或 top 之前會先呼叫 stack_empty()；堆疊為空時它直接印出 EMPTY，不會呼叫你的 stack_pop / stack_top。所以 stack_empty() 一定要正確。

輸入格式

• 第 1 行：整數 Q，操作的個數。
• 接下來 Q 行：每行一個操作，為 push x、pop、top、size 或 empty。

輸出格式

pop、top、size、empty 各印一行：pop 與 top 印出對應的元素，size 印出元素個數，empty 印出 1 或 0。堆疊為空時的 pop 與 top 印出 EMPTY。

限制

• 1 ≤ Q ≤ 500
• push 的值為 [−1000, 1000] 內的整數

範例

範例 1

輸入

5
push 1
push 2
top
pop
size

輸出

2
2
1

範例 2

輸入

2
pop
empty

輸出

EMPTY
1

範例 3

輸入

4
push 5
empty
pop
empty

輸出

0
5
1

範例 4

輸入

6
push 1
push 2
push 3
pop
pop
pop

輸出

3
2
1

範例 5

輸入

2
push 9
empty

輸出

0

說明

範例 1：先放入 1、2，頂端是 2；pop 取走 2，剩一個元素。範例 2 在空堆疊上 pop，所以印出 EMPTY，隨後 empty 得到 1。

提示：

• 容量不夠時配置兩倍大的新陣列並複製舊資料，單次 push 偶爾要花 O(n)，但平均每個操作是 O(1)。
• pop 一定要讓元素個數減一，否則之後的 size 與 top 都會錯。
• 每個操作都應在攤銷 O(1) 時間內完成。