零.前言

栈作为一种数据结构是一种特殊的顺序表，即规定只能在·末尾·进行插入和删除，栈和队列的提出实际是为了减少思考量，比如你发现某个存储结构满足栈的特点，那就不用考虑进行什么头插头删和查找等操作了，直接把想要实现的操作（比如顺序表）写成栈就可以了。

1.栈的特点

栈是一种存储数据的结构，只支持后进先出，通常用顺序表来进行栈的实现。我们实现栈只需要遵循一个原则就是后进后出就足够了。

2.栈的结构

1.逻辑结构

在这里插入图片描述
只能从顶部进行插入和删除。

2.物理结构

物理结构和顺序表时一样的，都是用数组来存储数据。

3.栈的基本操作

1.建立一个栈

typedef struct stack {
	DataType* a;
	int top;
	int capacity;
}ST;

*a表示的是指向栈中元素的指针，top表示指向的栈顶元素的前一个元素，这是因为在进行栈的插入之后top会进行++操作，所以top始终表示的是栈顶元素的前一个元素，进行-1才能获得栈顶的元素。capacity表示的是栈的最大容量，如果容量不够需要进行扩容操作。

2.栈的初始化

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;//top指针指向栈顶的元素
	ps->capacity = 0;//capacity表示的是栈的最大容量
}

栈的初始化即将指针a置为空，将top和capacity置为0.

3.栈的销毁

栈的销毁即将栈中指针所指向空间进行释放，然后将指针置为空，其他值置为0即可。

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

4.打印一个栈

打印一个栈，就要通过top对栈进行遍历，top每进行一次–就进行一次打印。

void PrintStack(ST* ps)
{
	assert(ps);
	int top2 = ps->top;
	while (ps->top>0)
	{
		printf("%d ", ps->a[--ps->top]);
	}
	ps->top = top2;
	printf("\n");	
}

5.判断栈的大小

栈的大小和top有关，因为top表示的是栈顶元素，top-1即为栈的大小。

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

6.判断栈是否为空

由于栈的大小和top有关，所以判断栈是否为空就是判断top是否大于0。

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

这里用的是一个布尔表达式来接收，如果top为0则返回true说明栈为空，如果top大于0，则返回false说明栈不为空。

7.得到栈顶元素

栈顶元素就是top-1表示的元素，其实栈的所有操作都和这个top有关，因为栈只支持后进先出，只需要对栈顶进行研究即可。

int StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

4.栈的插入和删除

1.栈的插入

在进行栈的插入时，我们就需要考虑栈的容量够不够大，即top和capacity的大小关系，如果空间不够则需要进行扩容，我们规定当栈为空时，为其分配四个空间，当栈不为空时为其分配原来二倍的空间。在进行插入时，通过对栈顶指针的修改即可实现。我们在堆区进行插入，方便在删除栈时释放空间。

void StackPush(ST* ps, DataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		DataType* tmp = (DataType*)realloc(ps->a, sizeof(DataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

2.栈的删除

栈的删除操作也是在栈顶进行的，只需要将栈顶指针–即可。同时还要保障栈存在且栈不为空。

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

5.栈的实现

1.ST.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#define DataType int
typedef struct stack {
	DataType* a;
	int top;
	int capacity;
}ST;
void StackInit(ST* ps);
void StackDestroy(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
void StackPush(ST* ps,DataType x);
void StackPop(ST* ps);
int StackTop(ST* ps);
void PrintStack(ST* ps);

2.ST.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "ST.h"
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
void StackPush(ST* ps, DataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		DataType* tmp = (DataType*)realloc(ps->a, sizeof(DataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
int StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}
void PrintStack(ST* ps)
{
	assert(ps);
	int top2 = ps->top;
	while (ps->top>0)
	{
		printf("%d ", ps->a[--ps->top]);
	}
	ps->top = top2;
	printf("\n");	
}

3.test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"ST.h"
void menu()
{
	printf("****1.入栈****2.出栈****\n");
	printf("****3.栈顶元素4.栈是否为空**\n");
	printf("****5.栈的大小0.销毁****\n");
}
int main()
{
	ST ps;
	StackInit(&ps);
	StackPush(&ps, 1);
	StackPush(&ps, 2);
	StackPush(&ps, 3);
	StackPush(&ps, 4);
	StackPush(&ps, 5);
	PrintStack(&ps);
	int input = 0;
	do
	{
		menu();
		int x;
		scanf("%d", &input);
		switch (input)
		{
		case 1:scanf("%d", &x);
			StackPush(&ps, x);
			PrintStack(&ps);
			break;
		case 2:StackPop(&ps);
			PrintStack(&ps);
			break;
		case 3:
			x = StackTop(&ps);
			printf("%d\n", x);
			break;
		case 4:
		if (StackEmpty(&ps) == 0)
		{
			printf("not empty\n");
		}
		 else 
	    {
			printf("empty\n");
		}
		break;
		case 5:
			x = StackSize(&ps);
			printf("%d\n", x);
			break;
		case 0:
			StackDestroy(&ps);
			break;
		default:printf("error type\n");
			break;
		}
	} while (input);
	return 0;
}