顺序栈与链式栈的实现

发表于 | 更新于 | 分类于 | 阅读次数： | 字数： 2,016 | 阅读时长： 10

栈的概念：

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

顺序栈：

base.h

这个头文件主要用来存放公用的常量和类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//base.h
//-----公用的常量和类型----------
#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;
#include<malloc.h>
#include<string.h>

//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1 //不可行的 infeaslble
#define OVERFLOW -2

typedef int Status;
typedef int SElemType;

sq_Stack.h

sq_Stack.h头文件用来具体实体实现栈的基本操作。

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
//sq_stack.h  顺序栈

//-------------栈的顺序存储表示----------------

#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量

typedef struct{
    SElemType *base; //在栈构造之前和销毁之后，base的值为NULL
    SElemType *top; //栈顶指针
    int stacksize;  //当前分配的存储空间，以元素为单位
}SqStack;

//----基本操作的函数原型说明-----------

//构建一个空栈S
Status InitStack_Sq(SqStack &S){
    S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if(!S.base)  //判断是否空间分配成功
        exit(OVERFLOW);
    S.top = S.base; //栈顶与栈底指向同一个位置
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}//InitStack_Sq

//销毁栈S
Status DestroyStack_Sq(SqStack &S){
    if(S.base){
        free(S.base);
        S.top = S.base = NULL;
        S.stacksize = 0;
        cout<<"栈销毁成功！"<<endl;
        return OK;
    }else{
        cout<<"栈不存在,不需要销毁！"<<endl;
        return ERROR;
    }
}//DestroyStack_Sq

//初始条件：栈S存在
//操作结果：清空栈
Status CleanStack_Sq(SqStack &S){
    S.top = S.base;
    return OK;
}//CleanStack_Sq

//初始条件：栈S存在
//操作结果：若为空栈，返回TRUE，否则FALSE
Status StackEmpty_Sq(SqStack S){
    if(S.top == S.base){
        cout<<"栈为空！"<<endl;
        return FALSE;
        }
    else{
        cout<<"栈不为空！"<<endl;
        return TRUE;
        }
}//StackEmpty_Sq

//初始条件：栈S存在
//操作结果：返回栈内元素个数，即栈的长度
int StackLength_Sq(SqStack S){
    int len;
    len = (S.top - S.base);
    return len;
}//StackLength_Sq

//初始条件：栈S存在
//操作结果：用e返回S的栈顶元素
Status GetTop_Sq(SqStack S, SElemType &e){
    if(S.top == S.base)//判空
        return ERROR;
    else{
        e = *(S.top - 1);
        return OK;
 }
}//GetTop_Sq

//初始条件：栈S存在
//操作结果：插入元素e为新的栈顶元素
Status Push_Sq(SqStack &S, SElemType e){
    //判满，追加存储空间
    if(S.top - S.base >= S.stacksize){
        S.base = (SElemType *)realloc(S.base,
          (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
        if(!S.base)//存储分配失败
            exit(OVERFLOW);
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e; //插入元素
    return OK;
}//Push_Sq

//初始条件：栈S存在
//操作结果：删除S的栈顶元素，并用e返回其值
Status Pop_Sq(SqStack &S, SElemType &e){
    if(S.top == S.base) //判空
        return ERROR;
    e = *--S.top; //返回删除元素的值
    return OK;
}//Pop_Sq

//初始条件：栈S存在
//操作结果：遍历栈元素并显示
Status StackTraverse_Sq(SqStack S){
    if(S.base){  //判断栈是否存在
        if(S.top == S.base) //判空
            cout<<"此栈是个空栈！"<<endl;
        else{
            SElemType *p;
            p = S.top;
            while(p > S.base)
            {
                p--;
                cout<<*p<<"  ";
            }
            cout<<endl;
        }
        return OK;
    }else{
        cout<<"栈不存在！"<<endl;
        return ERROR;
    }

}//StackTraverse_Sq

sqStackText.cpp

用来测试顺序栈的基本操作函数。

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
#include "base.h"
#include "sq_stack.h"
//用来测试顺序栈的基本操作
int main(){
    SqStack S;
    SElemType e;
    InitStack_Sq(S);
    StackTraverse_Sq(S);
    //给空栈赋值
    for(e = 0; e<10; e++){
        Push_Sq(S, e);
    }
    cout<<"栈的遍历：";
    StackTraverse_Sq(S);
    Push_Sq(S, 15);
    cout<<"压栈15后栈的遍历：";
    StackTraverse_Sq(S);
    Pop_Sq(S, e);
    cout<<"出栈后栈的遍历：";
    StackTraverse_Sq(S);
    cout<<"被删除的元素是："<<e<<endl;
    GetTop_Sq(S, e);
    cout<<"获取栈顶元素："<<e<<endl;
    cout<<"栈的长度为（即栈内元素个数）："
                <<StackLength_Sq(S)<<endl;
    cout<<"判栈空：";
    StackEmpty_Sq(S);
    cout<<"清空栈!"<<endl;
    CleanStack_Sq(S);
    cout<<"判栈空：";
    StackEmpty_Sq(S);
    cout<<"销毁栈：";
    DestroyStack_Sq(S);
    cout<<"再次销毁栈：";
    DestroyStack_Sq(S);
    return OK;
}

程序运行结果：

顺序栈的运行结果

图：顺序栈测试的运行结果

链式栈：

链式表的具体代码实现：

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
//link_stack.h  链式栈

//-------------栈的链式存储表示----------------

#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量

typedef struct StackNode{
    SElemType date; //数据域
    struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack{
    LinkStackPtr top; //栈顶
    int count; //记录栈元素个数
}*PLinkStack;
//----基本操作的函数原型说明-----------

//构建一个空栈S
Status InitStack_L(PLinkStack* S){
    //分配一个节点的初始化空间
    *S = (PLinkStack)malloc(sizeof(struct LinkStack));
    (*S)->top = NULL; //栈顶指针指向空
    (*S)->count = 0; //栈中元素个数初始为0
    return OK;
}//InitStack_L

//初始条件：栈S存在
//操作结果：清空栈
Status CleanStack_L(PLinkStack &S){
    LinkStackPtr p;
     //栈不为空时,进行循环，释放每一个节点的空间
    while(S->top){
        p = S->top;
        S->top = S->top->next;
        S->count--;
        free(p);
    }
    return OK;
}//CleanStack_L

//销毁栈S
Status DestroyStack_L(PLinkStack* S){
    CleanStack_L(*S); //先清空栈
    free(*S); //释放栈所有空间
    cout<<"栈销毁成功！"<<endl;
    return OK;
}//DestroyStack_L

//初始条件：栈S存在
//操作结果：若为空栈，返回TRUE，否则FALSE
Status StackEmpty_L(PLinkStack S){
    if(S->top){  //栈顶存在
        cout<<"栈不为空！"<<endl;
        return FALSE;
    }else{
        cout<<"栈为空！"<<endl;
        return TRUE;
    }
}//StackEmpty_L

//初始条件：栈S存在
//操作结果：返回栈内元素个数，即栈的长度
int StackLength_L(PLinkStack S){
    return S->count;
}//StackLength_L

//初始条件：栈S存在
//操作结果：用e返回S的栈顶元素
Status GetTop_L(PLinkStack S, SElemType &e){
    if(!S->top)
        return ERROR;
    e = S->top->date;
    return OK;
}//GetTop_L

//初始条件：栈S存在
//操作结果：插入元素e为新的栈顶元素
Status Push_L(PLinkStack &S, SElemType e){
    LinkStackPtr p = (LinkStackPtr)malloc(sizeof(struct StackNode));
    p->date = e;
    p->next = S->top;
    S->top = p;
    S->count++;
    return OK;
}//Push_L

//初始条件：栈S存在
//操作结果：删除S的栈顶元素，并用e返回其值
Status Pop_L(PLinkStack &S, SElemType &e){
   LinkStackPtr p;
   if(!S->top){
        return ERROR;
   }
   e = S->top->date;
   p = S->top;
   S->top = S->top->next;
   S->count--;
   free(p);
   return OK;
}//Pop_L

//初始条件：栈S存在
//操作结果：遍历栈元素并显示
Status StackTraverse_L(PLinkStack S){
    if(S->top){
        LinkStackPtr p;
        p = S->top;
        while(p){
            cout<<p->date<<"  ";
            p = p->next;
        }
        cout<<endl;
        return OK;
    }else{
        cout<<"此栈为空栈！"<<endl;
        return OK;
    }
}//StackTraverse_L

linkStackText

链式栈的测试：

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
void linkStackText(){
    PLinkStack S;
    SElemType e;
    InitStack_L(&S);
    StackTraverse_L(S);
    //给空栈赋值
    for(e = 0; e<10; e++){
        Push_L(S, e);
    }
    cout<<"栈的遍历：";
    StackTraverse_L(S);
    Push_L(S, 15);
    cout<<"压栈15后栈的遍历：";
    StackTraverse_L(S);
    Pop_L(S, e);
    cout<<"出栈后栈的遍历：";
    StackTraverse_L(S);
    cout<<"被删除的元素是："<<e<<endl;
    GetTop_L(S, e);
    cout<<"获取栈顶元素："<<e<<endl;
    cout<<"栈的长度为（即栈内元素个数）："
                <<StackLength_L(S)<<endl;
    cout<<"判栈空：";
    StackEmpty_L(S);
    cout<<"清空栈!"<<endl;
    CleanStack_L(S);
    cout<<"栈的遍历：";
    StackTraverse_L(S);
    cout<<"判栈空：";
    StackEmpty_L(S);
    cout<<"销毁栈：";
    DestroyStack_L(&S);
}

链式栈测试运行结果：

链式栈测试结果

图：链式栈测试结果

坚持原创技术分享，您的支持将鼓励我继续创作！