Stack 栈模型的顺序存储实现

栈（Stack）也是数据存储的一种方式，我们可以将其理解为一种线性的表，只不过他是前去后继的关系，他只能在线性表的尾部插入和取出数据，这个尾部所指的就是栈的栈顶，而最先被存入的数据则是栈底。它具有后进先出、先进后出的特性。表示图如下：

【代码实现】

下面代码中，使用顺序线性表实现了一个栈模型，与上图非常类似。具体代码如下（需要用到线性表顺序存储的相关头文件）：

#ifndef _SEQSTACK_H_
#define _SEQSTACK_H_

typedef void SeqStack;

//创建栈
SeqStack* SeqStack_Create(int capacity);

//销毁栈
void SeqStack_Destroy(SeqStack* stack);

//清空栈
void SeqStack_Clear(SeqStack* stack);

//进栈
int SeqStack_Push(SeqStack* stack, void* item);

//出栈
void* SeqStack_Pop(SeqStack* stack);

//获取栈顶元素
void* SeqStack_Top(SeqStack* stack);

//获取栈的大小
int SeqStack_Size(SeqStack* stack);

#endif //_SEQSTACK_H_

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "SeqStack.h"
#include "SeqList.h"

//创建栈
SeqStack* SeqStack_Create(int capacity)
{
	//相当于创建一个线性表
	SeqList* list = SeqList_Create(capacity);
	return list;
}

//销毁栈
void SeqStack_Destroy(SeqStack* stack)
{
	//相当于销毁一个线性表
	SeqList_Destroy(stack);
}


//清空栈
void SeqStack_Clear(SeqStack* stack)
{
	//相当于清空一个线性表
	SeqList_Clear(stack);
}


//进栈
int SeqStack_Push(SeqStack* stack, void* item)
{
	//在线性表尾部插入元素
	int ret = SeqList_Insert(stack, (SeqListNode*)item, SeqStack_Size(stack));
	return ret;
}


//出栈
void* SeqStack_Pop(SeqStack* stack)
{
	//在线性表尾部删除元素
	SeqListNode* pDel = SeqList_Delete(stack, SeqStack_Size(stack) - 1);
	return (void*)pDel;
}


//获取栈顶元素
void* SeqStack_Top(SeqStack* stack)
{
	//获取线性表尾部元素
	SeqListNode* pNode = SeqList_Get(stack, SeqStack_Size(stack) - 1);
	return pNode;
}


//获取栈的大小
int SeqStack_Size(SeqStack* stack)
{
	//相当于获取线性表的长度
	int len = SeqList_Length(stack);
	return len;
}

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "SeqStack.h"

int main()
{
	int i;
	int array[10] = { 0 };
	SeqStack* stack = NULL;
	//创建栈
	stack = SeqStack_Create(25);
	if (stack == NULL)
	{
		return -1;
	}
	//初始化数组
	for (i = 0; i < sizeof(array) / sizeof(int); i++)
	{
		array[i] = i;
		//压栈
		SeqStack_Push(stack, (void*)&array[i]);
	}

	//打印栈的大小
	printf("stack size = %d\n", SeqStack_Size(stack));
	//打印栈顶元素
	printf("stack top element = %d\n", *(int *)SeqStack_Top(stack));

	//所有元素出栈
	while (SeqStack_Size(stack) > 0)
	{
		//打印栈顶元素, 并出栈
		printf("-----stack top element = %d\n", *(int *)SeqStack_Pop(stack));
	}
	//销毁栈
	SeqStack_Destroy(stack);

	printf("Good good study, day day up!!!\n");
	system("pause");
	return 0;
}