C++ 如何实现顺序栈(使用模板类)

#ifndef Stack_h #define Stack_h const int maxSize = 50; template  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  #include "Stack.h" using namespace std; const int stackIncreament = 20; // 栈溢出时扩展空间的增量 //类的前置声明 template  class SeqStack; //友元函数的声明 template  ostream& operator<<(ostream &out, SeqStack &s); template  class SeqStack: public Stack { // 顺序栈的类定义 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<< (ostream &out, SeqStack &s); // 输出栈中元素的重载操作 private: T *elements; // 存放栈中元素的栈数组 int top; // 栈顶指针 int maxSize; // 栈最大可容纳的元素个数 void overflowProcess(); // 栈的溢出处理 }; template  SeqStack::SeqStack(int sz) { // 构造函数，建立一个空栈 top = -1; maxSize = sz; elements = new T[maxSize]; // 创建栈的数组空间 if(elements == NULL) { cerr << "内存空间分配失败！" << endl; exit(1); } } template  SeqStack::~SeqStack() { // 析构函数 delete []elements; } template  void SeqStack::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  void SeqStack::Push(const T x) { // 把x插入到栈顶,如果栈满，进行溢出处理 if(isFull() == true) // 栈满则溢出处理 overflowProcess(); elements[++top] = x; // top自增1，并存储x } template  bool SeqStack::Pop() { // 如果栈为空，不进行出栈，否则把栈顶元素出栈 if(isEmpty()) // 判断栈空否，若空则返回false return false; top--; // 栈顶减1，相当于把这个栈顶元素删掉 return true; } template  bool SeqStack::getTop(T &x)const { // 返回栈顶元素的值 if(isEmpty()) // 判断栈空否，若空则返回false return false; x = elements[top]; // 返回栈顶元素的值 return true; } template  bool SeqStack::isEmpty()const { // 判断栈是否为空 if(top == -1) return true; return false; } template  bool SeqStack::isFull()const { // 判断栈是否为空 if(top == maxSize-1) return true; return false; } template  int SeqStack::getSize()const { // 返回栈中元素的个数 return top+1; } template  void SeqStack::makeEmpty() { // 清空栈的内容 top = -1; // 将top赋值-1，相当于清空数组内容 } template  ostream& operator<<(ostream &out, SeqStack &s) { // 友元函数 // 输出栈中元素的重载操作 out << "top=" << s.top << endl; // 输出栈顶位置 for(int i = 0; i <= s.top; i++) // 逐个输出栈中元素的值 out << i << ":" << s.elements[i] << endl; return out; }

#include  #include "SeqStack.h" using namespace std; int main(int argc, const char * argv[]) { bool finished = false; int choice, n, val; // choice：选择 SeqStack 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 > 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; }