数据结构 之 栈（Stack）的实现及简单操作

栈是限定仅在表尾进行插入和删除操作的线性表，由于栈只能在尾进行插入和删除，所以这里我们选用顺序表来实现栈更方便快捷一点

对于栈我们要做的有栈的初始化，入栈，出栈，查看栈顶元素，查看栈内元素个数，清空栈，打印栈

在Stack.h:中对栈相关接口函数进行声明以及对栈的结构体进行定义

Stack.h:

#pragma once
#define NUM 50//栈的大小
typedef int DataType;

typedef struct Stack
{
	DataType* _array;
	size_t	_top; //栈顶 
	size_t	_end;
}Stack;

// 栈的实现接口 
void StackInit(Stack* s);//栈的初始化
void StackPush(Stack* s, DataType x);//入栈
void StackPop(Stack* s);//出栈
DataType StackTop(Stack* s);//查看栈顶元素
size_t StackSize(Stack* s);//栈内元素个数
int StackEmpty(Stack* s);//清空栈
void StackPrintf(Stack* s);//打印栈内元素(由栈底到栈顶)
           

这里用宏定义栈的大小

接着在Stack.c中对相关接口函数一一实现

Stack.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"Stack.h"

void StackInit(Stack* s)//初始化栈
{
	s->_array = (DataType*)malloc(sizeof(DataType)*NUM);//malloc申请内存空间
	if (s->_array != NULL)
	{
		s->_end = s->_top = 0;
		return;
	}
	printf("栈初始化失败！！");
	return;
}

void StackPush(Stack* s, DataType x)//入栈
{
	assert(s);
	if (s->_top == NUM)
	{
		printf("stack overflow");//栈溢出
		return;
	}
	s->_array[s->_top] = x;
	s->_top++;
}

void StackPop(Stack* s)//出栈
{
	assert(s);
	s->_top--;
}

DataType StackTop(Stack* s) //栈顶元素
{
	assert(s);
	if (s->_top == 0)
	{
		printf("栈为空！！");
		return -1;
	}
	else
		return s->_array[s->_top- 1];
}

size_t StackSize(Stack* s)//栈内元素个数
{
	assert(s);
	return s->_top;
}

int StackEmpty(Stack* s)//清空栈
{
	s->_top = 0;
	return 0;
}

void StackPrintf(Stack* s)//打印栈内元素
{
	assert(s);
	rsize_t i = 0;
	for (i = 0; i < s->_top; i++)
	{
		printf("%-3d", s->_array[i]);
	}
	printf("\n");
}

int main()
{
	Stack s;
	StackInit(&s);
	StackPush(&s, 1);
	StackPush(&s, 2);
	StackPush(&s, 3);
	StackPush(&s, 4);
	StackPush(&s, 5);
	StackPop(&s);
	StackPush(&s, 6);
	printf("栈内元素为：");
	StackPrintf(&s);
	printf("栈内元素个数为：%d\n", StackSize(&s));
	printf("栈顶元素为：%d\n", StackTop(&s));
	system("pause");
	return 0;
}
           

这里我们用宏定义栈的大小，需要注意的是因为栈的大小是一定的，所以在入栈时候要判断栈是否是满的，这里如果不加以判断就有可能造成访问越界，在这里当栈满时 屏幕打印 stack overflow

关于stack overflow这个问题我们在平时写递归时候如果不慎写出死循环之类的问题经常程序因为栈溢出而挂掉

int main()
{
	Stack s;
	StackInit(&s);
	StackPush(&s, 1);
	StackPush(&s, 2);
	StackPush(&s, 3);
	StackPush(&s, 4);
	StackPush(&s, 5);
	StackPop(&s);
	StackPush(&s, 6);
	printf("栈内元素为：");
	StackPrintf(&s);
	printf("栈内元素个数为：%d\n", StackSize(&s));
	printf("栈顶元素为：%d\n", StackTop(&s));
	system("pause");
	return 0;
}
           

简单的对相关接口进行测试