栈的特点和相关操作

1.栈的特点（LIFO）

​ 数据存取关系满足“后进先出，先进后出”的特点的数据结构

​ 逻辑结构：线性

​ 存储结构：顺序存储、链式存储

​ 算法：初始化、压栈、出栈、栈空、栈满判断（顺序栈）

如果有1 2 3 三个数据，依次入栈，出栈情况，错误的是？

A 1 2 3

B 1 3 2

C 2 3 1

D 2 1 3

E 3 2 1

F 3 1 2

2.顺序栈

存储结构连续的，用数组的方式

顺序栈的管理结构体

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int DataType;

typedef struct SequentStack	//栈的管理结构体
{
	DataType *stack;	//用stack指向一块连续的内存空间
	int size;			//size保存了该顺序栈的总大小
	int top;			//用top来指示栈顶元素的偏移量
}Stack;

初始化顺序栈

//初始化顺序栈 传入size
Stack *InitStack(int size)
{
	Stack *s = malloc(sizeof(Stack));
	if(s!=NULL)
	{
		s->stack =calloc(size,sizeof(DataType));//calloc默认初始化为0
		s->size = size;
		s->top = -1;
	}
	return s;
}

//栈空、栈满、出栈、入栈、遍历

//栈空
bool IsStackEmpty(Stack *s)
{
	return (s->top == -1);
}

//栈满
bool IsStackFull(Stack *s)
{
	return (s->top == s->size-1);
}

//入栈
bool push(Stack *s,DataType data)
{
	if(IsStackFull(s)||s==NULL)
		return false;

	//栈顶偏移++
	s->top++;
	//将新的数据放到栈顶
	//*(s->stack + s->top) = data;
	s->stack[s->top]=data;

	return true;
}

//出栈
bool pop(Stack *s,DataType *data)
{
	if(IsStackEmpty(s)||s==NULL)
		return false;

	//先拿到栈顶的数据
	//*data = *(s->stack + s->top);
	*data=s->stack[s->top];
	//栈顶偏移
	s->top--;

	return true;
}

//遍历
void Display(Stack *s)
{
	if(IsStackEmpty(s)||s==NULL)
		return;

	for (int i = 0; i <= s->top; ++i)
		printf("%d\t",s->stack[i]);

	printf("\n");
}

3.链式栈

逻辑结构：线性

存储结构：链式

运算：初始化、压栈、出栈、栈空

链式栈设计数据节点结构体

typedef int DataType;

//数据节点结构体
typedef struct node
{
	DataType data;		//数据
	struct node *next;	//指针
}LinkNode;

//管理结构体
typedef struct stack
{
	struct node *top;		//栈顶偏移 栈顶指针就是节点指针的类型
	int size;				//当前元素个数
}Stack;

初始化链式栈

Stack * InitStack()
{
	Stack * s = malloc(sizeof(Stack));
	if(s!=NULL)
	{
		s->top=NULL;
		s->size=0;
		return s;
	}
}

压栈、出栈、栈空判断、遍历

bool IsStackEmpty(Stack *s)
{
	return (s->size == 0);
}

bool push(Stack *s,DataType data)
{
	LinkNode *newNode = malloc(sizeof(LinkNode));
	if(newNode!=NULL)
	{
		//新节点初始化
		newNode->data = data;
		//新节点next指向原来栈顶
		newNode->next = s->top;
		//将栈顶设置为新节点
		s->top=newNode;
		//元素个数加1
		s->size++;
		return true;
	}
	return false;
}


bool pop(Stack *s,DataType *data)
{
	if(IsStackEmpty(s)||s==NULL)
	{
		return false;
	}
	//先拿到栈顶的数据
	*data = s->top->data;
	//将栈顶往后（向下）偏移一个
	s->top = s->top->next;
	//长度减1
	s->size--;
	return true;

}

void Display(Stack *s)
{
	LinkNode *tmp=s->top;
	int data;
	while(tmp->next!=NULL)
	{
		data = tmp->data;
		printf("%d",data);
		tmp=tmp->next;
	}
}