专栏：数据结构
个人主页：HaiFan.
专栏简介：这里是HaiFan.的数据结构专栏，今天的内容是栈，一个特殊的数据结构。

栈

• 前言
• 栈的概念
• 栈的接口实现
• STKInit初始化
• STKDestory销毁空间
• STKPush压栈
• STKPop出栈
• STKEmpty判断栈是否为空
• STKSize栈中元素个数
• 源代码

前言

栈的概念

栈是一种特殊的数据结构，它不允许随机插入数据和随机删除数据，只允许在固定的一端加入数据和删除数据，加入数据的一端称为栈顶，另一端称为栈低，栈中的数据遵循先进后出原则。

加入数据的操作称为：压栈

删除数据的操作称为：出栈，删除数据也是在栈顶进行操作的。

现在有一组数据，分别为 1， 2， 3， 4.依次把这四个元素入栈。得到的数据就如图中一样。

出栈顺序是，4，3，2，1.

实现栈有两种方式，一种是数组方式实现，还有一种是链表实现，数组实现比较简单，链表实现就是尾插和尾删。

栈的接口实现

typedef int StkDataType;typedef struct Stack
{StkDataType* val;int top;int capacity;
}STK;void STKInit(STK* stk);//初始化
void STKDestory(STK* stk);//销毁空间void STKPush(STK* stk, StkDataType x);//压栈
void STKPop(STK* stk);//出栈bool STKEmpty(STK* stk);//栈是否为空void STKSize(STK* stk);//栈的元素个数

STKInit初始化

栈的初始化很容易，如同顺序表一样，可以先给val开辟一点空间。

void STKInit(STK* stk)
{stk->val = (StkDataType*)malloc(sizeof(StkDataType) * 4);stk->capacity = 4;stk->top = -1;//从当前位置开始//stk->top = 0;//从当前位置的下一个位置开始
}

栈顶top可以是-1也可以是0，当从-1开始的时候，top的位置就是栈顶的位置，当从0开始的时候top的位置就是栈顶的下一个位置。

STKDestory销毁空间

既然用到了动态开辟空间的函数，就需要销毁空间

void STKDestory(STK* stk)
{assert(stk);free(stk->val);stk->val = NULL;
}

STKPush压栈

压栈的操作很简单，首先要检查val数组的空间是否足够继续添加数据，然后添加数据即可。

void STKPush(STK* stk, StkDataType x)
{if (stk->capacity == stk->top + 1){StkDataType* tmp = (StkDataType*)realloc(stk->val, sizeof(StkDataType) * stk->capacity * 2);stk->capacity *= 2;stk->val = tmp;}stk->val[++stk->top] = x;}

STKPop出栈

出栈，也就是把栈顶元素给删除。

void STKPop(STK* stk)
{assert(stk);assert(!STKEmpty(stk));cout << stk->val[stk->top--] << endl;}

STKEmpty判断栈是否为空

判断栈是否为空，只需要判断栈顶是否为初始化的值即可。

bool STKEmpty(STK* stk)
{assert(stk);return stk->top == -1;
}

STKSize栈中元素个数

栈中元素个数可以根据top来判断。

void STKSize(STK* stk)
{assert(stk);cout << stk->top + 1<< endl;}

top初始化为-1，当进行压栈操作之后，栈顶元素的下标就是top，所以元素个数就等于top+1

源代码

.h文件

#pragma once#include 
#include 
#include using namespace std;typedef int StkDataType;typedef struct Stack
{StkDataType* val;int top;int capacity;
}STK;void STKInit(STK* stk);//初始化
void STKDestory(STK* stk);//销毁空间void STKPush(STK* stk, StkDataType x);//压栈
void STKPop(STK* stk);//出栈bool STKEmpty(STK* stk);//栈是否为空void STKSize(STK* stk);//栈的元素个数

.cpp

#define _CRT_SECURE_NO_WARNINGS 1#include "Stack.h"void STKInit(STK* stk)
{stk->val = (StkDataType*)malloc(sizeof(StkDataType) * 4);stk->capacity = 4;stk->top = -1;//从当前位置开始//stk->top = 0;//从当前位置的下一个位置开始
}void STKDestory(STK* stk)
{assert(stk);free(stk->val);stk->val = NULL;
}void STKPush(STK* stk, StkDataType x)
{if (stk->capacity == stk->top + 1){StkDataType* tmp = (StkDataType*)realloc(stk->val, sizeof(StkDataType) * stk->capacity * 2);stk->capacity *= 2;stk->val = tmp;}stk->val[++stk->top] = x;}void STKPop(STK* stk)
{assert(stk);assert(!STKEmpty(stk));cout << stk->val[stk->top--] << endl;}bool STKEmpty(STK* stk)
{assert(stk);return stk->top == -1;
}void STKSize(STK* stk)
{assert(stk);cout << stk->top + 1<< endl;}

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1#include "Stack.h"void StackTest()
{STK stk;STKInit(&stk);STKPush(&stk, 1);STKPush(&stk, 2);STKPush(&stk, 3);STKPush(&stk, 4);STKSize(&stk);while (stk.top != -1){STKPop(&stk);}STKDestory(&stk);
}int main()
{StackTest();return 0;
}