# 實習課第五次作業

###### tags: `NTOU CSE C++ Programming`

> 教學文件和作業說明文件： https://hackmd.io/@kogiokka/ntou-cse-cpp-nav

> 範例程式和範例專案：[Google Drive](
https://drive.google.com/drive/folders/100YvcqccLgY_27mJnubRSuPALrMAghJQ?usp=sharing)

本次主題是堆疊（stack）資料結構。

## 題目

程式要以下列三個方式實作三個版本的堆疊（stack），**儲存值的型態為`float`**：
1. 版本一、巨集（`#define ...`）
2. 版本二、動態陣列（`malloc`）
3. 版本三、連結串列（linked-list）

## 要求

* 不可使用全域變數（global variables）。
* 程式要包含一個無窮迴圈，每次供使用者輸入選項 1 到 4，分別執行下列功能：

| 輸入 | 動作 |
| -------- | -------- |
| 1 | 版本一 |
| 2 | 版本二 |
| 3 | 版本三 |
| 4 | 結束程式 |

* 每一個版本在 Demo 時要執行下列功能：
a) push
b) pop
c) printStack
d) 結束（回到選擇版本的迴圈）

* 定義下列結構（`struct`）：

| 方法 | 名稱 | 成員 |
| - | - | - |
| 巨集 |`struct Stack_define` | `stack_array`、`size`、`top` |
| 動態陣列 |`struct Stack_malloc` | `stack_array`、`size`、`top` |
| 連結串列 |`struct Stack_linked` | `headPtr` |

* 定義下列函式（functions）：

| 函式名稱 | 回傳值型態 | 回傳值意義 |
| - | - | - |
| `push` | `bool` | `true` 代表成功，`false` 代表失敗。|
| `pop` | `bool` | `true` 代表成功，`false` 代表失敗。|
| `isEmpty` | `bool` | `true` 代表成功，`false` 代表失敗。|
| `isFull` | `bool` | `true` 代表成功，`false` 代表失敗。|
| `printStack` | `void` | 無回傳值 |

* 三個版本皆包含在同一個專案內。使用一個標頭檔：
→ `stack.h`
* 每個實作版本和`main`函式必須分別放在不同檔案內:
→ `main.cpp`
→ `stack_define.cpp`
→ `stack_malloc.cpp`
→ `stack_linked.cpp`

* 使用 reference 語法寫`push`、`pop`：

// 改為 bool push(StackNodePtr&,float); 
// 回傳 bool true代表成功，false代表失敗
void push(StackNodePtr *, int);

// 改為 bool pop(StackNodePtr&, float&);
int pop(StackNodePtr *);

> 參考文章：[Lvalue references - Learn C++](https://www.learncpp.com/cpp-tutorial/lvalue-references/)

### 版本一、巨集

使用 `#define` 來定義陣列大小：

// Example
#define STACK_SIZE 10
float stack[STACK_SIZE];

### 版本二、動態陣列

使用函式來初始化堆疊的大小：

/* 定義 stackInitial 函式
 *
 *  - 使用 malloc
 *  - 回傳成功或失敗
 *  - 參數 size 為堆疊初始化的大小
 *  - size 預設值為 10
 */ 
bool stackInitial(int size);

### 版本三、連結串列

不用定義 `isFull` 函式。

## 作業上傳規定

格式：`<學號>-<姓名>.zip`，例如：`11057022-江柏毅.zip`

如果你是用 Visual Studio，請刪除下列資料夾再上傳：**`.vs`**、`out`、`Debug`、`x64`。
使用其他 IDE 的同學也請刪掉建置資料夾再上傳，例如：`build`、`out`。

## 參考資料
* [Implementation of Stack Using Array in C](https://www.programming9.com/programs/c-programs/302-implementation-of-stack-using-array-in-c)
* [Linked List: Intro(簡介)](http://alrightchiu.github.io/SecondRound/linked-list-introjian-jie.html)
* [Stack: 以Array與Linked list實作](http://alrightchiu.github.io/SecondRound/stack-yi-arrayyu-linked-listshi-zuo.html)
* [如何在 C++ 中建立一個動態陣列](https://www.delftstack.com/zh-tw/howto/cpp/dynamically-allocated-array-cpp/)