用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;
}
