栈的逻辑结构

在这里插入图片描述

栈的定义

栈是限定仅在表的一段进行插入和删除操作的线性表，允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何元素的栈称之为空栈。栈具有后进先出的特性。

栈 的顺序存储结构–顺序栈

栈的顺序存储结构称之为顺序栈。

顺序栈的C语言实现

#include<stdio.h>
#include<stdlib.h>

//假设栈元素最多100个
#define StackSize 100
//定义栈的数据类型为int
typedef int DataType;

//定义栈的结构体
typedef struct{
	
	//存放栈元素的数组
	DataType data[StackSize];
	//栈顶位置，栈顶元素在数组的下标
	
	int top;
	
}SeqStack;

//栈的初始化
//初始化一个空的顺序栈，只需将栈顶位置top置为-1
void InitStack(SeqStack * S){
	
	S->top = -1;
}

//顺序栈的销毁
//顺序栈是静态存储分配，在顺序栈变量退出作用域时自动释放顺序栈所占的存储单元，即，顺序栈无需销毁。


//入栈操作
int Push(SeqStack * S ,DataType x){
	
	
	if(S->top == StackSize -1){
		printf("上溢错误，插入失败\n");
		return 0;
	}
	S->data[++S->top] = x;
	return 1;
}

//出栈操作
int Pop(SeqStack * S,DataType * ptr){
	
	
	if(S->top == -1 ){
		
		printf("下溢错误，删除失败\n");
		return 0;
	}
	//top-- 操作先赋值，在进行运算。即在结束时，top自动减一。
	//被删除的元素通过ptr指针返回
	*ptr = S->data[S->top--];
	return 1;
}

//取栈顶元素

int GetTop(SeqStack * S,DataType * ptr){
	
	if(S->top == -1){
		printf("下溢错误，取栈顶失败\n");
		return 0;
	}
	*ptr = S->data[S->top];
	return 1;
}

//判空操作
int Empty(SeqStack * S ){
	
	if(S->top == -1)
		return 1;
	else 
		return 0;
	
}


//顺序栈的使用
int main(){
	
	DataType x;
	SeqStack S;
	
	//初始化
	InitStack(&S);
	
	
	printf("对1 2 3进行入栈操作\n");
	Push(&S,1);
	Push(&S,2);
	Push(&S,3);
	
	if(GetTop(&S,&x) == 1){
		printf("栈顶元素为%d\n",x);
	}
	
	//进行出栈操作
	Pop(&S,&x);
	printf("出栈的元素为%d\n",x);
	
	Pop(&S,&x);
	printf("出栈的元素为%d\n",x);
	
	if(GetTop(&S,&x) == 1){
		printf("栈顶元素为%d\n",x);
	}
	
	printf("请输入待入栈的元素\n");
	scanf("%d",&x);
	Push(&S,x);
	
	if(Empty(&S) == 1){
		printf("栈为空\n");
	}else{
		printf("栈非空\n");
	}
	
	return 0;

}

在这里插入图片描述