数据结构的练习与巩固
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
1 //栈的数据结构类型
2 template <class T>
3 class Stack()
4 {
5 Stack() {};
6 virtual void Push(T& x) = 0; //进栈
7 virtual bool Pop(T& x) = 0; //出栈
8 virtual bool getTop(T& x)const = 0; //取得栈顶
9 virtual bool IsEmpty()const = 0; //判断栈是否空
10 virtual bool IsFull()const = 0; //判断栈是否满
11 virtual int getSize()const = 0; //获取栈长度
12 };
1 //顺序栈
2 const int stackIncrement = 20; //栈的长度增加单位
3 template <class T>
4 class SeqStack :public Stack<T>
5 {
6 private:
7 T* elements;
8 int top;
9 int maxSize;
10 void overflowProcess(); //栈溢出处理
11
12 public:
13 SeqStack(int size = 50); //栈的初始化
14 ~SeqStack() { delete[]elements; } //栈的删除
15 void Push(const T& x); //进栈
16 bool Pop(T& x); //出栈
17 bool getTop(T& x); //获取栈顶
18 bool IsEmpty()const { return top == -1; } //是否栈空
19 bool IsFull()const { return top == maxSize - 1; } //是否栈满
20 int getSize()const { return top + 1; } //获取栈长
21 void makeEmpty() { top == -1; } //置空栈
22 };
23
24 template <class T>
25 void SeqStack<T>::overflowProcess()
26 {
27 T* newArray = new T[maxSize + stackIncrement]; //创建长度增加的数组
28 if (newArray == NULL) //如果创建了空数组
29 { cerr << "创建失败" << endl; exit(1); }
30 for (int i = 0; i <= top; i++) //逐项赋值给新数组
31 newArray[i] = element[i];
32 maxSize += stackIncrement; //将maxSize数值更新
33 delete[]elements; //删除原有栈
34 elements = newArray; //让elements指向新数组的首项
35 };
36
37 template <class T>
38 void SeqStack<T>::Push(const T& x)
39 {
40 if (IsFull() == true)overflowProcess(); //如果栈长度不够，则进行栈溢出操作
41 elements[++top] = x; //将值赋给新栈空间
42 };
43
44 template <class T>
45 bool SeqStack<T>::Pop(T& x)
46 {
47 if (IsEmpty() == true)return false; //如果栈空，则不进行操作
48 x = elements[top--]; //将值取出
49 return true;
50 };
51
52 template <class T>
53 bool SeqStack<T>::getTop(T& x)
54 {
55 if (IsEmpty() == true)return false; //如果栈空，则不进行操作
56 x = elements[top]; //将值取出
57 return true;
58 };