# 實習課第十三次作業

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

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

承[實習課第五次作業](https://hackmd.io/@kogiokka/ntou-cse-cpp-practice-05)，用**類別模板**改寫陣列版本的 Stack。

回顧之前跟堆疊（Stack）相關的作業：

* [第五次作業 - 堆疊的實作方式](https://hackmd.io/@kogiokka/ntou-cse-cpp-practice-05)
* [第六次作業 - 函式模板（function template）](https://hackmd.io/@kogiokka/ntou-cse-cpp-practice-06)
* [第八次作業 - 類別、建構子和解構子](https://hackmd.io/@kogiokka/ntou-cse-cpp-practice-08)
* 本次作業 - 類別模板（class template）

## 需求

用 class template 改寫實習課第五次作業的陣列版本的 Stack 類別。template 必須接受 **2** 個參數:

1. stack data type
2. stack 大小

必須定義下列函式（functions）：

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

### 參考資料

* 實習 3
* 課本 22 章

## 測試函式

// Function template to manipulate Stack< T >
template <typename T>
void testStack(Stack<T>& stack, // reference to the Stack< T >
               T value, // initial value to be pushed
               T increment, // increment for subsequent values
               const std::string& stackName) // name of the Stack <T> object
{
    string delim = "";

    cout << "Pushing elements onto " << stackName << ":\n";
    while (stack.push(value)) {
        cout << delim << value;
        value += increment;
        delim = ", ";
    }
    cout << "\n"
         << "Stack is full. Cannot push " << value << "." << endl;

    cout << "Popping elements from " << stackName << ":\n";
    delim = "";
    while (stack.pop(value)) {
        cout << delim << value;
        delim = ", ";
    }
    cout << "\n"
         << "Stack is empty. Cannot pop." << endl;
}

## 範例程式

* [實習課第十三次範例程式：StackClassTemplate（Google Drive）](https://drive.google.com/drive/folders/17Ut2RncT1Al4nW9kjkDjucKuZAd0AMdE?usp=sharing)
* 專案的資料夾路徑不能有中文字元，否則用 Visual Studio 編譯 CMake 專案會出錯。

### StackClassTemplate

#### 編譯和執行

> 不是使用 Visual Studio 嗎？請見 [CMake專案建置](https://hackmd.io/@kogiokka/ntou-cse-cpp-tutorial-02)。

在 Visual Studio 選擇**開啟本機資料夾**或**檔案 → 開啟 → 資料夾**，並選擇`StackClassTemplate/`的資料夾。Visual Studio 會自動開始設定 CMake 專案。等待輸出欄位的訊息跑完之後，在上方工具列的**選取啟動項目**選 `stack-class-template.exe` 就可以自動編譯執行了。

### 原始碼

`CMakeLists.txt`

cmake_minimum_required(VERSION 3.12)

project("Stack data structure - class template")

add_executable(stack-class-template)

target_include_directories(stack-class-template PRIVATE "${CMAKE_SOURCE_DIR}") # project root
target_sources(stack-class-template PRIVATE
    "main.cpp"
    "Utility/Console.cpp"
)

`main.cpp`

#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::string;

#include "Stack.hpp"
#include "Utility/Console.hpp"

template <typename T>
void testStack(Stack<T>& stack, // reference to the Stack<T>
               T value, // initial value to be pushed
               T increment, // increment for subsequent values
               const std::string& stackName); // name of the Stack <T> object

int main()
{
    BANNER();

    HEAD1("Stack Implementation with Class Template");

    HEAD2("Test - stack with double values");
    Stack<double> doubleStack(5);
    testStack(doubleStack, 1.1, 1.1, "doubleStack");
    END();

    HEAD2("Test - stack with int values");
    Stack<int> intStack;
    testStack(intStack, 1, 1, "intStack");
    END();

    PAUSE();
    return 0;
}

// Function template to manipulate Stack<T>
template <typename T>
void testStack(Stack<T>& stack, // reference to the Stack<T>
               T value, // initial value to be pushed
               T increment, // increment for subsequent values
               const std::string& stackName) // name of the Stack <T> object
{
    string delim = "";

    cout << "Pushing elements onto " << stackName << ":\n";
    while (stack.push(value)) {
        cout << delim << value;
        value += increment;
        delim = ", ";
    }
    cout << "\n"
         << "Stack is full. Cannot push " << value << "." << endl;

    cout << "Popping elements from " << stackName << ":\n";
    delim = "";
    while (stack.pop(value)) {
        cout << delim << value;
        delim = ", ";
    }
    cout << "\n"
         << "Stack is empty. Cannot pop." << endl;
}

`Stack.hpp`

#ifndef STACK_H_
#define STACK_H_

template <typename T>
class Stack
{
public:
    Stack(int = 10); // default constructor (stack size 10)
    ~Stack(); // destructor
    bool push(const T&); // push an element onto the stack
    bool pop(T&); // pop an element off the stack
private:
    int size; // number of elements in the stack
    int top; // location of the top element
    T* stackPtr; // pointer to the stack

    bool isEmpty() const;
    bool isFull() const;
};

// Why can templates only be implemented in the header file?
//     https://stackoverflow.com/a/495056/6888571
#include "Stack.inl.hpp"

#endif // STACK_H_

`Stack.inl.hpp`

#include "Stack.hpp"

// Constructor with default size 10
template <typename T>
Stack<T>::Stack(int s)
{
    size = s > 0 ? s : 10;
    top = -1; // Stack is initially empty
    stackPtr = new T[size]; // allocate space for elements
}

template <typename T>
Stack<T>::~Stack()
{
    delete[] stackPtr;
}

// Push an element onto the stack
// return 1 if successful, 0 otherwise
template <typename T>
bool Stack<T>::push(const T& pushValue)
{
    if (isFull()) {
        return false;
    }
    stackPtr[++top] = pushValue; // add an item onto the stack
    return true; // push successfully
}

// Pop an element off the stack
template <typename T>
bool Stack<T>::pop(T& popValue)
{
    if (isEmpty()) {
        return false;
    }
    popValue = stackPtr[top--]; // remove an item from the stack
    return true; // pop successfully
}

template <typename T>
bool Stack<T>::isEmpty() const
{
    return top == -1;
}

template <typename T>
bool Stack<T>::isFull() const
{
    return top == size - 1;
}

`Utility/Console.cpp`

#include <iostream>

#include "Utility/Console.hpp"

/* <iostream> */
using std::cout;
using std::endl;

/* <string> */
using std::string;

static void _HEAD_INTERNAL(const string& text, char ch);

void BANNER()
{
    cout << R"classtemplate(
______________________________
      __
    /    )   /
---/--------/----__---__---__-
  /        /   /   ) (_ ` (_ `
_(____/___/___(___(_(__)_(__)_


__________________________________________________
  ______
    /                           /
---/-------__---_--_------__---/----__--_/_----__-
  /      /___) / /  )   /   ) /   /   ) /    /___)
_/______(___ _/_/__/___/___/_/___(___(_(_ __(___ _
                      /
                     /
)classtemplate";
}

void HEAD1(const string& text)
{
    string tildes(text.length(), '*');
    cout << tildes << "\n";
    cout << text << "\n";
    cout << tildes << "\n\n";
}

void HEAD2(const string& text)
{
    _HEAD_INTERNAL(text, '=');
}

void HEAD3(const string& text)
{
    _HEAD_INTERNAL(text, '-');
}

void END()
{
    cout << endl;
}

void CUT()
{
    string line(80, '=');
    cout << line << "\n" << endl;
}

// Portable system("pause")
void PAUSE()
{
    cout << "Press enter to continue..." << endl;
    std::cin.get();
}

static inline void _HEAD_INTERNAL(const string& text, char ch)
{
    string line(text.length(), ch);
    cout << text << "\n";
    cout << line << "\n\n";
}

`Utility/Console.hpp`

#ifndef CONSOLE_H_
#define CONSOLE_H_

#include <string>

void BANNER();
void HEAD1(const std::string& text);
void HEAD2(const std::string& text);
void HEAD3(const std::string& text);
void END();
void CUT();
void PAUSE();

#endif // CONSOLE_H_