顺序栈

摘要：本文主要介绍了顺序栈的实现和具体的应用。

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> &copy);  //复制构造函数
23     SqStack<ElemType>& operator=(const SqStack<ElemType>&copy);  //重载赋值运算符
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> &copy) {
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>&copy) {
87     if (&copy!=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 }