数据结构之栈的实现

数据结构之栈的实现

前言：
对于栈我们只需要明白以下几点即可：
1、栈是一个线性表
2、栈只能在表尾（成为栈顶）进行删除和插入（表头称为栈底）
3、栈的特征是后进先出
4、栈的实现也有顺序存储结构和链式存储结构之分
5、顺序栈的实现要注意，栈顶指针始终在栈顶元素的下一个位置

一、栈的顺序存储结构的基本操作实现代码如下：

// 栈.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "malloc.h"
#include "stdio.h"
#include "stdlib.h"

#define stack_init_size 100
#define stackincrement 10

typedef int SElemType;

typedef struct StackName
{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;

/*栈的初始化*/
bool initStack(SqStack *S)
{
	//构造一个空栈
	S->base=(SElemType*)malloc(stack_init_size*sizeof(SElemType));
	if (!S->base)
	{
		return false;
	}
	S->top=S->base;

	S->stacksize=stack_init_size;
	printf("栈初始化完成!\n");
	return true;
}

/*入栈*/
bool Push(SqStack *S,SElemType e)
{
	printf("%d 入栈完成!\n",e);
	if (S->top-S->base>=S->stacksize)//栈满
	{
		S->base=(SElemType*)realloc(S->base,(S->stacksize+stackincrement)*sizeof(SElemType));
		if (!S->base)
		{
			return false;
		}
	}
	*S->top++=e;
	return true;
}
/*出栈*/
bool Pop(SqStack *S,SElemType *e)
{
	if (S->top==S->base)//栈空
	{
		return false;
	}
	e=--S->top;
	printf("%d 元素出栈\n",*e);
	return true;
}

/*获得栈顶元素*/
void getTop(SqStack S,SElemType *e)
{
	if (S.base!=S.top)
	{
		*e=*(S.top-1);
	}
}

/*打印顺序栈*/
void printfStack(SqStack S)
{
	printf("打印顺序栈如下:\n");
	while (S.base!=S.top)
	{
		printf("%d ",*--S.top);
	}
	printf("\n");
};

int _tmain(int argc, _TCHAR* argv[])
{
	SqStack *S=(SqStack *)malloc(sizeof(SqStack));
	initStack(S);
	Push(S,6);
	Push(S,8);
	Push(S,10);
	printfStack(*S);
	SElemType *e=(SElemType*)malloc(sizeof(SElemType));
	Pop(S,e);
	printfStack(*S);
	getTop(*S,e);
	printf("栈顶元素为%d\n",*e);
	system("pause");
	return 0;
}

通过以上基本操作代码的运行结果，也能够清楚的看出，栈的后进先出的特点。