数据结构

前言

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端成为栈顶，另一端称为栈底。栈中的元素遵循后进先出（LIFO, Last In First Out）原则。

一、栈的介绍

1、栈的英文为(stack)

2、栈是一个先进后出(FILO-First In Last Out)的有序列表。

3、栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。

4、根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。

图解方式说明出栈(pop)和入栈(push)的顺序

二、栈的实现

栈有顺序栈和链栈两种，所以栈的实现可以使用数组实现，也可以使用链表。
但是相对而言数组的结构实现更优一些。

1.栈的结构

由于栈的访问都是在尾上，所以用一个top来标记尾。

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType *a;//存储数据的数组
	int top; //栈顶的位置
	int capacity; //栈能存储的最大容量
}stack;
//静态栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
	STDataType a[N];
	int top; // 栈顶
}Stack;

2.栈的初始化

//栈的初始化
int StackInit(stack *st)
{
	assert(st);   
	//这里给栈的初始大小为4个整型变量的大小
	st->a = (STDataType*)malloc(sizeof(stack)* 4);
	st->top = -1;//给栈顶一个初始值也可设置为其他值
	st->capacity = 4;//给一个初始大小，也可设置为其他值
	return 1;
}

3.进栈

//进栈 
int StackPush(stack *st, STDataType x)
{
	assert(st);
	
	if (st->top == st->capacity)//如果栈满则扩容
	{
		STDataType* tmp = (STDataType*)realloc(st->a, sizeof(stack)* st->capacity * 2);

		if (tmp == NULL)
		{
			exit(-1);//结束整个程序
		}
		st->capacity *= 2;
		st->a = tmp;
	}

	//在top位置插入数据后，top++表示栈顶向后移一个位置
	st->a[st->top++] = x;
	printf("%d进栈成功\n",x); 
}

4.出栈

//出栈 
void StackPop(stack* st)
{
	assert(st);
	//assert(!StackEmpty(st));//判断栈非空，若空则不进行删除操作
	st->top--;//top--即可，下一次数据入栈会直接覆盖top位置的值
}

出栈两次之后只剩下两个栈

5.栈的判断

//判断栈是否为空
void StackEmpty(stack* st)
{
	assert(st);
	if (st->top == -1)//若top为-1，说明栈中没有元素，为空
	{
		printf("栈为空\n"); 
	}
	else
	printf("栈不为空\n"); 
}

//得到栈的数据个数
void StackSize(stack *st)
{
	assert(st);
	printf("有%d个栈\n",(st->top)+1);  //从-1开始所以要初始化为0 
}

6.取栈顶元素

//取栈顶元素 
void StackTop(stack* st)
{
	assert(st);
//	assert(!StackEmpty(st));

	printf( "栈顶为%d\n",st->a[st->top - 1]);
}

7.栈的清空

void Stackclear(stack* st)
{
	assert(st);
	//assert(!StackEmpty(st));//判断栈非空，若空则不进行删除操作
	st->top=-1;//top--即可，下一次数据入栈会直接覆盖top位置的值
	printf("栈清空成功\n");
}

8.栈的销毁

//栈的销毁
void StackDestroy(stack* st)
{
		
	assert(st);
	free(st->a);
	st->a = NULL;
	st->capacity = 0;
	st->top = 0;
	free(st);
	printf("栈销毁成功\n"); 
}

总结

附上完整代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 支持动态增长的栈，本文以动态增长的栈为例
typedef int STDataType;
typedef struct Stack
{
	STDataType *a;//存储数据的数组
	int top; //栈顶的位置
	int capacity; //栈能存储的最大容量
}stack;

//栈的初始化
int StackInit(stack *st)
{
	assert(st);   
	//这里给栈的初始大小为4个整型变量的大小
	st->a = (STDataType*)malloc(sizeof(stack)* 4);
	st->top = -1;//给栈顶一个初始值也可设置为其他值
	st->capacity = 4;//给一个初始大小，也可设置为其他值
	return 1;
}

//进栈 
int StackPush(stack *st, STDataType x)
{
	assert(st);
	
	if (st->top == st->capacity)//如果栈满则扩容
	{
		STDataType* tmp = (STDataType*)realloc(st->a, sizeof(stack)* st->capacity * 2);

		if (tmp == NULL)
		{
			exit(-1);//结束整个程序
		}
		st->capacity *= 2;
		st->a = tmp;
	}
	//在top位置插入数据后，top++表示栈顶向后移一个位置
	st->a[st->top++] = x;
	printf("%d进栈成功\n",x); 
//	if(st->top>3)
//	printf("%d进栈失败\n",x); 
}
//判断栈是否为空
void StackEmpty(stack* st)
{
	assert(st);
	if (st->top == -1)//若top为-1，说明栈中没有元素，为空
	{
		printf("栈为空\n"); 
	}
	else
	printf("栈不为空\n"); 
}

//得到栈的数据个数
void StackSize(stack *st)
{
	assert(st);
	printf("有%d个栈\n",(st->top)+1);  //从-1开始所以要初始化为0 
}
//出栈 
void StackPop(stack* st)
{
	assert(st);
	//assert(!StackEmpty(st));//判断栈非空，若空则不进行删除操作
	st->top--;//top--即可，下一次数据入栈会直接覆盖top位置的值
}
//取栈顶元素 
void StackTop(stack* st)
{
	assert(st);
//	assert(!StackEmpty(st));

	printf( "栈顶为%d\n",st->a[st->top - 1]);
}
//栈的销毁
void StackDestroy(stack* st)
{	
	assert(st);
	free(st->a);
	st->a = NULL;
	st->capacity = 0;
	st->top = 0;
	free(st);
	printf("栈销毁成功\n"); 
}
void Stackclear(stack* st)
{
	assert(st);
	//assert(!StackEmpty(st));//判断栈非空，若空则不进行删除操作
	st->top=-1;//top--即可，下一次数据入栈会直接覆盖top位置的值
	printf("栈清空成功\n");
}
int main()
{
	stack st;
	int ret=StackInit(&st);
	if(ret==1)
	printf("栈初始化成功\n"); 
    StackPush(&st,1);
    StackPush(&st,3);
    StackPush(&st,5);
    StackPush(&st,7);
    StackEmpty(&st);
    StackSize(&st);
    StackPop(&st); 
    StackSize(&st);
    StackPop(&st); 
    StackSize(&st);
    StackTop(&st);
    Stackclear(&st);
    StackSize(&st);
 }