数据结构系列－顺序栈的基本操作

落日映苍穹つ 2022-05-29 03:16 187阅读 0赞

栈(Stack)是限定只能在表尾部进行插入、删除的线性表。也称后进先出的线性表。允许执行插入、删除的那一端成为栈顶，另一端就是栈底，因为只能在栈顶执行操作，所以他是一种特殊的线性表。

既然栈是特殊的线性表，也会有顺序存储和链式存储。

对于栈的顺序存储，就是用数组来实现，将下标０的一端作为栈底，因为首元素都在栈底，变化最小。

顺序栈的数据结构及基本操作：

如果需要改变栈的内容，函数的参数类型为指针，否则是普通参数。

#include "stdio.h"
    #include "stdlib.h"
    #include "io.h"
    #include "math.h"
    #include "time.h"
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 20
    
    typedef int Status;
    typedef int SElemType;
    
    //顺序存储结构的栈
    typedef struct{
    	SElemType data[MAXSIZE];
    	int top;//栈顶指针
    }SqStack;
    
    Status visit(SElemType se){
    	printf(" %d ",se);
    	return OK;
    }
    
    //初始化一个空栈
    Status InitStack(SqStack *S){
    	S->top =-1;
    	return  OK;
    }
    
    //清空栈
    Status ClearStack(SqStack *S){
    	S->top =-1;
    	return OK;
    }
    
    //判断栈是否为null
    Status StackEmpty(SqStack S){
    	if(S.top)
    		return TRUE;
    	else
    		return FALSE;
    }
    
    //返回栈的元素个数
    int StackLength(SqStack S){
    	return S.top+1;
    }
    
    //获取栈定元素,用ｅ返回栈顶元素
    Status GetTop(SqStack S, SElemType *e){
    	if(S.top == -1)
    		return ERROR;
    	else 
    		*e = S.data[S.top];
    	return OK;
    }
    
    //元素入栈到栈顶
    Status Push(SqStack *S, SElemType e){
    	if(S->top == MAXSIZE -1)//栈满
    		return ERROR;
    
    	S->top++;//栈顶指针加１
    	S->data[S->top] =e;
    	return OK;
    }
    
    //弹出栈顶元素
    Status Pop(SqStack *S, SElemType *e){
    	if(S->top == -1)//空栈
    		return ERROR;
    	*e = S->data[S->top];
    	S->top--;
    	return OK;
    }
    
    //遍历栈中的元素
    Status StackTraverse(SqStack S){
    	int i =0;
    	while(i<=S.top){
    		visit(S.data[i++]);
    	}
    	printf("\n");
    	return OK;
    }
    
    int main(){
    	int j;
    	SqStack sS;
    	int e;
    	if(InitStack(&sS) == OK){
    		for(j=1;j<=10;j++)
    			Push(&sS,j);
    	}
    	printf("栈中的元素：");
    	StackTraverse(sS);
    	Pop(&sS,&e);
    	printf("出栈的元素，e=%d \n",e);
    	ClearStack(&sS);
    	printf("清空栈后，栈的长度：%d\n",StackLength(sS));
    }

运行结果：

![Image 1][]

[Image 1]: