栈的实现

1、栈的概念

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

2、栈的数据结构

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。

定长的静态栈的结构

typedef int STDataTyp
#define N 10
typedef struct Stack
{
STDataType _a[N];
int _top; // 栈顶
}Stack;

动态增长的栈

typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;

Stac.h

#ifndef _STACK_H_
#define _STACK_H_

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define CAPACITY 2

typedef int StackDataType;

typedef struct Stack
{
	StackDataType *_array;
	size_t _size;
	size_t _capacity;
}Stack;

//初始化
void StackInit(Stack *pstack, size_t capacity);
//销毁
void StackDestory(Stack *pstack);
//扩容
void CheckCapacity(Stack *pstack);
//压栈
void StackPush(Stack *pstack, StackDataType x);
//弹出
void StackPop(Stack *pstack);
//返回栈顶元素
StackDataType StackTop(Stack *pstack);
//返回栈的大小
int StackSize(Stack *pstack);
//判空
int StackEmpty(Stack *pstack);
//打印
void StackPrint(Stack *pstack);
#endif //_STACK_H_

Stack.c

#include "Stack.h"

//初始化
void StackInit(Stack *pstack, size_t capacity)
{
	assert(pstack);
	pstack->_capacity = capacity;
	pstack->_array = (StackDataType *)malloc(capacity*sizeof(StackDataType));
	assert(pstack->_array);
	pstack->_size = 0;
}

//销毁
void StackDestory(Stack *pstack)
{
	assert(pstack);
	if (pstack->_array)
	{
		free(pstack->_array);
		pstack->_array = NULL;
		pstack->_size = 0;
		pstack->_capacity = 0;
	}
}

//扩容
void CheckCapacity(Stack *pstack)
{
	assert(pstack);
	if (pstack->_size == pstack->_capacity)
	{
		pstack->_capacity *= CAPACITY;
		pstack->_array = (StackDataType *)realloc(pstack->_size, pstack->_capacity*sizeof(StackDataType));
	}
}

//压栈
void StackPush(Stack *pstack, StackDataType x)
{
	assert(pstack);
	CheckCapacity(pstack);
	pstack->_array[pstack->_size] = x;
	pstack->_size++;
}

//弹出
void StackPop(Stack *pstack)
{
	assert(pstack || pstack->_size);
	pstack->_size--;
}

//返回栈顶元素
StackDataType StackTop(Stack *pstack)
{
	assert(pstack);
	if (pstack->_array)
	{
		return pstack->_array[pstack->_size - 1];
	}
	return -1;
}

//返回栈的大小
int StackSize(Stack *pstack)
{
	assert(pstack);
	assert(pstack);
	if (pstack->_array)
	{
		return pstack->_size;
	}
	return -1;
}

//判空
int StackEmpty(Stack *pstack)
{
	assert(pstack);
	if (StackSize(pstack) == -1)
	{
		return 1;
	}
	return -1;
}

//打印
void StackPrint(Stack *pstack)
{
	assert(pstack);
	for (int i = 0; i < pstack->_size; i++)
	{
		printf("%d--", pstack->_array[i]);
	}
	printf("Top\n");
}

main.c

#include "Stack.h"

int main()
{
	Stack stack;
	StackInit(&stack, 10);
	StackPush(&stack, 1);
	StackPush(&stack, 2);
	StackPush(&stack, 3);
	StackPush(&stack, 4);
	StackPush(&stack, 5);
	StackPush(&stack, 6);
	StackPush(&stack, 7);
	StackPush(&stack, 8);
	StackPush(&stack, 9);
	StackPush(&stack, 10);
	StackPrint(&stack);
	StackPop(&stack);
	StackPrint(&stack);
	printf("StackDataType = %d\n", StackTop(&stack));
	printf("StackSize = %d\n", StackSize(&stack));
	printf("StackEmpty = %d\n", StackEmpty(&stack));
	system("pause");
	return 0;
}