数据结构与算法（C语言） | 栈和队列——栈(自己做过测试)

曾经终败给现在 2023-10-18 13:51 70阅读 0赞

栈是一种重要的线性结构，通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。（后进先出）

–栈的元素必须“后进先出”。

–栈的操作只能在这个线性表的表尾进行。

–注：对于栈来说，这个表尾称为栈的栈顶（top），相应的表头称为栈底（bottom）。

•因为栈的本质是一个线性表，线性表有两种存储形式，那么栈也有分为栈的顺序存储结构和栈的链式存储结构。

•最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。

//栈的顺序存储结构  
typedef struct  
\{  
ElemType \*base;  
ElemType \*top;  
int stackSize;  
\}sqStack;  
顺序栈  
//----- 栈的动态分配顺序存储结构 -----  
\#define STACK\_INIT\_SIZE 100 //顺序栈初始容量  
\#define STACKINCREMENT 10 //顺序栈容量增量  
typedef struct \{  
SElemType \*base; //顺序栈基地址(栈底指针)  
SElemType \*top; //栈顶指针  
int stacksize; //顺序栈当前存储容量  
\}SqStack;  
初始化

//----- 基本操作的算法描述 -----  
Status InitStack( SqStack &S ) \{  
// 构造一个空栈 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  
返回栈顶元素

Status GetTop( SqStack S, SElemType &e ) \{  
// 若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK;  
// 否则返回 ERROR  
if (S.top = = S.base) return ERROR;  
e = \*(S.top-1);  
return OK;  
\}//GetTop  
压入栈

Status Push( SqStack &S, SElemType e ) \{  
// 在栈 S 中插入元素 e 为新的栈顶元素  
if (S.top-S.base>=S.stacksize) \{ // 栈满，追加存储空间  
newbase=(SElemType\*)realloc(S.base,  
(S.stacksize+STACKINCREMENT)\*sizeof(SElemType));  
if (!newbase) exit(OVERFLOW); // 存储分配失败  
S.base = newbase;  
S.top = S.base+S.stacksize;  
S.stacksize += STACKINCREMENT;  
\}  
\*S.top++ = e;  
return OK;  
\}//Push  
弹出栈

Status Pop( SqStack S, SElemType &e ) \{  
// 若栈不空，则删除 S 的栈顶元素，用 e 返回其值,  
// 并返回 OK; 否则返回 ERROR  
if (S.top = = S.base) return ERROR;  
e = \*--S.top;  
return OK;  
\}//Pop  
  
注：c语言中->和.的区别——->用于指针， .用于对象

"->"用于指向结构成员，它的左边应为指向该结构类型的指针（结构指针），而"."的左边应为该结构类型的变量（结构变量），如已定义了一个结构体struct student，里面有一个int a；然后有一个结构体变量struct student stu及结构体变量指针struct student \*p；且有p=&stu，那么p->a和stu.a表示同一个意思。

实例分析：

•题目：利用栈的数据结构特点，将二进制转换为十进制数。

•分析：地球人都知道，二进制数是计算机数据的存储形式，它是由一串0和1组成的，每个二进制数转换成相应的十进制数方法如下：

(XnXn-1……X3X2X1)2 = X1\*2^0+X2\*2^1+…+Xn\*2^(n-1)

•一个二进制数要转换为相应的十进制数，就是从最低位起用每一位去乘以对应位的积，也就是说用第n位去乘以2^(n-1)，然后全部加起来。

由于栈具有后进先出的特性，例如我们输入11001001这样的二进制数

\#include<stdio.h>  
\#include<stdlib.h>  
\#include<math.h>  
  
\#define STACK\_INIT\_SIZE 20  
\#define STACKINCREMENT 10  
  
typedef char ElemType;  
typedef struct  
\{  
ElemType \*base;  
ElemType \*top;  
int stackSize;  
\}sqStack;  
  
void InitStack(sqStack \*s)  
\{  
s->base = (ElemType \*)malloc(STACK\_INIT\_SIZE\*sizeof(ElemType));  
if(!s->base)  
\{  
exit(0);  
\}  
s->top = s->base;  
s->stackSize = STACK\_INIT\_SIZE;  
\}  
  
void Push(sqStack \*s,ElemType e)  
\{  
if(s->top-s->base >= s->stackSize )  
\{  
s->base = (ElemType \*)realloc(s->base,(s->stackSize + STACKINCREMENT)\*sizeof(ElemType));  
if(!s->base)  
\{  
exit(0);  
\}  
s->top = s->base + s->stackSize;  
s->stackSize = s->stackSize + STACKINCREMENT;  
\}  
\*(s->top) = e;  
s->top++;  
  
\}  
void Pop(sqStack \*s,ElemType \*e)  
\{  
if(s->top == s->base)  
\{  
return;  
\}  
\*e = \*--(s->top);  
\}  
  
int StackLen(sqStack s)  
\{  
return (s.top - s.base);  
//不是地址的相减而是内容  
\}  
int main()  
\{  
ElemType c;  
sqStack s;  
int len, i, sum = 0;  
InitStack(&s);  
printf("请输入二进制书，输入\#符号表示结束！\\n");  
scanf("%c",&c);  
while(c!= '\#')  
\{  
Push(&s, c);  
scanf("%c",&c);  
\}  
//清理键盘缓冲区 回车的ASCII=10  
getchar();  
len = StackLen(s);  
printf("栈的当前容量是：%d\\n",len);  
for(i=0; i<len ; i++)  
\{  
Pop(&s,&c);  
sum = sum + (c-48) \* pow(2, i);  
\}  
printf("转化为十进制为：%d \\n",sum);  
return 0;  
\}  
二进制转化为八进制、二进制转化为十六进制：

二进制每三位转化为一个八进制

修改一下以上的主函数部分：

int main()  
\{  
ElemType c;  
sqStack s1;  
sqStack s2;  
int len, i, j, sum = 0;  
  
InitStack(&s1); // 初始化栈s1，用来存放二进制输入  
  
printf("请输入二进制数，输入‘\#’号表示结束！\\n\\n");  
scanf("%c", &c);  
while( c != '\#' )  
\{  
if( c=='0' || c=='1' ) // 检查输入是否二进制  
Push(&s1, c);  
scanf("%c", &c);  
\}  
getchar(); // 把'\\n'从缓冲区去掉  
len = StackLen(s1);  
  
InitStack(&s2); // 初始化栈s2，用来存放转换的八进制  
  
for( i=0; i < len; i+=3 )  
\{  
for( j=0; j < 3; j++ )  
\{  
Pop( &s1, &c ); // 取出栈顶元素  
sum = sum + (c-48) \* pow(2, j);  
  
if( s1.base == s1.top )  
\{  
break;  
\}  
\}  
  
Push( &s2, sum+48 );  
sum = 0;  
\}  
  
printf("\\n转化为八进制数是: ");  
while( s2.base != s2.top )  
\{  
Pop( &s2, &c );  
printf("%c", c);  
\}  
printf("(O)\\n");  
  
return 0;  
\}  
二进制每四位有一个十六进制与之呼应

int main()  
\{  
ElemType c;  
sqStack s1;  
sqStack s2;  
int len, i, j, sum = 0;  
  
InitStack(&s1); // 初始化栈s1，用来存放二进制输入  
  
printf("请输入二进制数，输入‘\#’号表示结束！\\n\\n");  
scanf("%c", &c);  
while( c != '\#' )  
\{  
if( c=='0' || c=='1' ) // 检查输入是否二进制  
Push(&s1, c);  
scanf("%c", &c);  
\}  
getchar(); // 把'\\n'从缓冲区去掉  
len = StackLen(s1);  
  
InitStack(&s2); // 初始化栈s2，用来存放转换的八进制  
  
for( i=0; i < len; i+=4 )  
\{  
for( j=0; j < 4; j++ )  
\{  
Pop( &s1, &c ); // 取出栈顶元素  
sum = sum + (c-48) \* pow(2, j);  
  
if( s1.base == s1.top )  
\{  
break;  
\}  
\}  
  
switch( sum )  
\{  
case 10: sum = 'A'; break;  
case 11: sum = 'B'; break;  
case 12: sum = 'C'; break;  
case 13: sum = 'D'; break;  
case 14: sum = 'E'; break;  
case 15: sum = 'F'; break;  
default: sum += 48;  
\}  
  
Push( &s2, sum );  
sum = 0;  
\}  
  
printf("\\n转化为十六进制数是: ");  
while( s2.base != s2.top )  
\{  
Pop( &s2, &c );  
printf("%c", c);  
\}  
printf("(H)\\n");  
  
return 0;  
\}  
链式栈

teypedef struct StackNode  
\{  
ElemType data; // 存放栈的数据  
struct StackNode \*next;  
\} StackNode, \*LinkStackPtr;  
teypedef struct LinkStack  
\{  
LinkStackPrt top; // top指针  
int count; // 栈元素计数器  
\}

实践：计算数学表达式(1-2)\*(4+5)

简介：逆波兰表达式

——后来，在20世纪三十年代，波兰逻辑学家Jan.Lukasiewicz不知道是像牛顿一样被苹果砸到脑袋而想到万有引力原理，或者还是像阿基米德泡在浴缸里突发奇想给皇冠是否纯金做验证，总之他也是灵感闪现了，然后发明了一种不需要括号的后缀表达式，我们通常把它称为逆波兰表达式(RPN) 。

•如果用逆波兰表示法，应该是这样：1 2 – 4 5 + \*

实现对逆波兰输入的表达式进行计算，并且支持带小数点的数据。  
\---------------------

linux上面编译的时候需要加上-lm选项，因为上面的类引用了\#include <math.h>

gcc zhan.c -o zhan -lm

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70][]  
作者：Shannon333  
来源：CSDN  
原文：https://blog.csdn.net/qq\_35924276/article/details/81384826  
版权声明：本文为博主原创文章，转载请附上博文链接！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190117105944236.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70