前端之家收集整理的这篇文章主要介绍了
【数据结构】 栈的基本操作,
前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
- /*
- ===============================================================================================
- 栈的基本操作
- 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;
- }