### 資料結構筆記:Stack堆疊

Stack是一種先進後出的資料結構(First In Last Out,FILO)
頂端稱為top
底端稱為bottom
Stack不支持遍歷操作，因為Stack只能查看和取用頂層的內容

Stack的push&pop示意圖:

https://www.programiz.com/dsa/stack

這一篇會試著用矩陣與來實作Stack

Class中實作Stack需要3個成員變數
套用模板的dynamic array stack紀錄內容
int的top紀錄頂部內容的位置
int的capacity記錄這個容器的容量

template <class DataType>
class Stack
{
private:
    DataType *stack;
    int top;
    int capacity;

簡單的constructor和destructor

Stack(int size = SIZE)
    {
        stack = new DataType[SIZE];
        capacity = SIZE;
        top = -1;
    } // constructor
    ~Stack()
    {
        delete[] stack;
    } // destructor

最後就是Stack的常用函式
push()放入內容
pop()拿出內容
peek查看頂部內容
size()回傳容器目前的內容數量

void push(DataType content)
    {
        if (isFull())
        {
            exit(EXIT_FAILURE);
        }
        top++;
        stack[top] = content;
    }
    DataType pop()
    {
        if (isEmpty())
        {
            exit(EXIT_FAILURE);
        }
        DataType temp = stack[top];
        top--;
        return temp;
    }
    DataType peek()
    {
        return stack[top];
    }
    int size()
    {
        return (top + 1);
    }
    

最後就是包含測試資料的完整的程式碼了

#include <iostream>
#include <cstdlib>
using namespace std;

#define SIZE 10
template <class DataType>
class Stack
{
private:
    DataType *stack;
    int top;
    int capacity;

public:
    Stack(int size = SIZE)
    {
        stack = new DataType[SIZE];
        capacity = SIZE;
        top = -1;
    } // constructor
    ~Stack()
    {
        delete[] stack;
    } // destructor

    void push(DataType content)
    {
        if (isFull())
        {
            exit(EXIT_FAILURE);
        }
        top++;
        stack[top] = content;
    }
    DataType pop()
    {
        if (isEmpty())
        {
            exit(EXIT_FAILURE);
        }
        DataType temp = stack[top];
        top--;
        return temp;
    }
    DataType peek()
    {
        return stack[top];
    }
    int size()
    {
        return (top + 1);
    }
    bool isEmpty()
    {
        if (top < 0)
            return true;
        else
            return false;
    }
    bool isFull()
    {
        if (top + 1 == capacity)
            return true;
        else
            return false;
    }
};

int main()
{
    Stack<int> pt(3);

    pt.push(1);
    pt.push(2);

    pt.pop();
    pt.pop();

    pt.push(3);

    cout << "The top element is " << pt.peek() << endl;
    cout << "The stack size is " << pt.size() << endl;

    pt.pop();

    if (pt.isEmpty())
    {
        cout << "The stack is empty\n";
    }
    else
    {
        cout << "The stack is not empty\n";
    }

    return 0;
}