顺序栈的表示与实现

81 阅读 0 评论 54 点赞

我是靠谱客的博主神勇电灯胆，这篇文章主要介绍顺序栈的表示与实现，现在分享给大家，希望可以做个参考。

一、顺序表实现

说明
想要使用顺序表实现栈，结构体中应包含栈顶和栈底的指针，同时需要指定栈的存储单元大小（动态可变）。其中栈底指针base用来动态分配栈的内存空间，栈顶指针top用来指定栈顶元素在顺序栈中的位置。
初始化时 $t o p = b a s e$ ，表示栈中无元素，而后每压入一个新的元素，先为栈顶内存赋值，再让栈顶指针指向下一块内存单元。
值得注意的是，栈顶指针总是在栈顶元素的下一个位置。我觉得可以这样理解：假设 $0$ 为最初下标，没有元素时，可以认为此时元素位置是 $- 1$ ，而后加入元素，指针上移，始终比元素下标高一个位置。
另外，对于 $p u s h$ 和 $p o p$ 等各种操作，都应该对栈中元素进行判空或判满处理，以使无错误之虞。
代码

复制代码

//顺序表实现栈
#include<iostream>
#include<cstring>
#include<string>
#define OK 1
#define ERROR -1
#define STACK_INIT_SIZE 1024
#define STACKINCREMENT 128
using namespace std;
typedef int ElemType;
typedef struct {
ElemType *top;
ElemType *base;
int stacksize;
}Stack;
int InitStack(Stack &st)
{
st.base = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);
if (!st.base)
return ERROR;
st.stacksize = STACK_INIT_SIZE;
st.top = st.base;
return OK;
}
int DestroyStack(Stack &st)
{
if (!st.base)
return ERROR;
free(st.base);
return OK;
}
int ClearStack(Stack &st)
{
if (st.base == st.top)
return ERROR;
st.top = st.base;
return OK;
}
bool StackEmpty(Stack &st)
{
return st.top == st.base;
}
int StackLenght(Stack &st)
{
return st.stacksize;
}
int GetTopElem(Stack &st)
{
if (StackEmpty(st))
return ERROR;
return *(st.top - 1);
}
int Push(Stack &st, ElemType e)
{
if (st.top - st.base >= st.stacksize) {
// 如果不够则分配更多空间
st.base = (ElemType *)realloc(st.base, 
(st.stacksize + STACKINCREMENT) * sizeof(ElemType));
if (!st.base)
return ERROR;
st.top = st.base + st.stacksize;
st.stacksize += STACKINCREMENT;
}
*st.top++ = e;
return OK;
}
int Pop(Stack &st, ElemType &e)
{
if (StackEmpty(st))
return ERROR;
e = *--st.top;	// 栈顶指针在栈顶元素的下一个位置
return OK;
}
//学习函数指针详解
void test(Stack &st)
{
ElemType temp;
for (int i = 1;i <= 9;i++)
Push(st, i);
cout <<"top element:"<< GetTopElem(st) << endl;
cout << "stack size:" << (st.top-st.base) << endl;
cout << "inverse:";
for (int i = 1;i <= 9;i++) {
Pop(st, temp);
cout << temp << ' ';
}
cout << endl;
}
int main()
{
Stack s;
InitStack(s);
test(s);
system("pause");
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//顺序表实现栈
#include<iostream>
#include<cstring>
#include<string>
#define OK 1
#define ERROR -1
#define STACK_INIT_SIZE 1024
#define STACKINCREMENT 128
using namespace std;
typedef int ElemType;
typedef struct {
ElemType *top;
ElemType *base;
int stacksize;
}Stack;
int InitStack(Stack &st)
{
st.base = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);
if (!st.base)
return ERROR;
st.stacksize = STACK_INIT_SIZE;
st.top = st.base;
return OK;
}
int DestroyStack(Stack &st)
{
if (!st.base)
return ERROR;
free(st.base);
return OK;
}
int ClearStack(Stack &st)
{
if (st.base == st.top)
return ERROR;
st.top = st.base;
return OK;
}
bool StackEmpty(Stack &st)
{
return st.top == st.base;
}
int StackLenght(Stack &st)
{
return st.stacksize;
}
int GetTopElem(Stack &st)
{
if (StackEmpty(st))
return ERROR;
return *(st.top - 1);
}
int Push(Stack &st, ElemType e)
{
if (st.top - st.base >= st.stacksize) {
// 如果不够则分配更多空间
st.base = (ElemType *)realloc(st.base, 
(st.stacksize + STACKINCREMENT) * sizeof(ElemType));
if (!st.base)
return ERROR;
st.top = st.base + st.stacksize;
st.stacksize += STACKINCREMENT;
}
*st.top++ = e;
return OK;
}
int Pop(Stack &st, ElemType &e)
{
if (StackEmpty(st))
return ERROR;
e = *--st.top;	// 栈顶指针在栈顶元素的下一个位置
return OK;
}
//学习函数指针详解
void test(Stack &st)
{
ElemType temp;
for (int i = 1;i <= 9;i++)
Push(st, i);
cout <<"top element:"<< GetTopElem(st) << endl;
cout << "stack size:" << (st.top-st.base) << endl;
cout << "inverse:";
for (int i = 1;i <= 9;i++) {
Pop(st, temp);
cout << temp << ' ';
}
cout << endl;
}
int main()
{
Stack s;
InitStack(s);
test(s);
system("pause");
return 0;
}