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

#define MAX 10        //数组栈的高度
typedef struct Stack
{
	int* number;    //数组充当栈，用一个指针
	int top;        //栈顶标记
}STACK,*STACKLINK;

STACKLINK creatstack()            //创建数组栈
{
	STACKLINK pstack = (STACKLINK)malloc(sizeof(STACK));
	assert(pstack);
    //以下描述数组栈的最初状态
	pstack->number = (int*)malloc(sizeof(int) * MAX);
	pstack->top = -1;        //这里栈顶标记为-1方便操作，当然从0开始也可以
	return pstack;
}

2、数组栈的简单操作

1、入栈操作

void push(STACKLINK pstack, int data)
{
	if (pstack->top + 1 == MAX)        //入栈的时候记得判断栈是否已经满了
	{
		printf("栈已满，无法入栈！\n");
		return;
	}
    //先将top标记做++运算，因为我们创建数组栈的时候将栈顶标记设置为了-1
	pstack->number[++pstack->top] = data;
}

2、出栈操作

void pop(STACKLINK pstack)
{
	if (pstack->top == -1)        //出栈判断栈是否为空
	{
		printf("栈为空，无法出栈！\n");
		return;
	}
	pstack->top--;        //出栈只需要将栈顶标记做--运算就可以了
}

3、判空操作

//栈为空返回1，否则返回0
int empty(STACKLINK pstack)
{
	if (pstack->top == -1)
	{
		return 1;
	}
	return 0;
}

4、获取栈顶元素

int gettopnumber(STACKLINK pstack)
{
	if (empty(pstack))       //取栈顶元素也要判空
	{
		printf("栈为空，无法获取栈顶数据！\n");
		return 0;
	}
	return pstack->number[pstack->top];        //直接返回栈顶标记所在的数据就好了
}

3、运行测试


int main()
{
	int a = 0;
	STACKLINK pstack = creatstack();        //创建数组栈
	for (int i = 0; i < 10; i++)        //测试入栈
	{
		push(pstack, i);
	}
	while (!empty(pstack))        //打印栈顶数据
	{

		printf("%d\t",gettopnumber(pstack));        //打印栈顶数据
		pop(pstack);                            //每次出栈一个元素，循环打印栈顶数据

	}
	printf("\n");
	return 0;
}

4、运行结果

?这里可以看到打印的数据的规律，我们是先从0开始入栈，根据先进后出的规律，在打印栈顶数据的时候确实是先打印的9，这印证了栈结构管理数据的特点

二、链式栈

1、链式栈的创建和封装

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

//数据结构体
typedef struct Node
{
	int data;
	struct Node* next;
}NODE, * NODELINK;

NODELINK linkcreatnode(int data)
{
	NODELINK newnode = (NODELINK)malloc(sizeof(NODE));
	assert(newnode);
	newnode->data = data;
	newnode->next = NULL;
	return newnode;
}

//封装栈结构体
typedef struct Stack
{
	NODELINK listnode;    //这个就相当于栈顶标记
	int size;        //万金油参数，保存当前元素个数
}STACK, * STACKLINK;

STACKLINK linkcreatstack()
{
	STACKLINK pstack = (STACKLINK)malloc(sizeof(STACK));
	assert(pstack);
	pstack->listnode = NULL;
	pstack->size = 0;
	return pstack;

}

2、链式栈的简单操作

1、入栈操作

void linkpush(STACKLINK pstack, int data)
{
	NODELINK newnode = linkcreatnode(data);       //先将数据通过我们写的函数变成一个节点
	newnode->next = pstack->listnode;        //插入操作
	pstack->listnode = newnode;        //将栈顶标记移到新节点上
	pstack->size++;        //记得将万金油参数做++运算

}

2、出栈操作


void linkpop(STACKLINK pstack)
{
        //入栈时不一定判满，但是出栈时一定要判空
	/*if (pstack->listnode == NULL)      //第一种判空（通过判断栈顶节点是否为空判空） 
	{
		printf("栈为空！\n");
		return;
	}*/
	if (pstack->size == 0)	{        //第二种判空（通过万金油参数判空）
		printf("栈为空，无法出栈！\n");
	}
    //出栈操作
	NODELINK nextnode = pstack->listnode->next;
	free(pstack->listnode);        //记得将内存释放掉
	pstack->listnode = nextnode;
	pstack->size--;        //别忘了我们的万金油参数做--运算

}

3、获取栈顶节点里面的数据

int linkgettopnumber(STACKLINK pstack)
{
    //像这种一步一步获取数据的操作，我们称之为剥洋葱
	return pstack->listnode->data;
}

4、链式栈判空

//判空
int linkempty(STACKLINK pstack)
{
    //判空有多种写法
	/*if (pstack->listnode == NULL)  //判空的第一种写法      
	{
		return 1;
	}
	return 0;*/
	return pstack->size == 0;        //判空的第二种写法
}

3、运行测试



int main()
{
	STACKLINK pstack = linkcreatstack();//创建链式栈
	for (int i = 0; i < 11; i++)        //测试入栈操作
	{
		linkpush(pstack, i);
	}
	while (!linkempty(pstack))    //打印数据
	{
		printf("%d\t", pstack->listnode->data);
		linkpop(pstack);        //每次打印完栈顶节点里面的数据后记得要出栈才能继续打印
	}


	return 0;
}

4、运行结果

?我们可以看到效果和上面的数组栈效果是一样的，要根据实际选择数组栈和链式栈

三、双向栈

1、双向栈的实现和创建

可能这个东西很多小伙伴都没听说过哈，我来给大家解释一下双向栈是个什么东西，说白了双向栈就是两个栈公用一个栈顶，左右两边都可以出栈和入栈，“两个栈”都有栈顶标记，当两个栈的栈顶标记只相差一的时候，就代表这个双向栈满了，无法入栈了。当两个栈顶标记为初始值的时候，就代表双向栈为空了，无法出栈和获取栈顶元素了

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

#define MAX 10        //双向栈的长度

enum pushway { left, right };    //采用枚举类型

typedef struct Stack
{
	int* number;
	int lefttop;        //左边的栈顶标记
	int righttop;        //右边栈的栈顶标记
}STACK, * STACKLINK;

STACKLINK creatstack2()        //创建双向栈
{
	STACKLINK pstack = (STACKLINK)malloc(sizeof(STACK));
	assert(pstack);
	pstack->number = (int*)malloc(sizeof(int) * MAX);
	pstack->lefttop = -1;        //左边的栈顶标记
	pstack->righttop = MAX;        //右边的栈顶标记
	return pstack;
}

2、双向栈的简单操作

1、入栈操作

//入栈操作
void doublepush(STACKLINK pstack, int data, enum pushway way)
{
	if (pstack->righttop - pstack->lefttop == 1)//当左边栈顶和右边栈顶相差一的时候，栈满
	{
		printf("栈已满，无法插入！\n");
		return;
	}
	switch (way)        //对传入的形参进行判断，执行不同的语句
	{
	case left:
		pstack->number[++pstack->lefttop] = data;
		break;
	case right:
		pstack->number[--pstack->righttop] = data;
		break;


	}
}

2、出栈操作

//出栈操作
void doublepop(STACKLINK pstack, enum pushway way)
{
	switch (way)
	{
	case left:
		if (pstack->lefttop == -1)
		{
			printf("左栈为空，无法出栈！\n");
			return;
		}
		pstack->lefttop--;
		break;
	case right:
		if (pstack->righttop == MAX)
		{
			printf("右栈为空，无法出栈！\n");
			return;
		}
		pstack->righttop++;
		break;
	
	}
}

3、获取栈顶元素

//获取栈顶元素
int doubletop(STACKLINK pstack, enum pushway way)
{
	switch (way)
	{
	case left:
		return pstack->number[pstack->lefttop];
		break;
	case right:
		return pstack->number[pstack->righttop];
		break;
	
	}
}

4、判空处理

//判空
int doubleempty(STACKLINK pstack)
{
	return pstack->lefttop == -1 && pstack->righttop == MAX;
}

3、运行测试

//增加判断奇偶性的函数，用于主函数里面数据入栈的时候，区分数据从哪边入栈
//判断奇偶性（奇数返回0，偶数返回1）
int isou(int number)
{
	if (number % 2 == 0)
		return 1;
	return 0;
}


int main()
{
	//创建双向栈
	STACKLINK pstack = creatstack2();
	//将偶数数据从右方压入双向栈，奇数从左方压入双向栈
	for (int i = 0; i < 9; i++)
	{
		if (isou(i))
		{
			doublepush(pstack, i, right);
		}
		else
		{
				doublepush(pstack, i, left);
		}
	

	}
	//从左侧输出双向栈
	while (!doubleempty(pstack) && pstack->lefttop != -1)
	{
		printf("%d\t", doubletop(pstack, left));
		doublepop(pstack, left);
	}
	printf("\n");
	//从右侧输出双向栈
	while (!doubleempty(pstack) && pstack->righttop != MAX)
	{
		printf("%d\t", doubletop(pstack, right));
		doublepop(pstack, right);
	}


	return 0;
}