栈的顺序存储与栈的链式存储

栈的顺序存储与栈的链式存储

模拟入栈和出栈

#ifndef SEQSTACK_H
#define SEQSTACK_H

#include
#include

//数组去模拟栈的顺序存储
#define MAX_SIZE 1024
#define SEQSTACK_TRUE 1
#define SEQSTACK_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);
//返回栈中元素的个数
int Size_SeqStack(SeqStack* stack);
//清空栈
void Clear_SeqStack(SeqStack* stack);
//销毁
void FreeSpace_SeqStack(SeqStack* stack);



#endif

#include "SeqStack.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)
	{
		return;
	}
	if (stack->size == MAX_SIZE)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	stack->data[stack->size] = data;
	stack->size++;

}
//返回栈顶元素
void* Top_SeqStack(SeqStack* stack)
{
	if (stack == NULL) {
		return NULL;
	}

	if (stack->size == 0) {
		return NULL;
	}

	return stack->data[stack->size-1];
}
//出栈
void Pop_SeqStack(SeqStack* stack)
{
	if (stack == NULL) {
		return;
	}
	if (stack->size == 0) {
		return;
	}
	stack->data[stack->size - 1] = NULL;
	stack->size--;
}
//判断是否为空
int IsEmpty(SeqStack* stack)
{
	if (stack == NULL) {
		return -1;
	}

	if (stack->size == 0) {
		return SEQSTACK_TRUE;
	}

	return SEQSTACK_FALSE;
}
//返回栈中元素的个数
int Size_SeqStack(SeqStack* stack)
{
	return stack->size;
}
//清空栈
void Clear_SeqStack(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);
}


//栈的顺序存储测试
typedef struct PERSON
{
	char name[64];
	int age;
}Person;

int main()
{
	//创建栈
	SeqStack* stack1 = Init_SeqStack();

	//创建数据
	Person p1 = { "aaa",10 };
	Person p2 = { "bbb",20 };
	Person p3 = { "ccc",30 };
	Person p4 = { "ddd",40 };

	//入栈
	Push_SeqStack(stack1, &p1);
	Push_SeqStack(stack1, &p2);
	Push_SeqStack(stack1, &p3);
	Push_SeqStack(stack1, &p4);

	//输出，当栈中元素个数大于0时候输出
	while (Size_SeqStack > 0)
	{
		//访问栈顶元素
		Person* person = (Person*)Top_SeqStack(stack1);
		printf("Name: %s Age: %dn", person->name, person->age);
		//d出栈顶元素
		Pop_SeqStack(stack1);
	}
	//释放内存
	FreeSpace_SeqStack(stack1);

	printf("n");
	system("pause");
	return 0;
}

栈的链式存储

这里的stack->head.next 等价于pNext

 

#ifndef linkSTACK_H
#define linkSTACK_H

#include 
#include 

//链式栈的结点
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_linkStack(linkStack* stack);
//清空栈
void Clear_linkStack(linkStack* stack);
//销毁栈
void FreeSpace_linkStack(linkStack* stack);


#endif

#include"linkStack.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)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	data->next = stack->head.next;
	stack->head.next = data;
	stack->size++;
}
//出栈
void Pop_linkStack(linkStack* stack)
{
	if (stack == NULL) {
		return;
	}
	if (stack->size == 0) {
		return;
	}
	//第一个有效结点
	linkNode* pNext = stack->head.next;
	stack->head.next = pNext->next;

	stack->size--;
}
//返回栈顶元素
linkNode* Top_linkStack(linkStack* stack)
{
	if (stack == NULL) {
		return NULL;
	}
	if (stack->size == 0) {
		return NULL;
	}
	return stack->head.next;
}
//返回栈元素的个数
int Size_linkStack(linkStack* stack)
{
	if (stack == NULL) {
		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);
}



//测试
typedef struct PERSON {
	linkNode node;
	char name[64];
	int age;
}Person;

int main(void) {

	//创建栈
	linkStack* stack = Init_linkStack();

	//创建数据
	Person p1, p2, p3, p4, p5;
	strcpy(p1.name, "aaa");
	strcpy(p2.name, "bbb");
	strcpy(p3.name, "ccc");
	strcpy(p4.name, "ddd");
	strcpy(p5.name, "eee");

	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_linkStack(stack) > 0) {

		//取出栈顶元素
		Person* p = (Person*)Top_linkStack(stack);
		printf("Name:%s Age:%dn", p->name, p->age);
		//d出栈顶元素
		Pop_linkStack(stack);
	}

	//销毁栈
	FreeSpace_linkStack(stack);

	system("pause");
	return 0;
}