【数据结构】 栈的基本操作

前端之家收集整理的这篇文章主要介绍了【数据结构】 栈的基本操作前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
/*
===============================================================================================
			栈的基本操作
		By~fanxingzju			2014-04-14
1.构造一个空栈Stack
2.销毁栈Stack
3.把Stack置为空栈
4.若栈Stack为空栈,则返回true,否则返回false
5.用length返回栈中元素的个数,即栈的长度
6.若栈不为空,则用elem返回Stack的栈顶元素,并返回true,否则返回false
7.向栈顶压入值为elem为新元素
8.若栈不为空,则删除S的栈顶元素,用elem返回其值,并返回true,否则返回false

===============================================================================================
说明:
1.我在大部分函数添加了 “if (NULL == Stack.base)”的条件判断,但正常使用时,这段代码不是必须的,可以删除
2.在Push操作时,对于栈满的情况,进行了追加内存的操作。为了保证堆栈的顺序,引入了中间堆栈tempStack
*/
#include <stdio.h>
#include <stdlib.h>

#define STACK_MAX_SIZE 10
#define STACK_INCREMENT 3
#define SElemType int

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

//1.构造一个空栈Stack
bool InitStack(SqStack &Stack)
{
	Stack.base = new SElemType[STACK_MAX_SIZE];
	if (!Stack.base)
	{
		printf("InitStack()函数运行,内存分配失败\n");
		system("pause");
		exit(-1);
	}
	Stack.top = Stack.base;
	Stack.stacksize = STACK_MAX_SIZE;
	printf("InitStack()函数执行,空栈构造成功\n");
	return true;
}

//2.销毁栈Stack
bool DestoyStack(SqStack &Stack)
{
	Stack.top = Stack.base;
	delete[] Stack.base;
	Stack.base = NULL;
	Stack.top = NULL;
	printf("DestoryStack()函数执行,栈销毁成功\n");
	return true;
}

//3.把Stack置为空栈
bool ClearStack(SqStack &Stack)
{
	if (NULL == Stack.base)
	{
		printf("ClearStack()函数执行,栈不存在,无法清空\n");
		return false;
	}
	Stack.top = Stack.base;
	printf("ClearStack()函数执行,栈清空成功\n");
	return true;
}

//4.若栈Stack为空栈,则返回true,否则返回false
bool StackEmpty(SqStack Stack)
{
	if (NULL == Stack.base)
	{
		printf("StackEmpty()函数执行,栈不存在!!\n");
		system("pause");
		exit(-1);
	}
	if (Stack.top == Stack.base)
	{
		printf("StackEmpty()函数执行,栈为空栈\n");
		return true;
	} 
	printf("StackEmpty()函数执行,栈不为空\n");
	return false;
}

//5.返回栈中元素的个数,即栈的长度
bool StackLength(SqStack Stack,int &length)
{
	if (NULL == Stack.base)
	{
		printf("StackLength()函数执行,栈不存在,返回长度失败\n");
		return false;
	}
	length = Stack.top - Stack.base;
	printf("Stacklength()函数执行,栈的长度为 %d \n",length);
	return true;
}

//6.若栈不为空,则用elem返回Stack的栈顶元素,并返回true,否则返回false
bool GetTopStack(SqStack Stack,SElemType &elem)
{
	if (NULL == Stack.base)
	{
		printf("GetTop()函数执行,栈不存在,获取栈顶元素失败\n");
		return false;
	}
	if (Stack.base == Stack.top)
	{
		printf("GetTop()函数执行,栈为空,获取栈顶元素失败\n");
		return false;
	}
	elem = *(Stack.top - 1);
	printf("GetTop()函数执行,栈顶元素为: %d \n",elem);
	return true;
}

//7.7.向栈顶压入值为elem为新元素
bool PushStack(SqStack &Stack,SElemType elem)
{
	if (NULL == Stack.base)
	{
		printf("PushStack()函数执行,栈不存在,向栈顶压入元素失败\n");
		system("pause");
		exit(-1);
	}
	if (Stack.top - Stack.base >= Stack.stacksize)
	{
		printf("PushStack()函数执行,原始栈已满,重新给栈分配更大的空间\n");
		SqStack tempStack,newStack;
		tempStack.base = new SElemType[Stack.stacksize];
		newStack.base = new SElemType[Stack.stacksize + STACK_INCREMENT];
		if ((!tempStack.base)||(!newStack.base))
		{
			printf("PushStack()函数运行,内存分配失败\n");
			system("pause");
			exit(-1);
		}
		tempStack.top = tempStack.base;
		tempStack.stacksize = Stack.stacksize;
		newStack.top = newStack.base;
		newStack.stacksize = Stack.stacksize + STACK_INCREMENT;
		while(Stack.top != Stack.base)
		{
			SElemType temp = *--Stack.top;
			*tempStack.top++ = temp;
		}
		while(tempStack.top != tempStack.base)
		{
			SElemType temp = *--tempStack.top;
			*newStack.top++ = temp;
		}
		delete[] Stack.base;
		delete[] tempStack.base;
		Stack = newStack;
	}

	*Stack.top++ = elem;
	printf("PushStack()函数执行,元素 %d 压入栈顶成功\n",elem);
	return true;
}

//8.若栈不为空,则删除S的栈顶元素,用elem返回其值,并返回true,否则返回false
bool PopStack(SqStack &Stack,SElemType &elem)
{
	if (NULL == Stack.base)
	{
		printf("PopStack()函数执行,栈不存在,弹出栈顶元素失败\n");
		system("pause");
		exit(-1);
	}
	if (Stack.base == Stack.top)
	{
		printf("PopStack()函数执行,栈为空,弹出栈顶元素失败\n");
		return false;
	}
	elem = *--Stack.top;
	printf("PopStack()函数执行,弹出栈顶元素成功,栈顶的元素为: %d \n",elem);
	return true;
}

int main()
{
	SqStack Stack;
	InitStack(Stack);

	for (int i = 0; i != 30; ++i)
	{
		PushStack(Stack,i);
	}
	StackEmpty(Stack);

	int length = 0;
	StackLength(Stack,length);

	SElemType elem;
	GetTopStack(Stack,elem);

	while(PopStack(Stack,elem))
	{
		//printf("PopStack()函数执行,弹出栈顶元素成功,栈顶的元素为: %d \n",elem);
	}

	ClearStack(Stack);
	DestoyStack(Stack);

	system("pause");
	return 0;
}
原文链接:https://www.f2er.com/datastructure/383054.html

猜你在找的数据结构相关文章