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;
}