88 lines
2.2 KiB
C++
88 lines
2.2 KiB
C++
|
// 设计一个模板类 Stack，实现基本的堆栈功能，包括入栈（push）、出栈（pop）、获取栈顶元素（top）和判断栈是否为空（isEmpty）等操作。
|
|||
|
|
// 【提示】Stack栈结构的特性是FILO(先进后出)
|
|||
|
|
#include <iostream>
|
|||
|
|
|
|||
|
|
using namespace std;
|
|||
|
|
|
|||
|
|
template <typename T>
|
|||
|
|
class Stack
|
|||
|
|
{
|
|||
|
|
private:
|
|||
|
|
int capacity; // 容量
|
|||
|
|
int size; // 已存数量计数器
|
|||
|
|
T *arr; // 指向数组的指针
|
|||
|
|
|
|||
|
|
public:
|
|||
|
|
Stack(int capacity)
|
|||
|
|
{
|
|||
|
|
this->capacity = capacity;
|
|||
|
|
this->arr = new T[capacity];
|
|||
|
|
this->size = 0;
|
|||
|
|
}
|
|||
|
|
Stack(const Stack<T> &other)
|
|||
|
|
{
|
|||
|
|
this->capacity = other.capacity;
|
|||
|
|
this->size = other.size;
|
|||
|
|
this->arr = new T[capacity];
|
|||
|
|
for (int i = 0; i < size; i++)
|
|||
|
|
{
|
|||
|
|
this->arr[i] = other.arr[i];
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
~Stack()
|
|||
|
|
{
|
|||
|
|
delete[] arr;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
public:
|
|||
|
|
// & 用于返回引用，支持链式调用
|
|||
|
|
Stack &push(T val)
|
|||
|
|
{
|
|||
|
|
if (size == capacity)
|
|||
|
|
{
|
|||
|
|
cout << "栈已经满了!" << endl;
|
|||
|
|
return *this;
|
|||
|
|
}
|
|||
|
|
arr[size++] = val;
|
|||
|
|
return *this; // 返回自身，支持链式调用
|
|||
|
|
}
|
|||
|
|
T pop()
|
|||
|
|
{
|
|||
|
|
if (size == 0)
|
|||
|
|
{
|
|||
|
|
cout << "栈已经空了!" << endl;
|
|||
|
|
return -1;
|
|||
|
|
}
|
|||
|
|
return arr[--size]; // 先减再取，因为size是计数器，指向下一个空位
|
|||
|
|
}
|
|||
|
|
T top()
|
|||
|
|
{
|
|||
|
|
if (size == 0)
|
|||
|
|
{
|
|||
|
|
cout << "栈已经空了!" << endl;
|
|||
|
|
return -1;
|
|||
|
|
}
|
|||
|
|
return arr[size - 1]; // 直接取顶部元素
|
|||
|
|
}
|
|||
|
|
string isEmpty()
|
|||
|
|
{
|
|||
|
|
return size == 0 ? "栈空" : "栈未空"; // 判断计数器是否为 0，为 0 表示栈空
|
|||
|
|
}
|
|||
|
|
};
|
|||
|
|
|
|||
|
|
int main()
|
|||
|
|
{
|
|||
|
|
Stack<int> s(5);
|
|||
|
|
s.push(1).push(2).push(3).push(4).push(5);
|
|||
|
|
cout << s.pop() << endl; // 5
|
|||
|
|
cout << s.pop() << endl; // 4
|
|||
|
|
cout << s.top() << endl; // 3
|
|||
|
|
cout << s.isEmpty() << endl; // 栈未空
|
|||
|
|
cout << s.pop() << endl; // 3
|
|||
|
|
cout << s.pop() << endl; // 2
|
|||
|
|
cout << s.pop() << endl; // 1
|
|||
|
|
cout << s.isEmpty() << endl; // 栈空
|
|||
|
|
cout << s.pop() << endl; // 栈已经空了! -1
|
|||
|
|
return 0;
|
|||
|
|
}
|