顺序存储栈的实现

2013-08-18 15:35:11

顺序存储的栈的实现，包括初始化、销毁、push、pop、求长度、显示栈中元素、获取栈顶元素等基本操作。

注意：

通过动态申请的空间一定要销毁，本实现在InitStack函数中申请空间，使用完后在函数DestoryStack中销毁；
栈显示时，注意下标的更新不是在while条件判断时，应在显示元素之后，如下：

1 //while (base++ < top)   //下面要显示base指向的内容，因此此处不能改动
2     while (base < top)
3     {
4         cout<<*(base)<<"	";
5         base++;
6     }

代码（测试暂未发现错误，欢迎交流指正！）：

  1 #include <iostream>
  2 #include <cassert>
  3 using namespace std;
  4 
  5 const size_t MAXSIZE = 100;
  6 typedef int DataType; 
  7 
  8 typedef struct stack
  9 {
 10     size_t stackSize;
 11     DataType *base;
 12     DataType *top;
 13 }Stack;
 14 
 15 //初始化栈
 16 void InitStack(Stack &s)
 17 {
 18     s.base = new DataType[MAXSIZE];
 19     s.top = s.base;
 20     s.stackSize = MAXSIZE;
 21 }
 22 
 23 //初始化栈
 24 void DestoryStack(Stack &s)
 25 {
 26     delete [] s.base;
 27 }
 28 
 29 //出栈
 30 void PushStack(Stack &s,DataType data)
 31 {
 32     assert ( (s.top - s.base) < s.stackSize);  //检查是否溢出
 33     *s.top++ = data;
 34 }
 35 
 36 //入栈
 37 DataType PopStack(Stack &s)
 38 {
 39     assert ( s.top != s.base); //检查是否为空
 40     return *(--s.top);
 41 }
 42 
 43 //获取栈顶元素
 44 DataType GetTopOfStack(Stack &s)
 45 {
 46     assert ( s.top != s.base); //检查是否为空
 47     return *(s.top - 1);
 48 }
 49 
 50 //获取栈中元素个数
 51 size_t GetLengthOfStack(Stack &s)
 52 {
 53     return (s.top - s.base);
 54 }
 55 
 56 void DisplayStack(Stack &s)
 57 {
 58     DataType *base = s.base;
 59     DataType *top = s.top;
 60 
 61     //while (base++ < top)   //下面要显示base指向的内容，因此此处不能改动
 62     while (base < top)
 63     {
 64         cout<<*(base)<<"	";
 65         base++;
 66     }
 67     cout<<endl;
 68 }
 69 
 70 //栈测试
 71 void TestStack()
 72 {
 73     Stack s;
 74     InitStack(s);
 75     size_t command = 0;
 76 
 77     const size_t PUSH = 0;
 78     const size_t POP = 1;
 79     const size_t GETLENGTH = 2;
 80     const size_t GETTOP = 3;
 81 
 82     DataType data;
 83 
 84     cout<<"Please enter the command ,end with ctrl+z : "<<endl;
 85     while (cin>>command)
 86     {
 87         switch(command)
 88         {
 89         case(PUSH):
 90             {
 91                 cout<<"Please enter z data to push : "<<endl;
 92                 cin>>data;
 93                 cout<<"push "<<data<<endl;
 94 
 95                 cout<<"the stack before push : "<<endl;
 96                 DisplayStack(s);
 97 
 98                 PushStack(s,data);    
 99 
100                 cout<<"the stack after push : "<<endl;
101                 DisplayStack(s);
102 
103                 break;
104             }
105 
106         case(POP):
107             {
108                 cout<<"the stack before pop : "<<endl;
109                 DisplayStack(s);
110 
111                 cout<<"pop "<<PopStack(s)<<endl;    
112 
113                 cout<<"the stack after pop : "<<endl;
114                 DisplayStack(s);
115 
116                 break;
117             }
118 
119         case(GETLENGTH):
120             {
121                 cout<<"the length of stack is : "<<GetLengthOfStack(s)<<endl;
122 
123                 break;
124             }
125 
126         case(GETTOP):
127             {
128                 cout<<"the top element of stack is : "<<GetTopOfStack(s)<<endl;
129 
130                 break;
131             }
132         default:
133             break;
134         }
135         cout<<"Please enter the command ,end with ctrl+z : "<<endl;
136     }
137 
138     DestoryStack(s); //销毁栈
139 }
140 
141 
142 int main()
143 {
144     TestStack();
145     return 0;
146 }

测试结果：

Please enter the command ,end with ctrl+z :
0
Please enter z data to push :
1
push 1
the stack before push :

the stack after push :
1
Please enter the command ,end with ctrl+z :
0
Please enter z data to push :
2
push 2
the stack before push :
1
the stack after push :
1       2
Please enter the command ,end with ctrl+z :
0
Please enter z data to push :
3
push 3
the stack before push :
1       2
the stack after push :
1       2       3
Please enter the command ,end with ctrl+z :
0
Please enter z data to push :
4
push 4
the stack before push :
1       2       3
the stack after push :
1       2       3       4
Please enter the command ,end with ctrl+z :
2
the length of stack is : 4
Please enter the command ,end with ctrl+z :
3
the top element of stack is : 4
Please enter the command ,end with ctrl+z :
4
Please enter the command ,end with ctrl+z :
1
the stack before pop :
1       2       3       4
pop 4
the stack after pop :
1       2       3
Please enter the command ,end with ctrl+z :
1
the stack before pop :
1       2       3
pop 3
the stack after pop :
1       2
Please enter the command ,end with ctrl+z :
1
the stack before pop :
1       2
pop 2
the stack after pop :
1
Please enter the command ,end with ctrl+z :
1
the stack before pop :
1
pop 1
the stack after pop :

Please enter the command ,end with ctrl+z :
1
the stack before pop :

Assertion failed: s.top != s.base, file e:visual studio 2010_projectssequence_
stack_2013_08_17sequence_stack_2013_08_17sequence_stack.cpp, line 39
请按任意键继续. . .