107 lines
2.1 KiB
C++
107 lines
2.1 KiB
C++
|
// 设计一个 Stack 的类，实现栈的基本操作，包括入栈、出栈和判断栈是否为空等。主要用于存放int数值或string字符串，并对其操作。
|
|||
|
|
// 【提示】
|
|||
|
|
// 1\) 使用数组实现，每一次重分数组空间的大小是原大小的2倍；
|
|||
|
|
|
|||
|
|
// 2\) Stack是栈的结构（FILO先进后出的）
|
|||
|
|
#include <iostream>
|
|||
|
|
#include <cstring>
|
|||
|
|
#include <cstdlib>
|
|||
|
|
|
|||
|
|
using namespace std;
|
|||
|
|
|
|||
|
|
class Stack
|
|||
|
|
{
|
|||
|
|
private:
|
|||
|
|
int capacity; // 栈容量
|
|||
|
|
int size; // 当前栈中元素个数
|
|||
|
|
int *data; // 存放栈的数组
|
|||
|
|
public:
|
|||
|
|
Stack()
|
|||
|
|
{
|
|||
|
|
this->capacity = 10; // 初始容量
|
|||
|
|
this->size = 0;
|
|||
|
|
this->data = new int[this->capacity]; // 初始化栈数据数组
|
|||
|
|
}
|
|||
|
|
~Stack()
|
|||
|
|
{
|
|||
|
|
delete[] data; // 删除栈数据数组
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
public:
|
|||
|
|
void push(int value); // 入栈
|
|||
|
|
int pop(); // 出栈
|
|||
|
|
int isEmpty(); // 判断栈空否
|
|||
|
|
};
|
|||
|
|
|
|||
|
|
void Stack::push(int value)
|
|||
|
|
{
|
|||
|
|
if (size == capacity)
|
|||
|
|
{
|
|||
|
|
cout << "栈满，重新分配空间中" << endl;
|
|||
|
|
int newCapacity = capacity * 2;
|
|||
|
|
int *newData = new int[newCapacity];
|
|||
|
|
for (int i = 0; i < size; i++)
|
|||
|
|
{
|
|||
|
|
newData[i] = data[i];
|
|||
|
|
}
|
|||
|
|
delete[] data;
|
|||
|
|
data = newData;
|
|||
|
|
capacity = newCapacity;
|
|||
|
|
cout << "空间分配完成，数据转存完毕" << endl;
|
|||
|
|
}
|
|||
|
|
data[size] = value;
|
|||
|
|
cout << value << " 入栈成功" << endl;
|
|||
|
|
size++;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
int Stack::pop()
|
|||
|
|
{
|
|||
|
|
if (size == 0)
|
|||
|
|
{
|
|||
|
|
cout << "栈空" << endl;
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
int popValue = data[size - 1];
|
|||
|
|
size--;
|
|||
|
|
cout << "出栈成功" << endl;
|
|||
|
|
return popValue;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
int Stack::isEmpty()
|
|||
|
|
{
|
|||
|
|
if (size == 0)
|
|||
|
|
{
|
|||
|
|
cout << "栈空" << endl;
|
|||
|
|
return 1; // 非 0 为栈空
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
return 0;
|
|||
|
|
cout << "栈不空" << endl;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
int main()
|
|||
|
|
{
|
|||
|
|
Stack stk;
|
|||
|
|
|
|||
|
|
stk.push(10);
|
|||
|
|
stk.push(12);
|
|||
|
|
stk.push(16);
|
|||
|
|
stk.push(5);
|
|||
|
|
|
|||
|
|
while (!stk.isEmpty())
|
|||
|
|
{
|
|||
|
|
cout << stk.pop() << " ";
|
|||
|
|
}
|
|||
|
|
cout << endl;
|
|||
|
|
|
|||
|
|
// stk.push(7);
|
|||
|
|
|
|||
|
|
stk.isEmpty();
|
|||
|
|
|
|||
|
|
return 0;
|
|||
|
|
}
|