#ifndef Stack_h
#define Stack_h
 
const int maxSize = 50;
 
template <class T>
class Stack {
public:
    Stack(){}; // 構造函數
    void Push(const T x); // 新元素進棧
    bool Pop(); // 棧頂元素出棧
    virtual bool getTop(T &x) const = 0; // 讀取棧頂元素，由x返回
    virtual bool isEmpty() const = 0; // 判斷棧空否
    virtual bool isFull() const = 0; // 判斷棧滿否
    virtual int getSize() const = 0; // 計算棧中元素個數
};
 
#endif /* Stack_h */

#ifndef SeqStack_h
#define SeqStack_h
#include <iostream>
#include "Stack.h"
using namespace std;
 
const int stackIncreament = 20; // 棧溢出時擴展空間的增量
 
//類的前置聲明
template <typename T>
class SeqStack;
 
//友元函數的聲明
template <typename T>
ostream& operator<<(ostream &out, SeqStack<T> &s);
 
 
template <class T>
class SeqStack: public Stack<T>
{ // 順序棧的類定義
public:
    SeqStack(int sz=50); // 構造函數，建立一個空棧
    ~SeqStack(); // 析構函數
    void Push(const T x); // 把x插入到棧頂,如果棧滿，進行溢出處理
    bool Pop(); // 如果棧為空，不進行出棧，否則把棧頂元素出棧
    bool getTop(T &x) const; // 返回棧頂元素的值
    bool isEmpty()const; // 判斷棧是否為空
    bool isFull()const; // 棧是否滿
    int getSize()const; // 返回棧中元素的個數
    void makeEmpty(); // 清空棧的內容
    friend ostream& operator<< <T>(ostream &out, SeqStack<T> &s); // 輸出棧中元素的重載操作
private:
    T *elements; // 存放棧中元素的棧數組
    int top; // 棧頂指針
    int maxSize; // 棧最大可容納的元素個數
    void overflowProcess(); // 棧的溢出處理
};
 
template <class T>
SeqStack<T>::SeqStack(int sz) {
    // 構造函數，建立一個空棧
    top = -1;
    maxSize = sz;
    elements = new T[maxSize]; // 創建棧的數組空間
    if(elements == NULL) {
        cerr << "內存空間分配失敗！" << endl;
        exit(1);
    }
}
 
template <class T>
SeqStack<T>::~SeqStack() {
    // 析構函數
    delete []elements;
}
 
template <class T>
void SeqStack<T>::overflowProcess() {
    // 棧的溢出處理
    T *newArray = new T[maxSize + stackIncreament];
    if(newArray == NULL) {
        cerr << "存儲空間分配失敗！" << endl;
        exit(1);
    }
    // 將elements數組中的值復制到新數組中
    for(int i = 0; i <= top; i++)
        newArray[i] = elements[i];
    maxSize = maxSize + stackIncreament;
    delete []elements;
    elements = newArray; // 復制數組
}
 
template <class T>
void SeqStack<T>::Push(const T x) {
    // 把x插入到棧頂,如果棧滿，進行溢出處理
    if(isFull() == true) // 棧滿則溢出處理
        overflowProcess();
    elements[++top] = x; // top自增1，并存儲x
}
 
template <class T>
bool SeqStack<T>::Pop() {
    // 如果棧為空，不進行出棧，否則把棧頂元素出棧
    if(isEmpty()) // 判斷棧空否，若空則返回false
        return false;
    top--; // 棧頂減1，相當于把這個棧頂元素刪掉
    return true;
}
 
template <class T>
bool SeqStack<T>::getTop(T &x)const {
    // 返回棧頂元素的值
    if(isEmpty()) // 判斷棧空否，若空則返回false
        return false;
    x = elements[top]; // 返回棧頂元素的值
    return true;
}
 
template <class T>
bool SeqStack<T>::isEmpty()const {
   // 判斷棧是否為空
    if(top == -1)
        return true;
    return false;
}
 
template <class T>
bool SeqStack<T>::isFull()const {
    // 判斷棧是否為空
    if(top == maxSize-1)
        return true;
    return false;
}
 
template <class T>
int SeqStack<T>::getSize()const { // 返回棧中元素的個數
    return top+1;
}
 
template <class T>
void SeqStack<T>::makeEmpty() {
    // 清空棧的內容
    top = -1; // 將top賦值-1，相當于清空數組內容
}
 
template <class T>
ostream& operator<<(ostream &out, SeqStack<T> &s) { // 友元函數
    // 輸出棧中元素的重載操作
    out << "top=" << s.top << endl; // 輸出棧頂位置
    for(int i = 0; i <= s.top; i++) // 逐個輸出棧中元素的值
        out << i << ":" << s.elements[i] << endl;
    return out;
}

#include <iostream>
#include "SeqStack.h"
using namespace std;
 
int main(int argc, const char * argv[]) {
    bool finished = false;
    int choice, n, val; // choice：選擇
    SeqStack<int> obj;
    
    while(!finished) {
        cout << "\n*********菜單*********\n";
        cout << "1:建棧\n";
        cout << "2:壓棧\n";
        cout << "3:出棧\n";
        cout << "4:取棧頂元素的值\n";
        cout << "5:棧是否為空\n";
        cout << "6:棧是否滿\n";
        cout << "7:獲取棧中元素的個數\n";
        cout << "8:清空棧的內容\n";
        cout << "9:輸出棧中的所有元素\n";
        cout << "10:退出\n";
        cout << "請輸入選擇[1-10]：\n";
        cin >> choice;
        switch(choice) {
            case 1:
                cout << "請輸入要進棧的元素個數：";
                cin >> n;
                cout << "請輸入要進棧的元素值:" << endl;
                for(int i = 0; i < n; i++) {
                    cin >> val;
                    obj.Push(val);
                }
                break;
            case 2:
                cout << "請輸入要進棧的元素值:" << endl;
                cin >> val;
                obj.Push(val);
                break;
            case 3:
                if(obj.Pop())
                    cout << "出棧成功！" << endl;
                else
                    cout << "出棧失敗！" << endl;
                break;
            case 4:
                if(obj.getTop(val))
                    cout << "棧頂元素為：" << val << endl;
                else
                    cout << "棧為空！" << endl;
                break;
            case 5:
                if(obj.isEmpty())
                    cout << "棧為空！" << endl;
                else
                    cout << "棧不為空！" << endl;
                break;
            case 6:
                if(obj.isFull())
                    cout << "棧滿！" << endl;
                else
                    cout << "棧不滿！" << endl;
                break;
            case 7:
                int size;
                size = obj.getSize();
                cout << "棧中的元素個數為：" << size << endl;
                break;
            case 8:
                obj.makeEmpty();
                break;
            case 9:
                cout << obj << endl; // 重載輸出<<
                break;
            case 10:
                finished = true;
                break;
            default:
                cout << "輸入錯誤，請重新輸入！" << endl;
        } // switch
    } // while
    return 0;
}