【C语言数据结构5】--栈的实现

举报
北山啦 发表于 2021/07/19 22:55:41 2021/07/19
【摘要】 栈 一、什么是栈 栈是一种特殊的线性表,我们可以认为栈是一种阉割版的线性表。它的插入、删除操作只能在栈顶进行。因此造就了它后进先出(LIFO)的特征。 在生活中有很多栈的例子,比如平时吃的冰糖葫芦,我们需要先吃掉上面的才能吃下面的(虽然不是这样,但是希望大家配合一下)。又比如我们脱衣服,要把外面的衣服脱了才能脱里面的衣服。 我们可以看一下下面的图片: ...

一、什么是栈

栈是一种特殊的线性表,我们可以认为栈是一种阉割版的线性表。它的插入、删除操作只能在栈顶进行。因此造就了它后进先出(LIFO)的特征。

在生活中有很多栈的例子,比如平时吃的冰糖葫芦,我们需要先吃掉上面的才能吃下面的(虽然不是这样,但是希望大家配合一下)。又比如我们脱衣服,要把外面的衣服脱了才能脱里面的衣服。

在这里插入图片描述

我们可以看一下下面的图片:

在这里插入图片描述

中间部分就是一个栈,而栈最顶端的部分就是栈顶。栈最常用的两个操作就是进栈(入栈)和出栈操作。这组操作就是插入删除操作,它们只允许在栈顶进行。

进栈操作就是将新数据放入栈顶的上方(逻辑上),然后变成栈的新栈顶。而出栈操作则是将栈顶元素删除,然后让栈顶下方的元素作为栈顶。

二、栈的表示

我们可以用顺序存储和链式存储两种结构来实现栈,下面我们分别看看用两种存储结构如何表示一个栈。

(1)顺序存储结构

这里和顺序表的表示是类似的,但是我们需要设置一个栈顶指针。

#define MAXSIZE 20
typedef int ElemType;
typedef struct{ ElemType data[MAXSIZE];		//静态数组,用于存放栈的元素 int top; //栈顶指针
}SqStack;

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

在结构体中定义了一个静态数组用于存放栈中的数据,另外还需要定义一个栈顶指针。栈顶指针会一直指向数组中最后一个元素的下标(栈顶元素)。

(2)链式存储结构

链式存储结构实现的栈和单链表是类似的,结构体如下:

typedef struct SNode{ ElemType data;			//数据域 struct SNode *next;		//指针域
}*LinkedStack;

  
 
  • 1
  • 2
  • 3
  • 4

这里就不详细解释了。

因为栈的操作是限制在栈顶的,因此不存在线性表中大量移动数据的问题,因此我们选择用顺序存储结构来实现栈的各个操作。

三、栈的实现

(1)栈的初始化

顺序存储我们同样可以使用两种方式来实现,一种是通过静态数组的方式,另一种是通过malloc函数动态申请内存的方式。

对于前者我们的初始化只需要初始化栈顶,对于后者我们还需要使用malloc分配内存。两种差别不大,这里我们选择用前者实现。

/**
*	用于初始化栈S
*/
int InitSqStack(SqStack *S){ //将栈顶指向-1 S->top = -1; return 1;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

在前面我们说过,栈顶指针会一直指向栈顶元素的下标。这里之所以不设置为0是因为,如果栈顶为0,那就表示栈中又一个元素。因此初始化时我们设置为-1。

(2)入栈

入栈的图示如下:

在这里插入图片描述

入栈操作我们需要判断栈是否满了,如果满了则返回0,如果没满则需要移动栈顶指针,再将元素入栈。

int Push(SqStack *S, ElemType elem){ //如果栈满了,则top == MAXSIZE-1,此时不进行入栈操作,返回0 if(S->top == MAXSIZE-1){ return 0; } //移动栈顶指针 S->top++; //将入栈元素放置在栈顶 S->data[S->top] = elem; return 1;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

我们还可以将移动指针和元素放入栈顶的操作合并成一句:

//先进行++S->top移动指针,再将元素赋值到新top的位置
S->data[++S->top] = elem;

  
 
  • 1
  • 2

不过鉴于可读性差了许多。作者认为,在代码不会影响执行效率的情况下,还是不要为了追求代码简短而放弃可读性。

(3)出栈

出栈操作和入栈操作是相反的。图示如下:

在这里插入图片描述

我们先判断是否栈空,如果栈中有数据,则先获取数据,再移动栈顶指针。

int Pop(SqStack *S, ElemType *elem){ //如果栈为空,则top==-1,此时不进行出栈操作 if(S->top == -1){ return 0; } //获取栈顶元素 *elem = S->data[S->top]; //移动栈顶指针 S->top--; return 1;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

因为我们要获取出栈的数据,因此这里传入的elem是一个指针。

(4)清空栈

清空栈的操作我们只需要完成逻辑上的清空即可,即将栈的top赋值为-1,代码如下:

void ClearStack(SqStack *S){ //将栈顶指向-1 S->top = -1;
}

  
 
  • 1
  • 2
  • 3
  • 4

(5)栈判空

栈判空我们只需要判断top是否指向-1即可:

int EmptyStack(SqStack S){ //如果S.top==-1则返回1,如果S.top!=-1则返回0 return S.top == -1 ? 1 : 0;
}

  
 
  • 1
  • 2
  • 3
  • 4

上面使用了三元运算符,我们可以把上面的代码翻译成如下:

int EmptyStack(SqStack S){ if(S.top == -1){ return 1; }else{ return 0; }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

(6)获取栈顶元素

除了出栈,我们还可以提供一个获取栈顶元素的操作。它和出栈的区别就是它不会移动栈顶指针(不会删除栈中元素),因此它的操作要比出栈简单:

int GetTop(SqStack S, ElemType *elem){ if(S.top == -1){ return 0; } *elem = S.data[S.top]; return 1;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

除了上面的操作,我们还可以实现很多其它操作。这里就不再细说了。

四、栈的应用

栈有很多应用,可能刚开始接触栈会觉得这种结构非常多余。但是其实操作系统很多功能都是基于栈这种结构的,像是数值运算,程序递归,括号匹配等都可以用栈来实现。下面我们来实现几个简单的例子。

(1)逆序输出

现在我们要求实现输入一个序列,然后按照与这个序列输入相反的顺序输出。

这里我们利用栈先进后出的特性。我们将序列的数据依次入栈,再依次出栈输出即可达到逆序输出效果,代码如下:

void ReversePrint(int n){ ElemType temp; SqStack S; InitSqStack(&S); //将输入元素依次入栈 for(int i = 0; i < n; ++i){ scanf("%d", &temp); Push(&S, temp); } //将元素出栈并输出 for(int i = 0; i < n; ++i){ Pop(&S, &temp); printf("%d\t", temp); }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

(2)进制转换

在进制转换中,栈同样扮演者逆序输出的作用。

将10进制数N转换成d进制数的原理如下:
N 1 = N / d s 1 = N 1 % d N 2 = N 1 / d s 2 = N 2 % d . . . N n = N n − 1 / d s n = N n % d N_1 = N/d \\ s_1 = N_1\%d \\ N_2 = N_1/d \\ s_2 = N_2\%d \\...\\ N_n = N_{n-1}/d \\ s_n = N_n \%d N1=N/ds1=N1%dN2=N1/ds2=N2%d...Nn=Nn1/dsn=Nn%d
其中%为取模操作。我们先对十进制数进行除操作,然后将除的结果取模。最终N的d进制数为:
s n s n − 1 . . . s 1 s_ns_{n-1}...s_1 snsn1...s1
我们实际操作一下,这里N取1348,d取8:

N N/d N%d
1348 168 4
168 21 0
21 2 5
2 0 2

最后得出10进制数1348的8进制为2504。下面我们用代码来实现一下:

void conversion(){ int n; //用于获取出栈元素 ElemType e; SqStack S; InitSqStack(&S); scanf("%d", &n); while (n){ //把式中s放入栈 Push(&S, n % 8); n = n / 8; } while (!EmptyStack(S)){ //逆序输出 Pop(&S, &e); printf("%d\t", e); }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

(3)括号匹配

括号匹配的大致步骤如下:

  1. 依次判断字符串内容
  2. 如果是左括号则直接入栈
  3. 如果是右括号则匹配栈顶是否是对应的右括号
  4. 如果匹配成功则入栈继续匹配,如果匹配失败则返回0
  5. 遍历完字符后,如果栈为空,则匹配成功。如果栈非空,则匹配失败

我们可以用几个例子模拟一下:

([)]
()()()
([][]{})
([][]{}))

  
 
  • 1
  • 2
  • 3
  • 4

这里就不详细分析了,下面是具体代码:

int match(char str[], int len){ ElemType elem; SqStack S; InitSqStack(&S); for(int i = 0; i < len; i++){ //如果是左括号则直接入栈 if(str[i] == '(' || str[i] == '[' || str[i] == '{'){ Push(&S, str[i]); //如果是右括号,则进行匹配 }else if(str[i] == ')'){ //匹配成功则出栈 if(GetTop(S, &elem) && elem == '('){ Pop(&S, &elem); }else{ return 0; } }else if(str[i] == ']'){ if(GetTop(S, &elem) && elem == '['){ Pop(&S, &elem); }else{ return 0; } }else if(str[i] == '}'){ if(GetTop(S, &elem) && elem == '{'){ Pop(&S, &elem); }else{ return 0; } } } if(EmptyStack(S)){ return 1; }else{ 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

另外大家可以用栈实现一些其它算法。

文章来源: zacksock.blog.csdn.net,作者:ZackSock,版权归原作者所有,如需转载,请联系作者。

原文链接:zacksock.blog.csdn.net/article/details/118907908

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200