数据结构基础之栈

  继续上一篇博客的话题,继续总结数据结构的相关知识,此篇博客主要总结栈的基本概念、存储结构、基本操作以及应用,栈是一种操作受限的线性表,只允许在表的一端进行插入和删除,也正因为它的这个特点,使得栈的应用十分广泛,比如数制转换、表达式求值等问题的解决都用到栈以及栈在递归中的重要作用。

栈的基本概念

定义:只允许在表的一端进行插入和删除的操作的线性表。

栈顶:允许插入和删除的一端。

特点:后进先出(Last In First Out,LIFO)。

顺序栈

7-1

对栈顶指针进行初始化时,可以将其初始化为-1,也可以初始化为0,当初始化为-1时栈顶指针指向的元素即为栈顶元素,而初始化为0时,栈顶指针减1所指向的元素才是栈顶元素,具体区别如下:

初始化栈顶指针S->top = -1时
1
2
初始化栈顶指针S->top = 0时
1
2
3
4
5
6
7
8
9
10
11
栈顶元素为S->data[S->top - 1]
进栈操作:先送值到栈顶元素,栈顶指针再加1,即S->data[S->top++] = x
出栈操作:先将栈顶指针减1,再取栈顶元素值,即x = S->data[–S->top]
栈空条件:S->top = 0
栈满条件:S->top = MAXSIZE
栈长:S-top
基本操作实现

下面以将栈顶指针初始化为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
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define MAXSIZE 100 //定义栈的最大容量
#define true 1
#define false 0
typedef struct{
ElemType data[MAXSIZE]; //存放栈中元素的数组
int top; //栈顶指针
}SeqStack;
/******构造一个空栈******/
void InitStack(SeqStack *S)
{
S->top = 0; //栈顶指针初始化为0
}
/*******判断栈空*******/
int StackEmpty(SeqStack *S){
if(S->top == 0)
return true;
else
return false;
}
/***********出栈操作***********/
int Pop(SeqStack *S,ElemType *e)
{
if(S->top == 0) //若栈空出栈失败
return false;
*e = S->data[-- S->top]; //修改栈顶指针,并保存栈顶元素
return true;
}
/***********进栈操作***********/
int Push(SeqStack *S,ElemType e)
{
if(S->top == MAXSIZE) //若栈满则进栈失败
return false;
S->data[S->top ++] = e; //将e插入栈顶,并修改栈顶指针
return true;
}
/***********取栈顶元素***********/
int GetTop(SeqStack *S,ElemType *e){
if(S->top == 0) //若栈空取栈顶元素失败
return false;
*e = S->data[S->top-1]; //保存栈顶元素
return true;
}
int main()
{
SeqStack S;
InitStack(&S);
....
进行进栈、出栈、判断栈空等操作
....
}

链栈

  利用单链表结构来实现的栈,即栈中的每一个数据元素用一个结点来表示,同时设置一个指针top来指示栈顶元素的当前位置。

7-2

特点
  • 便于多个栈共享存储空间
  • 不存在栈满溢出的情况
  • 操作与链表类似,便于结点的插入和删除
基本操作实现
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
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define false 0
#define true 1
typedef struct SNode{
ElemType data; //数据域
struct SNode *next; //指针域
}SNode;
typedef struct{
SNode *top; //栈顶指针
}LinkStack;
/*******构造一个空栈*******/
int InitStack(LinkStack *S){
S = (LinkStack *)malloc(sizeof(LinkStack)); //分配栈顶指针的内存空间
if(S == NULL) //内存分配失败
return false;
S->top = NULL; //栈顶指针置为空
return true;
}
/**********置栈空**********/
void ClearStack(LinkStack *S)
{
S->top = NULL; //将栈顶指针置为空
}
/*********判断栈空********/
int StackEmpty(LinkStack *S)
{
return S->top == NULL; //判断栈顶指针是否为空
}
/***********进栈操作***********/
int Push(LinkStack *S,ElemType e){
SNode *temp;
temp = (SNode *)malloc(sizeof(SNode)); //生成新的结点
if(temp == NULL) //内存分配失败
return false;
temp->data = e; //赋值给结点数据域
temp->next = S->top; //插入栈顶
S->top = temp; //修改栈顶指针
return true;
}
/***********出栈操作***********/
int Pop(LinkStack *S,ElemType *e){
SNode *temp;
if(S->top == NULL) //若栈为空则出栈失败
return false;
temp = S->top;
S->top = temp->next; //修改栈顶指针
*e = temp->data; //保存栈顶元素
free(temp); //释放出栈结点
return true;
}
/***********取栈顶元素***********/
int GetTop(LinkStack *S,ElemType *e){
if(S->top == NULL) //若栈为空则无法获取栈顶元素
return false;
*e = S->top->data; //取栈顶指针指向的元素
return true;
}
int main()
{
LinkStack S;
InitStack(&S);
....
进行进栈、出栈、判断栈空等操作
....
}

共享栈

  为了避免出现有的栈溢出有的栈空闲的情况,可以让多个栈共享一个足够大的数组空间,是存储空间得到充分利用。常见的是两栈共享空间,即让两个栈共享一个一维数组空间,使两个栈的栈底分别设置在共享空间的两端,两个栈顶向共享空间的中间延伸。

7-3

特点

  同样,由于初始化的不同会出现两种情况,这里以初始化栈1的栈顶指针为0,栈2的栈顶指针为MAXSIZE-1为例进行说明:

1
2
3
4
5
6
7
8
9
栈满条件:S->top1 = S->top2 + 1
栈空条件:S->top1 = 0 或 S->top2 = MAXSIZE - 1
进栈操作:栈1:先赋值栈顶指针再加1,栈2:先赋值栈顶指针再减1
出栈操作:栈1:栈顶指针先减1再赋值,栈2:栈顶指针先加1再赋值
栈顶元素:栈1:S->data[S->top1-1],栈2:S->data[S->top2-1]

  如果初始化栈1的栈顶指针为-1,栈2的栈顶指针为MAXSIZE会有什么不同呢?还是自己想一想吧,这里就不给出啦。

基本操作实现

  下面是初始化为 0 和 MAXSIZE-1 的情况:

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
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define MAXSIZE 100 //定义栈的最大容量
#define true 1
#define false 0
typedef struct{
ElemType data[MAXSIZE]; //两栈共享的数组空间
int top[2]; //两栈的栈顶指针
}DSeqStack;
/*********构造一个空栈*********/
void InitStack(DSeqStack *S)
{
S->top[0] = 0; //初始化栈1的栈顶指针
S->top[1] = MAXSIZE-1; //初始化栈2的栈顶指针
}
/*********判断栈是否为空*********/
int StackEmpty(DSeqStack *S,int i){
switch(i){
case 1:
return (S->top[0] == 0? true:false); //判断栈1是否为空
break;
case 2:
return (S->top[1] == MAXSIZE-1? true:false); //判断栈2是否为空
break;
default:
return false; //参数错误
}
}
/**************进栈操作**************/
int Push(DSeqStack *S,ElemType e,int i)
{
if(S->top[0] == S->top[1]+1) //判断栈空间是否满
return false;
switch(i){
case 1:
S->data[S->top[0]] = e; //将e压入第1个栈
S->top[0]++;
break;
case 2:
S->data[S->top[1]] = e; //将e压入第2个栈
S->top[1]--;
break;
default:
return false; //参数错误
}
return true;
}
/**************出栈操作**************/
int Pop(DSeqStack *S,ElemType *e,int i)
{
switch(i){
case 1:
if(S->top[0] == 0) //判断栈1是否为空
return false;
S->top[0]--; //修改栈1的栈顶指针
*e = S->data[S->top[0]]; //从第1个栈中弹出
break;
case 2:
if(S->top[1] == MAXSIZE-1) //判断栈2是否为空
return false;
S->top[1]++; //修改栈2的栈顶指针
*e = S->data[S->top[1]]; //从第2个栈中弹出
break;
default:
return false; //参数错误
}
return true;
}
int main()
{
DSeqStack S;
InitStack(&S);
....
进行进栈、出栈、判断栈空等操作
....
}

栈的应用

数制转换

数制转换过程中我们得到的结果序列往往是我们所要结果的逆序,这时候就需要栈来帮忙了。比如,将十进制数12转换成二进制序列,过程如下:

1
2
3
4
5
6
12/2 = 6...0
6/2 = 3...0
3/2 = 1...1
1/2 = 0...1
依次得到0011,但是12的二进制表示为1100,即为逆序。

所以我们需要将每次得到的余数压入栈中,一直到没有元素需要压入栈中时再将元素依次从栈中弹出,即得到正确的结果。以十进制转K进制为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Conversion(int n,int k){
ElemType x;
SeqStack S;
InitStack(&S);
while(n>0){
x = n%k;
Push(&S,x); //将得到的余数依次压入栈中
n = n/k;
}
while(!StackEmpty(&S)){
Pop(&S,&x);
printf("%d",x);
}
}

  栈的应用还有很多,比如括号匹配的检验、表达式求值,以及栈在递归中的重要作用。这里就不再一一描述了,以后在 Leetcode 上看到类似的题目再进行说明。

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