顺序栈和链式栈

1. 基本概念

栈（stack）是一种操作受限的线性数据结构。栈的特点是：先进后出、后进先出。

栈（stack）是限定仅在表尾进行插入和删除操作的线性表。

我们把允许插入和删除的一端叫做栈顶（top），另一端叫做栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称 LIFO 结构。

1.1 栈的操作

• 栈的插入操作，叫做进栈，也称压栈、入栈。
• 栈的删除操作，叫做出栈，也叫作弹栈。

1.2 栈的应用场景

栈的特点是：先进后出，后进先出，在实际应用中经常用栈来实现回溯。

回溯就是返回的意思。例如我们要实现一个走迷宫的程序，无论迷宫那么复杂，从拓扑上来 讲，越复杂的迷宫只是分支越多而已，我们可以用穷举法去遍历不同的分支，一旦遇到死胡同就回溯到上一个岔路口，然后再去遍历下一个分支。

1.3 栈的存储方式

栈的存储方式主要有两种:线性存储和链式存储。

• 线性存储具有实现简单，操作方便的特 点，但是同时也有存储空间有限的缺点。
• 链式存储实现稍微复杂点，但是没有存储容量的限制。

2. 栈的顺序存储结构

栈是线性表的特例，栈的顺序存储其实也是线性表顺序存储的简化，简称为顺序栈。

顺序栈是用数组来实现的，对于栈这种只能一端插入删除的线性表来说，我们用数组下标为 0 的一端作为栈底，因为首元素都存在栈底，变化最小。

2.1 顺序栈的数据类型

由于栈的操作只跟栈顶元素有关，所以我们需要用一个整型变量top保存栈顶元素的下标。

当top为-1时，表示空栈，top+1则表示栈顶元素的数量。

2.2 顺序栈的结点设计

#define STACK_SIZE	50	//初始化有50个元素

typedef char datatype;

struct seq_stack 		//顺序栈的节点设计
{
	datatype *stack;	//栈底
	int top;			//栈顶（元素个数 = top+1）
};

2.3 顺序栈的初始化

struct seq_stack *stack_init(void)
{
	struct seq_stack *stack = malloc(sizeof(struct seq_stack));
	if(stack != NULL)
	{
		stack->stack = malloc(sizeof(datatype) * STACK_SIZE);
		if(stack->stack == NULL)
		{
			free(stack);	
			return NULL;
		}
		stack->top = -1;	//默认为-1
		return stack;	//返回成功初始化的栈底
	}
	return NULL;
}

2.4 判断栈空还是栈满

//栈空
bool stack_is_empty(struct seq_stack *stack)
{
	return stack->top == -1;
}
//栈满
bool stack_is_full(struct seq_stack *stack)
{
	return stack->top == STACK_SIZE-1;
}

2.5 顺序栈的入栈和出栈

// 入栈
void push(struct seq_stack *stack, datatype data)
{
	//判断是否栈满
	if(stack_is_full(stack))
	{
		printf("栈满了\n");
		return ;
	}
	// 入栈操作
	stack->top++;  						// 栈顶指针加一
	stack->stack[stack->top] = data;    // 将新增元素赋值给栈顶空间
}
//出栈
datatype pop(struct seq_stack *stack)
{
	datatype data = stack->stack[stack->top];
	stack->top--;
	
	return data;
}

2.6 栈销毁

void destory_stack(struct seq_stack *stack)
{
	free(stack->stack);
}

3. 栈的链式存储结构

栈的链式存储结构其实就是用链表实现的，简称为链式栈。

栈只是用栈顶来做插入和删除操作的，由于单链表有头指针，而栈顶指针也是必须的，所以把栈顶放在单链表的头部。因为栈顶已经放在单链表的头部了，所以链式栈是不需要头结点的。

链式栈不存在栈满的情况，除非内存已经没有使用的空间。对于空栈来说，链表原定义的是头指针指向空，所以链式栈的空就是top=NULL。

3.1 链式栈的结点设计

//单向链表节点设计
struct node
{
	datatype data;
	struct node *next;
};
//栈的管理结构
struct link_stack
{
	struct node *top;	//栈顶指针
	int size;	//元素个数
};

3.2 链式栈的初始化

struct link_stack *stack_init(void)
{
	struct link_stack *stack = malloc(sizeof(struct link_stack));
	if(stack != NULL)
	{
		stack->top = NULL;		//栈顶为空
		stack->size = 0;	//0个元素
		return stack;
	}
	return NULL;
} 

3.3 判断空栈

bool stack_is_empty(struct link_stack *stack)
{
	return stack->size == 0;
}

3.4 链式栈的入栈

链式栈的入栈就是先创建节点，把数据存储起来，然后让栈顶指针指向该结点，让该结点的后继直接指向当前的栈顶元素。

void push(struct link_stack *stack, datatype data)
{
	//先创建节点，把数据存储起来
	struct node *new = malloc(sizeof(struct node));
	if(new == NULL)
	{
		printf("节点创建失败\n");
		return ;
	}
	new->data = data;
	//把新节点入栈
	new->next = stack->top;  	// 把当前的栈顶元素赋值给新结点的直接后继
	stack->top = new;			// 将新的结点赋值给栈顶指针
	stack->size++;
}

3.5 链式栈的出栈

链式栈的出栈操作就是定义一个临时指针存储栈顶地址，一个临时变量存储栈顶数据，然后让栈顶指针下移一位，然后把原本的栈顶释放掉。

//出栈
datatype pop(struct link_stack *stack)
{
	
	struct node *tmp = stack->top;	//存储栈顶的地址
	datatype data = tmp->data;		//把栈顶的数据取出来临时存储到data
	stack->top = stack->top->next;	//让栈顶指向下一个元素，并且元素减一
	stack->size--;
	
	free(tmp);//把原本栈顶的节点释放
	
	return data;
}

3.5 链式栈的销毁

void destory_stack(struct link_stack *stack)
{
	struct node *tmp = stack->top;
	
	while(stack->top == NULL)
	{
		stack->top = stack->top->next;
		free(tmp);
		tmp = stack->top;
	}
	stack->size = 0;
}