C语言实现数据结构中的顺序栈

刺骨的言语ヽ痛彻心扉 2022-09-18 07:57 200阅读 0赞

栈(Stack)是限制仅在表的一端进行插入和删除运算的线性表,通常称插入,删除的一段为栈顶(Top),另一端为栈底(Botton)。当表中没有元素时称为空栈.

栈是后进先出(last in first out)的线性表

下面是C语言实现数据结构中的顺序栈及基本算法

\# include <stdio.h>  
\# include <stdlib.h>  
/\*定义顺序栈\*/  
\# define StackSize 100     //假定预分配的栈空间最多为100个元素  
typedef char DataType;     //假定栈元素的数据类型为字符  
typedef struct  
\{  
 DataType data\[StackSize\];  
 int top;  
\}SeqStack;

/\*错误信息输出函数\*/  
void Error(char \*message)  
\{  
 fprintf(stderr,"Error:%s/n",message);  
 exit(1);  
\}

/\*置空栈\*/  
void initStack(SeqStack \*s)  
\{  
 //将顺序栈置空  
 s->top=-1;  
\}

/\*判栈空\*/  
int stackEmpty(SeqStack \*s)  
\{  
 return s->top==-1;  
\}

/\*判栈满\*/  
int stackFull(SeqStack \*s)  
\{  
 return s->top==StackSize-1;  
\}

/\*进栈\*/  
void push(SeqStack \*s,DataType x)  
\{  
 if(stackFull(s))  
 \{  
  Error("Stack overflow");  
 \}  
 //栈顶指针加1后将x进栈  
 s->data\[++s->top\]=x;  
\}

/\*出栈\*/  
DataType pop(SeqStack \*s)  
\{  
 if(stackEmpty(s))  
 \{  
  Error("Stack underflow");  
 \}  
 //栈顶元素返回后将栈顶指针减一  
 return s->data\[s->top--\];  
\}  
/\*取栈顶元素\*/  
DataType getStackTop(SeqStack \*s)  
\{  
 if(stackEmpty(s))  
 \{  
  Error("Stack is empty");  
 \}  
 return s->data\[s->top\];  
\}

void main()  
\{  
 //定义栈  
 SeqStack stack;  
 SeqStack \*s;  
 char inData;  
 char outData;  
 s=&stack;  
 //初始化栈  
 initStack(s);  
 //入栈  
 printf("Please input data/n");  
 while(inData!='/n')  
 \{  
  scanf("%c",&inData);  
  push(s,inData);  
  printf("push %c to stack/n",inData);  
 \}  
 //出栈  
 while(s->top!=-1)  
 \{  
  outData=pop(s);  
  printf("Pop stack %c/n",outData);  
 \}  
\}