Stack是一種先進後出的資料結構(First In Last Out,FILO)
頂端稱為top
底端稱為bottom
Stack不支持遍歷操作,因為Stack只能查看和取用頂層的內容
Stack的push&pop示意圖:
這一篇會試著用矩陣與來實作Stack
Class中實作Stack需要3個成員變數
套用模板的dynamic array stack紀錄內容
int的top紀錄頂部內容的位置
int的capacity記錄這個容器的容量
template <class DataType> class Stack { private: DataType *stack; int top; int capacity; |
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; } }; |
巴哈拿來做筆記感覺還行
只是程式碼要用這個工具轉bbcode才能用出顏色來比較麻煩