摘要:本文主要介绍了顺序栈的实现和具体的应用。
SqStack.h
1 #pragma once
2 #ifndef _SQSTACK_
3 #define _SQSTACK_
4
5 template<class ElemType>
6 class SqStack
7 {
8 protected:
9 int count;
10 int maxSize;
11 ElemType *elems;
12 public:
13 SqStack(int size);
14 virtual~SqStack();
15 int Lence();
16 bool Empty();
17 void Clear();
18 bool Push(const ElemType &e); //在栈顶添加元素
19 void Traverse(void(*visit)(const ElemType&)); //遍历栈中的元素
20 bool Top(ElemType &e); //用e返回栈顶元素
21 bool Pop(ElemType &e); //删除栈顶元素
22 SqStack(const SqStack<ElemType> ©); //复制构造函数
23 SqStack<ElemType>& operator=(const SqStack<ElemType>©); //重载赋值运算符
24 };
25
26
27 #endif // !_SQSTACK_
SqStack.cpp
1 #include "SqStack.h"
2
3
4 template<class ElemType>
5 SqStack<ElemType>::SqStack(int size){
6 count = 0;
7 maxSize = size;
8 elems = new ElemType[maxSize];
9 }
10
11 template<class ElemType>
12 SqStack<ElemType>::~SqStack()
13 {
14 delete[] elems;
15 }
16
17 template<class ElemType>
18 int SqStack<ElemType>::Lence() {
19 return count;
20 }
21
22 template<class ElemType>
23 bool SqStack<ElemType>::Empty() {
24 return count == 0;
25 }
26
27 template<class ElemType>
28 void SqStack<ElemType>::Clear() {
29 count = 0;
30 }
31
32 template<class ElemType>
33 bool SqStack<ElemType>::Push(const ElemType &e) {
34 if (count==maxSize) {
35 return false;
36 }
37 else {
38 elems[count++] = e;
39 return true;
40 }
41 }
42
43 template<class ElemType>
44 void SqStack<ElemType>::Traverse(void(*visit)(const ElemType&)) {
45 for (int pos = 1; pos<=Lence(); pos++)
46 {
47 (*visit)(elems[pos-1]);
48 }
49 }
50
51 template<class ElemType>
52 bool SqStack<ElemType>::Top(ElemType &e){
53 if (Empty()) {
54 return false;
55 }
56 else {
57 e = elems[count-1];
58 return true;
59 }
60 }
61
62 template<class ElemType>
63 bool SqStack<ElemType>::Pop(ElemType &e) {
64 if (Empty()) {
65 return false;
66 }
67 else {
68 e = elems[count-1];
69 count--;
70 return true;
71 }
72 }
73
74 template<class ElemType>
75 SqStack<ElemType>::SqStack(const SqStack<ElemType> ©) {
76 maxSize = copy.maxSize;
77 elems = new ElemType[maxSize];
78 count = copy.count;
79 for (int pos=1;pos<=Lence();pos++)
80 {
81 elems[pos - 1] = copy.elems[pos-1];
82 }
83 }
84
85 template<class ElemType>
86 SqStack<ElemType>& SqStack<ElemType>::operator=(const SqStack<ElemType>©) {
87 if (©!=this) {
88 maxSize = copy.maxSize;
89 delete[] elems;
90 elems = new ElemType[maxSize];
91 count = copy.count;
92
93 for (int pos = 1; pos <= Lence(); pos++)
94 {
95 elems[pos - 1] = copy.elems[pos - 1];
96 }
97 }
98 }
main.cpp
1 #include<iostream>
2 #include "SqStack.cpp"
3
4 using namespace std;
5
6 void show(const int &e) {
7 cout << e << endl;
8 }
9
10 void test() {
11 SqStack<int> s(5);
12 s.Push(10);
13 s.Push(20);
14 s.Push(30);
15 void(*pt)(const int &);
16 pt = show;
17 s.Traverse(pt);
18 int a;
19 s.Pop(a);
20 cout << a << endl; //返回30
21 s.Top(a);
22 cout << a << endl; //返回20
23 SqStack<int> s1(s);
24 s1.Traverse(pt); //返回10,20
25 SqStack<int> s2 = s;
26 s2.Traverse(pt); //返回10,20
27 }
28
29 int main() {
30 test();
31 system("pause");
32 return 0;
33 }