目录
1.栈的基本概念
2.入栈和出栈图示
3.栈的顺序存储及链式存储示意图
4.栈的顺序存储代码示例
5.栈的链式存储代码示例
1.栈的基本概念
概念：
首先栈是一个线性表，栈元素具有线性关系，即前驱后继关系。只不过它是一种受限制的线性表，定义中说明栈这种线性表在线
性表的表尾进行插入或者删除操作，这里的表尾是指栈顶，而不是栈底.
特点：
先进后出(First In Last Out,FILO结构)
特性：
栈的插入和删除位置始终只能在栈进行，栈底是固定的，最先进的只能在栈底.
操作：
栈的插入操作，叫做进栈，也称压栈，类似子弹入弹夹.
栈的删除操作：叫做出栈，也称弹栈退栈，如同从弹夹中的子弹弹出.
2.入栈和出栈图示
3.栈的顺序存储及链式存储示意图
4.栈的顺序存储代码示例
/*
文件名：SeqStack.h
作者：Muten
编码时间：20201023
编码目的：栈的顺序存储相关声明
代码功能：栈的顺序存储相关声明
测试环境：Mircosoft Visual Studio Professional 2015 版本14.0.25431.01 Update3
版本信息：VER1.0
*/
#pragma once
#ifndef SEQSTACK_H
#define SEQSTACK_H
#define MAX_SIZE 1024
#define SEQEMPTY_TRUE 1
#define SEQEMPTY_FALSE 0
typedef struct SEQSTACK {
void* data[MAX_SIZE];
int size;
}SeqStack;
// 初始化栈
SeqStack* Init_SeqStack();
// 入栈(压栈)
void Push_SeqStack(SeqStack* stack,void* data);
// 返回栈顶元素
void* Top_SeqStack(SeqStack* stack);
// 出栈
void Pop_SeqStack(SeqStack* stack);
// 判断是否为空
int IsEmpty(SeqStack* stack,void* data);
// 返回栈中元素的个数
int Size_SeqStack(SeqStack* stack);
// 清空栈
void Clear_Stack(SeqStack* stack);
// 销毁
void FreeSpace_SeqStack(SeqStack* stack);
#endif
/*
文件名：SeqStack.c
作者：Muten
编码时间：20201023
编码目的：栈的顺序存储相关实现
代码功能：栈的顺序存储相关实现
测试环境：Mircosoft Visual Studio Professional 2015 版本14.0.25431.01 Update3
版本信息：VER1.0
*/
#include "SeqStack.h"
#include <stdio.h>
#include <stdlib.h>
SeqStack * Init_SeqStack()
{
SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack));
for (int i = 0; i < MAX_SIZE; i++)
{
stack->data[i] = NULL;
}
stack->size = 0;
return stack;
}
void Push_SeqStack(SeqStack * stack, void * data)
{
if (stack == NULL || data == NULL)
return;
if (stack->size == MAX_SIZE)
return;
stack->data[stack->size] = data;
stack->size++;
}
void * Top_SeqStack(SeqStack * stack)
{
if ((stack == NULL)||(stack->size == 0))
return;
return stack->data[stack->size -1];
}
void Pop_SeqStack(SeqStack * stack)
{
if ((stack == NULL) || (stack->size == 0))
return;
stack->data[stack->size - 1] = NULL;
stack->size--;
}
int IsEmpty(SeqStack * stack, void * data)
{
if(stack == NULL)
return -1;
if (stack->size == 0)
return SEQEMPTY_TRUE;
return SEQEMPTY_FALSE;
}
int Size_SeqStack(SeqStack * stack)
{
return stack->size;
}
void Clear_Stack(SeqStack * stack)
{
if (stack == NULL)
return;
for (int i = 0; i < stack->size; i++)
stack->data[i] = NULL;
stack->size = 0;
}
void FreeSpace_SeqStack(SeqStack * stack)
{
if (stack == NULL)
return;
free(stack);
}
/*
文件名：main.c
作者：Muten
编码时间：20201023
编码目的：演示栈的顺序存储相关代码
代码功能：测试栈的顺序存储相关
测试环境：Mircosoft Visual Studio Professional 2015 版本14.0.25431.01 Update3
版本信息：VER1.0
*/
#include "SeqStack.h"
#include <stdio.h>
#include <stdlib.h>
typedef struct PERSON {
char name[64];
int age;
}Person;
int main()
{
SeqStack* stack = Init_SeqStack();
Person p1 = {"aaa",10};
Person p2 = { "bbb",20 };
Person p3 = { "ccc",30 };
Person p4 = { "ddd",40 };
Person p5 = { "eee",50 };
Push_SeqStack(stack,&p1);
Push_SeqStack(stack, &p2);
Push_SeqStack(stack, &p3);
Push_SeqStack(stack, &p4);
Push_SeqStack(stack, &p5);
printf("栈的元素个数:%d \n", stack->size);
while (Size_SeqStack(stack) > 0)
{
Person* person = (Person*)Top_SeqStack(stack);
printf("Name:%s, Age：%d\n", person->name,person->age);
Pop_SeqStack(stack);
}
FreeSpace_SeqStack(stack);
system("pause");
}
5.栈的链式存储代码示例
/*
文件名：LinkStack.c
作者：Muten
编码时间：20201023
编码目的：栈的链式存储的函数声明
代码功能：栈的链式存储的函数声明
测试环境：Mircosoft Visual Studio Professional 2015 版本14.0.25431.01 Update3
版本信息：VER1.0
*/
#pragma once
#ifndef LINKSTACK_H
#define LINKSTACK_H
// 链式栈的节点
typedef struct LINKNODE {
struct LINKNODE* next;
}LinkNode;
// 链式栈
typedef struct LINKSTACK
{
LinkNode head;
int size;
}LinkStack;
// 初始化
LinkStack* Init_LinkStack();
// 入栈
void Push_LinkStack(LinkStack* stack,LinkNode* data);
// 出栈
void Pop_LinkStack(LinkStack* stack);
// 返回栈顶元素
LinkNode* Top_LinkStack(LinkStack* stack);
// 返回栈元素的个数
int Size_LinkStatck(LinkStack* stack);
// 清空栈
void Clear_LinkStack(LinkStack* stack);
// 销毁栈
void FreeSpace_LinkStack(LinkStack* stack);
#endif
/*
文件名：LinkStack.c
作者：Muten
编码时间：20201023
编码目的：演示栈的链式存储的函数实现
代码功能：栈的链式存储的函数实现
测试环境：Mircosoft Visual Studio Professional 2015 版本14.0.25431.01 Update3
版本信息：VER1.0
*/
#include "LinkStack.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
LinkStack * Init_LinkStack()
{
LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));
stack->head.next = NULL;
stack->size = 0;
return stack;
}
void Push_LinkStack(LinkStack * stack, LinkNode * data)
{
if (stack == NULL || data == NULL)
return;
data->next = stack->head.next;
stack->head.next = data;
stack->size++;
}
void Pop_LinkStack(LinkStack * stack)
{
if ((stack == NULL) || (stack->size == 0))
return;
// 第一个有效节点
LinkNode* pNext = stack->head.next;
stack->head.next = pNext->next;
stack->size--;
}
// 返回栈顶元素，即是头节点后面的那个元素
LinkNode * Top_LinkStack(LinkStack * stack)
{
if ((stack == NULL)|| (stack->size == 0))
return NULL;
return stack->head.next;
}
int Size_LinkStatck(LinkStack * stack)
{
if ((stack == NULL) || (stack->size == 0))
return -1;
return stack->size;
}
void Clear_LinkStack(LinkStack * stack)
{
if (stack == NULL)
return;
stack->head.next = NULL;
stack->size = 0;
}
void FreeSpace_LinkStack(LinkStack * stack)
{
if (stack == NULL)
return;
free(stack);
}
/*
文件名：main.c
作者：Muten
编码时间：20201023
编码目的：演示栈的链式存储相关代码
代码功能：测试栈的链式存储相关
测试环境：Mircosoft Visual Studio Professional 2015 版本14.0.25431.01 Update3
版本信息：VER1.0
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkStack.h"
typedef struct PERSON {
LinkNode node;
char name[64];
int age;
}Person;
int main()
{
// 创建栈
LinkStack* stack = Init_LinkStack();
// 创建数据
Person p1, p2, p3, p4, p5;
strcpy_s(p1.name,6, "aaaa");
strcpy_s(p2.name,6, "bbbb");
strcpy_s(p3.name,6, "cccc");
strcpy_s(p4.name,6, "dddd");
strcpy_s(p5.name,6, "eeee");
p1.age = 10;
p2.age = 20;
p3.age = 30;
p4.age = 40;
p5.age = 50;
// 入栈
Push_LinkStack(stack,(LinkNode*)&p1);
Push_LinkStack(stack,(LinkNode*)&p2);
Push_LinkStack(stack,(LinkNode*)&p3);
Push_LinkStack(stack,(LinkNode*)&p4);
Push_LinkStack(stack,(LinkNode*)&p5);
// 输出
while (Size_LinkStatck(stack) > 0)
{
// 取出栈顶元素
Person* p = (Person*)Top_LinkStack(stack);
printf("name:%s,Age：%d.\n",p->name,p->age);
// 弹出栈顶元素
Pop_LinkStack(stack);
}
// 销毁栈
FreeSpace_LinkStack(stack);
system("pause");
}
