- 1. 栈的简介
- 1.1栈的特点
- 1.2栈的相关概念
- 2.栈的顺序存储
- 2.1初始化栈
- 2.1入栈
- 2.3出栈
- 2.4 获取栈顶元素
- 2.5获取栈的大小
- 2.6 判断栈是否为空
- 2.7栈的销毁
- 2.8 测试部分
- 3.栈的链式存储
- 3.1链式存储的简单介绍
- 3.2链式存储中入栈和出栈的简单示意图
- 3.3代码实现过程
栈(Stack)是一种线性存储结构，它最大的特点就是：栈中的数据遵循先进后出的原则，想要在栈中插入和删除数据，只能在栈顶操作。
1.2栈的相关概念栈的相关概念：
1.栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。
2.入栈：栈的插入操作，叫做进栈，也称压栈。
3.出栈：栈的删除操作，也叫做弹栈。
下面我将介绍栈的两种实现结构，一种是栈的顺序存储，一种是栈的链式存储。
一般对于栈的操作主要有以下几个部分：
1.初始化栈，也就是创建出一个栈的结构
2.入栈操作
3.出栈操作
4.获取栈顶元素
5.获取栈的大小
6.判断栈是否为空
7.销毁栈
首先我们要创建一个栈的结构，结构体中包含数据块，以及定义一个变量来来记录栈的大小。
#define MAX 1024
typedef struct SStack
{
void* date[MAX];//将数据类型定义成为void* 这样就可以接收任意类型的数据了
int size;
};
2.1初始化栈
SStack* initStack()
{
SStack* stack = (SStack*)malloc(sizeof(SStack));
if(stack==NULL)
{
return NULL;
}
memset(date,0,sizeof(void*)*MAx);//将数据全部置为0
stack->size = 0;
return stack;
}
2.1入栈
void pushStack(SStack* stack,void* date)
{
if(stack==NULL||date==NULL)
{
return;
}
if(stack->size==MAX)//判断栈是否放满
{
return;
}
stack->date[stack->size] = date; //将数据放到栈顶
stack->szie++;
}
2.3出栈
void popStack(SStack* stack)
{
if(stack==NULL)
{
return;
}
if(stack->size==0)
{
return;
}
//将最后一个元素置空，执行出栈
stack->date[stack->size-1]=NULL;
stack->size--;
}
2.4 获取栈顶元素
void* getTopStack(SStack* stack)
{
if(stack==NULL)
{
return NULL;
}
if(stack->size==0)
{
return NULL;
}
//返回栈顶元素
return stack->date[stack->size-1];
}
2.5获取栈的大小
int sizeOfStack(SStack* stack)
{
if(stack==NULL)
{
return -1;
}
return stack->szie;
}
2.6 判断栈是否为空
bool isEmptyStack(SStack* stack)
{
if(stack==NULL)
{
return true;
}
if(stack->size==0)
{
return true;
}
return false;//不为空返回false
}
2.7栈的销毁
void destoryStack(SStack* stack)
{
if(stack==NULL)
{
return ;
}
free(stack);
stack = NULL;
}
2.8 测试部分
#include "stack.h"
//定义一个Person的结果体类型
struct Person
{
char name[20];
int age;
};
void test()
{
//初始化栈
SStack* stack = initStack();
struct Person p1 = { "陈",10 };
struct Person p2 = { "卢",12 };
struct Person p3 = { "张",14 };
struct Person p4 = { "王",15 };
struct Person p5 = { "周",11 };
struct Person p6 = { "李",16 };
//将数据进行入栈操作
pushStack(stack, &p1);
pushStack(stack, &p2);
pushStack(stack, &p3);
pushStack(stack, &p4);
pushStack(stack, &p5);
pushStack(stack, &p6);
int size = sizeOfStack(stack);
//打印出出栈前栈中元素的个数
printf("栈的大小为：%dn", size);
while (!isEmptyStack(stack)) //如果栈不为空 进行访问栈顶元素 并且出栈
{
struct Person* pTop = getTopStack(stack); //得到栈顶元素
//打印栈顶元素的信息
printf("栈顶元素的姓名：%s 年龄：%dn", pTop->name, pTop->age);
//进行出栈操作
popStack(stack);
}
size = sizeOfStack(stack);
printf("栈的大小为：%dn", size);//打印出出栈后栈中元素的个数
destoryStack(stack);
}
int main()
{
test();
return 0;
}
下面是程序运行的结果：可以清楚看到入栈的顺序与出栈的顺序，完全相反。
关于链式存储，显而易见，这就跟链表有关，而我们都知道对于链表而言，我们为了方便链表的操作，都会定义一个头结点出来，所以对于栈来说，我们也要定义一个头结点。那么问题来了，我们知道栈的结构分为栈顶和栈底，那么我们这个头结点是指向栈顶呢，还是指向栈底呢？
我们前面讲了，栈这种数据结构有一个特点：就是入栈和出栈都是对栈顶来进行操作的，如果我们把头结点指向栈底，那么对于栈顶的元素的插入，和删除操作就不太方便，所以综上所述，我们应该把头结点指向栈顶。
下面为链式存储中栈的数据的结构
当有新数据进来时，我们就进行头，怎么头插呢，具体的我们来看图：
我们让newnode->next指向栈中第一个数据（也就是top）,然后用
phead->next,执象我们的新节点，这就完成了。
栈的链式存储的主要功能和顺序存储的主要能类似，只是多了一个结构体指针。下面我就不分开写了
typedef struct StackNode
{
struct StackNode* next; //只维护指针域
}StackNode;
//定义栈的结构体
typedef struct linkStack
{
StackNode phead; //头节点
int size;//记录栈的大小
}linkStack;
//初始化
linkStack* initlinkStack()
{
linkStack* stack = malloc(sizeof(linkStack));
if (stack == NULL)
{
return NULL;
}
stack->phead.next = NULL;
stack->size = 0;
return stack;
}
//入栈
void pushlinkStack(linkStack* stack, void* date)
{
if (stack == NULL || date == NULL)
{
return;
}
//拿到用户数据的前四个字节,进行头插，
StackNode* myNode = date;
//入栈
myNode->next = stack->phead.next;
stack->phead.next = myNode;
stack->size++;
}
//出栈
void poplinkStack(linkStack* stack)
{
if (stack == NULL)
{
return;
}
if (stack->size <= 0)
{
return;
}
StackNode* first = stack->phead.next; //得到第一个有数据的节点
//进行出栈操作
stack->phead.next = first->next;
//更新链表长度
stack->size--;
}
//获取栈顶元素
void* getToplinkStack(linkStack* stack)
{
if (stack == NULL)
{
return NULL;
}
if (stack->size == 0)
{
return NULL;
}
return stack->phead.next;
}
//获取栈的大小
int sizeOflinkStack(linkStack* stack)
{
if (stack == NULL)
{
return -1;
}
return stack->size;
}
//判断栈是否为空
bool isEmptylinkStack(linkStack* stack)
{
if (stack == NULL)
{
return true;
}
if (stack->size == 0)
{
return true;
}
return false; //不为空返回false
}
//销毁栈
void destorylinkStack(linkStack* stack)
{
if (stack == NULL)
{
return;
}
free(stack);
stack = NULL;
}
下面是测试部分代码，跟顺序储存大同小异。
struct Person
{
StackNode node; //预留四个字节，也可以写成int* void*，只要是四个字节的空间就行
char name[20];
int age;
};
void test()
{
struct Person p1 = { "NULL", "陈", 10 };
struct Person p2 = { "NULL", "卢", 12 };
struct Person p3 = { "NULL", "张", 14 };
struct Person p4 = { "NULL", "王", 15 };
struct Person p5 = { "NULL", "周", 11 };
struct Person p6 = { "NULL", "李", 16 };
linkStack* stack = initlinkStack();
pushlinkStack(stack, &p1);
pushlinkStack(stack, &p2);
pushlinkStack(stack, &p3);
pushlinkStack(stack, &p4);
pushlinkStack(stack, &p5);
pushlinkStack(stack, &p6);
int size = sizeOflinkStack(stack);
printf("栈空间的大小：%dn", size);
while (!isEmptylinkStack(stack))
{
struct Person* pTop = getToplinkStack(stack);
printf("姓名：%s, 年龄：%dn", pTop->name, pTop->age);
poplinkStack(stack);
}
size = sizeOflinkStack(stack);
printf("栈空间的大小：%dn", size);
destorylinkStack(stack);
}
int main()
{
test();
return 0;
}
下面是代码运行结果：
