以C++类的方式实现整型元素堆栈（stack）数据结构资源-CSDN下载

共3个文件

cpp：2个

h：1个

以C++类的方式

堆栈（stack）数据结构

5星 · 超过95%的资源需积分: 48 87 浏览量 2011-06-04 16:44:42 上传评论 1 收藏 4KB RAR 举报

在C++编程中，堆栈（Stack）是一种非常重要的数据结构，它遵循“后进先出”（Last In First Out, LIFO）的原则。这里我们将详细介绍如何以C++类的形式来实现一个支持整型元素的堆栈。我们将涵盖类的设计、成员函数的实现以及堆栈操作的具体逻辑。我们需要定义一个名为`IntStack`的类，它包含一个私有成员变量`top`用于存储栈顶指针，以及一个动态分配的数组`arr`来存储栈中的整型元素。类的声明可能如下： ```cpp class IntStack { private: int* arr; int top; int capacity; public: // 构造函数 IntStack(int initialCapacity); // 析构函数 ~IntStack(); // 其他成员函数 void push(int value); void pop(); int peek() const; bool isEmpty() const; int size() const; void clear(); void printStack() const; }; ``` 接下来，我们实现这些成员函数： 1. **构造函数**：初始化堆栈，分配内存并设置栈顶指针为-1（表示栈为空）。 ```cpp IntStack::IntStack(int initialCapacity) { arr = new int[initialCapacity]; top = -1; capacity = initialCapacity; } ``` 2. **析构函数**：释放内存。 ```cpp IntStack::~IntStack() { delete[] arr; } ``` 3. **push**：将元素压入栈顶。 ```cpp void IntStack::push(int value) { if (top == capacity - 1) { // 检查是否需要扩容 resize(2 * capacity); } arr[++top] = value; } ``` 4. **pop**：从栈顶弹出元素，返回被删除的元素。 ```cpp int IntStack::pop() { if (isEmpty()) { throw std::runtime_error("Stack is empty"); } int poppedValue = arr[top--]; return poppedValue; } ``` 5. **peek**：返回栈顶元素但不删除。 ```cpp int IntStack::peek() const { if (isEmpty()) { throw std::runtime_error("Stack is empty"); } return arr[top]; } ``` 6. **isEmpty**：检查栈是否为空。 ```cpp bool IntStack::isEmpty() const { return top == -1; } ``` 7. **size**：返回栈中元素的数量。 ```cpp int IntStack::size() const { return top + 1; } ``` 8. **clear**：清空栈。 ```cpp void IntStack::clear() { top = -1; } ``` 9. **printStack**：遍历并打印栈中的所有元素。 ```cpp void IntStack::printStack() const { if (isEmpty()) { std::cout << "Stack is empty" << std::endl; } else { for (int i = 0; i <= top; ++i) { std::cout << arr[i] << " "; } std::cout << std::endl; } } ``` 在实际应用中，`resize`函数用于在堆栈满时进行动态扩容。这里我们可以定义一个简单的双倍扩容策略： ```cpp void IntStack::resize(int newSize) { int* newArr = new int[newSize]; for (int i = 0; i <= top; ++i) { newArr[i] = arr[i]; } delete[] arr; arr = newArr; capacity = newSize; } ``` 通过以上实现，我们创建了一个完整的C++整型元素堆栈类。这个类不仅包含了基本的堆栈操作，还具备了动态扩容的能力。在实际编程中，这样的自定义数据结构可以灵活地应用于各种算法和问题解决中。例如，在深度优先搜索（DFS）、回溯法、表达式求值等方面，堆栈都发挥着关键作用。

资源推荐

资源详情

资源评论

收起资源包目录

用C++类的方式实现的栈的操作大全.rar （3个子文件）

用C++类的方式实现的栈的操作大全

stack.h 2KB

stack.cpp 10KB

stack_main.cpp 809B

// stack.cpp: implementation of the stack class. // ////////////////////////////////////////////////////////////////////// #include "stack.h" #include <iostream> #include <malloc.h> ////////////////////////////////////////////////////////////////////// // Construction/Destruction ////////////////////////////////////////////////////////////////////// stack* g_pStack = NULL; stack::stack()//构造函数 { InitStack(); } stack::~stack()//析构函数 { DestroyStack(); //销毁链栈 } ///@brief 函数名： mainface() ///@brief 函数功能：系统主界面 ///@date 2011-4-12 ///@param [IN] ///@retval ///@return ///@note 备注： void mainface()//系统主界面 { printf( "\n"); printf( "\n"); printf( "\n"); printf( "\n"); printf( " ****************************************************"); printf( "\n"); printf( " WELCOME TO THE CODE ZOON OF STACK "); printf( "\n"); printf( " 欢迎来到栈的园地 "); printf( "\n"); printf( " ****************************************************"); printf( "\n"); printf( "\n"); } ///@brief 函数名： mainmenu() ///@brief 函数功能：系统管理界面 ///@date 2011/4/12--2011/4/14 ///@param [IN] ///@retval ///@return ///@note 备注： void mainmenu()//系统管理界面 { char ch; char yes_no; system("cls"); //调用清屏函数。 do { printf ( "\n"); printf ( "\n"); printf ( "\n"); printf ( "\n"); printf ( "\n"); printf ( "**************************************************************\n"); printf ( "* 请输入选项编号（A-J）： *\n"); printf ( "**************************************************************\n"); printf ( "* A、构造空栈 *\n"); printf ( "* B、销毁栈 *\n"); printf ( "* C 清除栈 *\n"); printf ( "* D、判断栈是否为空 *\n"); printf ( "* E、求栈长度 *\n"); printf ( "* F、返回栈顶元素 *\n"); printf ( "* G 插入栈顶元素 *\n"); printf ( "* H、弹出删除栈顶元素 *\n"); printf ( "* I、遍历打印栈元素 *\n"); printf ( "* J、退出 *\n"); printf ( "**************************************************************\n"); printf ( "请输入你的选择：\n"); //getchar(); scanf("%c",&ch); ElemType e; switch (ch) { case'A': //如果以前的栈没有销毁，则先销毁，或者提示他先销毁。 if ( g_pStack != NULL ) { free(g_pStack);//销毁栈 g_pStack = NULL; } g_pStack = new stack;//初始化栈 break; case 'B': if ( g_pStack != NULL ) { free(g_pStack);//销毁栈 g_pStack = NULL; } else { HintCreatStack(); } break; case 'C': if ( g_pStack == NULL ) { HintCreatStack(); } else { g_pStack->ClearStack (); //清除栈 } break; case 'D': if ( g_pStack == NULL ) { HintCreatStack(); } else { if ( g_pStack->StackEmpty () )//判断栈是否为空 { printf("YES\n"); } else { printf("NO\n"); } } break; case 'E': if ( g_pStack == NULL ) { HintCreatStack(); } else { printf( "%d\n", g_pStack->StackLength () );//求栈长度 } break; case 'F': if ( g_pStack == NULL ) { HintCreatStack(); } else { if ( g_pStack->GetTop ( e ) ) //取栈顶元素 { printf( "%d\n", e ); } else { printf("空栈！\n"); } } break; case 'G': if ( g_pStack == NULL ) { HintCreatStack(); } else { printf( "请输入要插入的整数：\n"); scanf("%d",&e); g_pStack->Push ( e );//进栈。插入栈顶元素:进栈，将元素e插入到栈中作为栈顶元素 } break; case 'H': if ( g_pStack == NULL ) { HintCreatStack(); } else { if ( g_pStack->Pop ( e ) )//出栈。返回栈顶元素:出栈，从栈中退出栈顶元素，并将其值赋给e { printf( "%d\n", e ); } else { printf("空栈！\n"); } } break; case 'I': if ( g_pStack == NULL ) { HintCreatStack(); } else { g_pStack->DispStack();//遍历打印栈元素 } break; case 'J': exit (0); break; default: { printf("输入错误，请重新输入\n"); mainmenu(); } } printf( "\n 要继续选择吗(Y/N)?\n"); do { scanf("%c",&yes_no);//yes_no = getchar(); } while ( yes_no != 'Y' && yes_no != 'y' && yes_no != 'N' && yes_no != 'n') ; if ( yes_no == 'N' || yes_no == 'n' ) { break; } } while ( yes_no == 'y' || yes_no == 'Y' ); } ///@brief 函数名： InitStack() ///@brief 函数功能：栈的初始化 ///@date 2011/4/15 ///@param [IN] ///@retval ///@return ///@note 备注： void stack::InitStack() //栈的初始化 { m_pHeadNode = ( NodeType * )malloc( sizeof ( stack ));//为头结点申请空间 m_pHeadNode ->next = NULL; system("cls"); //调用清屏函数。 printf("\n"); printf("\n"); printf("\n"); printf("\n"); printf("******************************************************"); printf("\n"); printf(" 完成栈的初始化!! "); printf("\n"); printf("******************************************************\n"); printf("\n"); } ///@brief 函数名： DestroyStack() ///@brief 函数功能：栈的销毁 ///@date 2011/4/16 ///@param [IN] ///@retval ///@return ///@note 备注： void stack::DestroyStack()//销毁栈 { NodeType *p = m_pHeadNode, *q = NULL; while ( p != NULL ) { q = p; p = p->next; free( q ); }; m_pHeadNode = NULL; system("cls"); //调用清屏函数。 printf("\n"); printf("\n"); printf("\n"); printf("\n"); printf("******************************************************"); printf("\n"); printf(" 完成栈的销毁!! "); printf("\n"); printf("******************************************************"); printf("\n"); } ///@brief 函数名： ClearStack () ///@brief 函数功能：栈的清除 ///@date 2011/4/17 ///@param [IN] ///@retval ///@return ///@note 备注： int stack::ClearStack () //清除栈 { NodeType *p = m_pHeadNode ->next,*q = NULL; while ( p != NULL ) { q = p; p = p->next; free( q ); } m_pHeadNode->next = NULL; system("cls"); //调用清屏函数。 printf("\n"); printf("\n"); printf("\n"); printf("\n"); printf("******************************************************"); printf("\n"); printf(" 完成栈的清除!! "); printf("\n"); printf("******************************************************"); printf("\n"); return 1; } ///@brief 函数名： StackLength () ///@brief 函数功能：求栈的长度 ///@date 2011/4/18 ///@param [IN] ///@retval ///@return ///@note 备注： int stack::StackLength ()//求栈长度 { int i = 0; NodeType *p; p = m_pHeadNode ->next; while( p != NULL ) { i++; p = p->next; } return i; } ///@brief 函数名： StackEmpty () ///@brief 函数功能：判断栈是否为空 ///@date 2011/4/19 ///@param [IN] ///@retval ///@return ///@note 备注： int stack::StackEmpty ()//判断栈是否为空 { return ( m_pHeadNode ->next == NULL ); } ///@brief 函数名： Push ( ElemType e ) ///@brief 函数功能：插入栈顶元素:进栈，将元素e插入到栈中作为栈顶元素 ///@date 2011/4/20 ///@param [IN] ///@retval //

评论收藏

内容反馈