栈结构——顺序栈、链栈

Published on:
Tags: 数据结构 栈

栈结构的定义和属性#

定义：栈是一种与线性表相似的线性结构。
不同之处是当需要对节点做增删操作时，只能操作栈顶的节点，因此具有先进后出（或者后进先出）的特点。

按存储结构的不同，可分为顺序栈和链栈。

栈结构的几个属性：

  • 栈顶/栈底：可接受节点增删操作的一端称为栈顶，另一端称为栈底
  • 入栈：在栈顶一端新增节点的操作称为入栈
  • 出栈：在栈顶一端删除节点的操作称为出栈
  • 栈满：当栈中节点超过允许存储空间时，表示栈满（链栈无栈满的状态）
  • 栈空：当栈中无节点元素时，表示栈空

栈结构的抽象数据类型#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ADT Stack
{
数据对象：
    D = {ai | ai ∈ ElemType, i=1,2,…,n, n>=0 }              // ElemType为类型标识符
数据关系：
    R = {<ai, ai+1> | ai, ai+1∈D, i=1,3,…,n-1 }
数据操作：
    (1) stackSeq * InitStack();    				//	初始化栈
    (2) void DestroyStack(stackSeq *s); 		//	销毁栈
    (3) Bool StackEmpty(stackSeq *s);   		//	栈是否为空
    (4) Bool StackFull(stackSeq *s);    		//	栈是否为满
    (5) int StackLength(stackSeq *s);  			//	返回栈中元素个数——栈长度
    (6) Bool Push(stackSeq *s,ElemType e); 		//	入栈
    (7) void Pop(stackSeq *s,ElemType *e); 		//	出栈
    (8) Bool GetTop(stackSeq *s,ElemType *e); 	//	取栈顶数据元素
    (9) void DispStack(stackSeq *s);  			//	输出栈
}

对比线性表的抽象数据类型可以发现，栈的抽象数据类型少了 返回指定序号的元素 和 返回指定元素的序号 两个方法，并且插入节点和删除节点方法也有位置上的限制，这些在计算上的限制正是栈结构的特点，因此栈也被称为受限的线性表。

顺序栈#

顺序栈的存储结构是利用一组地址连续的存储空间依次存放自栈底到栈顶的数据元素，同时设置栈顶元素的下标 top 指向栈顶元素的位置。

定义顺序栈的存储结构：

1
2
3
4
5
6
7
8
#define MaxSize 50

typedef char ElemType;
typedef struct Node
{
    ElemType data[MaxSize];
    int top;                
} stackSeq;

顺序栈代码实现：

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
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 50
#define true 1
#define false 0

typedef int Bool;
typedef char ElemType;
typedef struct Node
{
    ElemType data[MaxSize];
    int top;                
} stackSeq;                          

//初始化栈
stackSeq * InitStack();    
//销毁栈
void DestroyStack(stackSeq *s);  
//栈是否为空
Bool StackEmpty(stackSeq *s);    
//栈是否为满
Bool StackFull(stackSeq *s);     
//返回栈中元素个数——栈长度
int StackLength(stackSeq *s);  
//入栈
Bool Push(stackSeq *s,ElemType e); 
//出栈
void Pop(stackSeq *s,ElemType *e); 
//取栈顶数据元素
Bool GetTop(stackSeq *s,ElemType *e); 
//输出栈
void DispStack(stackSeq *s);  

int main()
{
    ElemType e;
    stackSeq *s;
    printf("(1)初始化栈s\n");
    s = InitStack();
    printf("(2)栈为%s\n",(StackEmpty(s) == 1?"空":"非空"));
    printf("(3)依次进栈元素a,b,c,d,e\n");
    Push(s,'a');
    Push(s,'b');
    Push(s,'c');
    Push(s,'d');
    Push(s,'e');
    printf("(4)栈为%s\n",(StackEmpty(s) == 1?"空":"非空"));
    printf("(5)栈长度:%d\n",StackLength(s));
    printf("(6)从栈顶到栈底元素:");DispStack(s);
    printf("(7)出栈序列:");
    while (!StackEmpty(s))
    {
        Pop(s,&e);
        printf("%c ",e);
    }
    printf("\n");
    printf("(8)栈为%s\n",(StackEmpty(s) == 1?"空":"非空"));
    printf("(9)释放栈\n");
    DestroyStack(s);
    return 0;
}

stackSeq * InitStack()
{
    stackSeq *tmp = (stackSeq *)malloc(sizeof(stackSeq));
    tmp->top = -1;
    return tmp;
}

Bool StackEmpty(stackSeq *s)
{
    if (s->top == -1)
        return true;
    else
        return false;  
}

Bool StackFull(stackSeq *s)
{
    if (s->top == MaxSize-1)
        return true;
    else
        return false;  
}

Bool Push(stackSeq *s,ElemType e)
{
    //  判断是否满栈
    if(StackFull(s)) return false;
    s->top++;
    s->data[s->top] = e;
    return true;
}

int StackLength(stackSeq *s)
{
    return s->top + 1;
}

void DispStack(stackSeq *s)
{
    int top = s->top;
    while (top > -1)
    {
        printf("%c\t",s->data[top]);
        top--;
    }
    printf("\n");
}

void Pop(stackSeq *s,ElemType *e)
{
    *e = s->data[s->top];
    s->top--;
}

void DestroyStack(stackSeq *s)
{
    free(s);
}

链栈#

链栈的实现与头插法的链表很相似。

链栈的存储结构定义为：

1
2
3
4
5
6
typedef int ElemType;
typedef struct Node
{
    ElemType data;              
    struct Node *next;      
} stackLink;

链栈的存储结构与链表一样，区别在于链表的指针始终指向第一个节点，而链栈的指针始终指向栈顶节点。

链栈的存储结构也可以定义为：

1
2
3
4
5
6
7
8
9
10
11
>typedef int ElemType;
>typedef struct Node
>{
   ElemType data;              
   struct Node *next;      
>} stackNode; 

>typedef struct
>{
   stackNode *top;
>} stackLink;

但是结构体变量 stackLink 只包含一个成员，所以直接把成员定义成变量。

因为 struct Node *next 与 stackNode *top 一样作用，所以直接使用结构体变量 stackNode 初始化链栈。

最后链栈的存储结构定义为：

1
2
3
4
5
6
>typedef int ElemType;
>typedef struct Node
>{
   ElemType data;              
   struct Node *next;      
>} stackLink;

链栈的抽象运算与顺序栈一致，但是由于存储结构不一样，所以具体实现也完全不一样。

链栈代码实现：

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
127
128
129
130
131
132
133
134
135
136
#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

typedef char ElemType;
typedef int Bool;

typedef struct Node
{
    ElemType data;              
    struct Node *next;      
} stackLink;                      

//  初始化栈
stackLink * InitStack();    
//  销毁栈
void DestroyStack(stackLink *s);  
//  栈是否为空
Bool StackEmpty(stackLink *s);    
//  链栈没有栈满的概念
Bool StackFull(stackLink *s);     
//  返回栈中元素个数——栈长度
int StackLength(stackLink *s);  
//  入栈
Bool Push(stackLink *s,ElemType e); 
//  出栈
void Pop(stackLink *s,ElemType *e); 
//  取栈顶数据元素
Bool GetTop(stackLink *s,ElemType *e); 
//  输出栈
void DispStack(stackLink *s);  


int main()
{
    ElemType e;
    stackLink *s;
    printf("(1)初始化链栈s\n");
    s = InitStack();
    printf("(2)链栈为%s\n",(StackEmpty(s) == 1?"空":"非空"));
    printf("(3)依次进链栈元素a,b,c,d,e\n");
    Push(s,'a');
    Push(s,'b');
    Push(s,'c');
    Push(s,'d');
    Push(s,'e');
    printf("(4)链栈为%s\n",(StackEmpty(s) == 1?"空":"非空"));
    printf("(5)链栈长度:%d\n",StackLength(s));
    printf("(6)从链栈顶到链栈底元素:");DispStack(s);
    printf("(7)出链栈序列:");
    while (!StackEmpty(s))
    {   Pop(s,&e);
        printf("%c ",e);
    }
    printf("\n");
    printf("(8)链栈为%s\n",(StackEmpty(s) == 1?"空":"非空"));
    printf("(9)释放链栈\n");
    DestroyStack(s);
    return 0;
}

//初始化栈
stackLink * InitStack()
{
    //栈头节点
    stackLink *tmp = (stackLink *)malloc(sizeof(stackLink));
    tmp->next = NULL;
    return tmp;
}

Bool StackEmpty(stackLink *s)
{
    if(s->next == NULL)
        return true;
    else
        return false; 
}

//  入栈
Bool Push(stackLink *s,ElemType e)
{
    stackLink *tmp = (stackLink *)malloc(sizeof(stackLink));
    tmp->data = e;
    tmp->next = s->next;
    s->next = tmp;
}

void DispStack(stackLink *s)
{
    stackLink *tmp;
    tmp = s->next;
    while(tmp != NULL){
        printf("%c\t",tmp->data);
        tmp = tmp->next;
    }
    printf("\n");
}

int StackLength(stackLink *s)
{
    int n = 0;
    stackLink *tmp;
    tmp = s->next;
    while(tmp != NULL){
        n++;
        tmp = tmp->next;
    } 
    return n;
}

//  出栈
void Pop(stackLink *s,ElemType *e)
{
    stackLink *tmp = s->next;
    *e = tmp->data;
    s->next = tmp->next;
    free(tmp);
}

//  销毁栈
void DestroyStack(stackLink *s)
{
    if(s != NULL) 
    {
        stackLink *tmp = s->next,*q;
        while (tmp != NULL)
        {
            q = tmp;
            tmp = tmp->next;
            free(q);
        }
        free(s);
    }
}