栈的表示和实现（C语言）

目录

栈的概念及结构

栈的实现

Stack.h

Stack.c

main.c测试接口

---

栈的概念及结构

   概念

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

   结构

进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

栈中的数据元素遵循后进先出的原则。

压栈：栈的插入操作叫做 进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫出栈。出数据也在栈顶。

---

练习题

 这道题很简单，栈的数据元素规则就是后进先出，这组元素中，E是最后进来的所以它先出去，其次就是元素D。                所以选B

栈可以想象成一个管道，你从管道口往里放一个东西，之后如果你还想放东西是不是还是需要从管道口往里放？那么你第一次放的东西就越靠近里面了，你没取一次东西肯定是先从靠近管道口的位置取。

便于学习时，也可以看成弹夹。

---

 这题答案是C。

A中顺序：1进--1出--234进完--4出--3出--2出

B中顺序：12进--2出--3进--3出--4进--4出--1出

D中顺序：123进--3出--4进--4出--2出--1出

---

栈的实现

推荐使用数组来实现栈

下面我们来看具体需要实现栈的哪些需求。

---

Stack.h

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void StackInit(ST* ps); //初始化
void StackDestory(ST* ps); //销毁
void StackPush(ST* ps, STDataType x); //入栈
void StackPop(ST* ps);  //出栈

STDataType StackTop(ST* ps); //返回栈顶元素

int StackSize(ST* ps); //求栈数据个数
bool StackEmpty(ST* ps); //判断栈是否为空

一些解释：

#pragma once是预编译

头文件中assert是类型断言的头文件，断言函数assert()，只有当括号内判断为真时才执行程序下面的代码

定义的结构体中，top是栈顶指针，capacity是容量（不够的时候要增容）

下面是各接口具体实现

---

Stack.c

#include"Stack.h"

void StackInit(ST* ps) //初始化
{
	assert(ps); //结构体指针不能为空
	ps->a = malloc(sizeof(STDataType)*4); //动态内存开辟空间
	if (ps->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0 ;  //如果top给0意味着指向的是栈顶元素的下一个 ； -1表示指向栈顶元素
}

void StackDestory(ST* ps) //销毁
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x) //入栈
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)  //出栈
{
	assert(ps);
	//栈空了，调用Pop，直接中止程序报错
	assert(ps->top > 0);
	ps->top--;
}

STDataType StackTop(ST* ps) //返回栈顶元素
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool StackEmpty(ST* ps) //判断栈是否为空
{
	assert(ps);
	return ps->top == 0;
}

---

main.c测试接口

#include<stdio.h>
#include"Stack.h"
int main()
{
	ST st; //声明一个结构体变量
	StackInit(&st);//初始化栈
	StackPush(&st, 1);  //入栈数据1,2,3,4，5
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);

	while (!StackEmpty(&st)) //如果栈不为空，就可以取数据
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);   //出栈
	}
	printf("\n");


	StackDestory(&st);//销毁栈
	return 0;
}

测试内容可自行更改。