用C++实现栈
简介：通过题目的方式来介绍如何通过C++实现栈，通过理解栈的底层原理，来更好的学习这个数据结构
题目
请设计通用栈类。
首先定义数据元素类型
typedef double ELEMENT;
然后定义栈
class STACK { public: STACK(); ~STACK(); bool Push(const ELEMENT &value); bool Pop(ELEMENT &value); bool Clear(); bool Empty() const; int Length() const; const static int stackSize; private: int size, top; ELEMENT *element; }; const int STACK::stackSize = 5;
说明：
- size 为动态数组的尺寸，top 为栈顶元素的下标，element 为动态数组的起始地址。
- stackSize 为动态数组的尺寸，初始值为 5。
- 构造函数：初始化栈：将初始尺寸保存到 size，将栈顶下标 top 置为 -1，为动态数组分配内存并将起始地址保存到 element。
- 析构函数：清理栈：释放动态数组的内存。
- Push 函数：若栈未满，则将元素 value 保存到栈中，函数值为 true；否则报告上溢错误，函数值为 false。
- Pop 函数：若栈不空，则从栈中取出元素并保存到 value中，函数值为 true；否则报告下溢错误，函数值为 false。
- Clear 函数：清空栈，操作成功，函数值为 true。
- Empty 函数：若栈空，则函数值为 true，否则为 false。
- Length 函数：函数值为栈中元素的数量。
裁判程序
#include <iostream> #include <iomanip> using namespace std; #include <cctype> typedef double ELEMENT; class STACK { public: STACK(); ~STACK(); bool Push(const ELEMENT &value); bool Pop(ELEMENT &value); bool Clear(); bool Empty() const; int Length() const; const static int stackSize; private: int size, top; ELEMENT *element; }; const int STACK::stackSize = 5; /* 你提交的代码将被嵌在这里 */ int main() { STACK stack; ELEMENT value; char choice; do { cout << "Push pOp Clear Empty Length Quit > "; cin >> choice; choice = toupper(choice); switch (choice) { case 'P': cout << "Value: "; cin >> value; if (stack.Push(value)) { cout << "Push successfully!\n"; } else { cout << "Push failed!\n"; } break; case 'O': if (stack.Pop(value)) { cout << "Pop successfully!\n"; cout << "Value: " << value << endl; } else { cout << "Pop failed!\n"; } break; case 'C': if (stack.Clear()) { cout << "Clear successfully!\n"; } else { cout << "Clear failed!\n"; } break; case 'E': if (stack.Empty()) { cout << "Stack is empty!\n"; } else { cout << "Stack is not empty!\n"; } break; case 'L': cout << "Stack length: " << stack.Length() << endl; break; case 'Q': break; default: cout << "Incorrect choice!\n"; } } while (choice != 'Q'); }
测试样例1
Push pOp Clear Empty Length Quit > t Incorrect choice! Push pOp Clear Empty Length Quit > K Incorrect choice! Push pOp Clear Empty Length Quit > Q
测试样例2
Push pOp Clear Empty Length Quit > L Stack length: 0 Push pOp Clear Empty Length Quit > e Stack is empty! Push pOp Clear Empty Length Quit > P Value: 4.5 Push successfully! Push pOp Clear Empty Length Quit > p Value: 1.6 Push successfully! Push pOp Clear Empty Length Quit > l Stack length: 2 Push pOp Clear Empty Length Quit > E Stack is not empty! Push pOp Clear Empty Length Quit > o Pop successfully! Value: 1.6 Push pOp Clear Empty Length Quit > O Pop successfully! Value: 4.5 Push pOp Clear Empty Length Quit > O Stack underflow! Pop failed! Push pOp Clear Empty Length Quit > q
测试样例3
Push pOp Clear Empty Length Quit > p Value: 0.5 Push successfully! Push pOp Clear Empty Length Quit > p Value: 1.7 Push successfully! Push pOp Clear Empty Length Quit > p Value: 2.8 Push successfully! Push pOp Clear Empty Length Quit > p Value: 3.6 Push successfully! Push pOp Clear Empty Length Quit > p Value: 4.9 Push successfully! Push pOp Clear Empty Length Quit > p Value: 9.9 Stack overflow! Push failed! Push pOp Clear Empty Length Quit > L Stack length: 5 Push pOp Clear Empty Length Quit > e Stack is not empty! Push pOp Clear Empty Length Quit > C Clear successfully! Push pOp Clear Empty Length Quit > l Stack length: 0 Push pOp Clear Empty Length Quit > E Stack is empty! Push pOp Clear Empty Length Quit > p Value: 8.5 Push successfully! Push pOp Clear Empty Length Quit > O Pop successfully! Value: 8.5 Push pOp Clear Empty Length Quit > q
输出样例
Push pOp Clear Empty Length Quit >
输入样例
q
代码长度限 16 KB 时间限制 400 ms 内存限制 64 MB
题解：
STACK::STACK() { size = stackSize; top = -1; element = new ELEMENT[size]; // 这里是c++程序 所以不能使用C语言的malloc和free函数因为new函数是每个元素都要构造的 但是malloc不会 } STACK::~STACK() { delete []element; // 释放资源 } bool STACK::Push(const ELEMENT &value) { if (top + 1 >= this->size) // 首先判断一下是否栈满了 { cout << "Stack overflow!\n"; // 如果栈满了就需要输出Stack overflow! return false ; // 返回入栈失败 } this->element[++top] = value; // 反之插入栈顶 return true; } int STACK::Length() const // 因为初始值是top = -1所以返回长度的时候需要top+1 { return top + 1; } bool STACK::Pop(ELEMENT &value) { if (top == -1) // 先判断栈是否为空 { cout << "Stack underflow!\n"; return false; } value = this->element[top--]; // 不为空的出栈第一个元素 然后top - 1 return true; } bool STACK::Clear() // 通过把top置为-1的方式快速清空栈 { // if (top == -1) return false; top = -1; return true; } bool STACK::Empty() const // 如果top=-1那么栈为空 { return top == -1; }
