stack容器
stack是一种先进后出(First In Last Out, FILO)的数据结构，它只有一个出口，形式如图所示。stack容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端外，没有任何其他方法可以存取stack的其他元素。换言之，stack不允许有遍历行为。
有元素推入栈的操作称为push；将元素推出stack的操作称为pop。
stack没有迭代器
stack所有元素的进出都必须符合”先进后出”的条件，只有stack顶端的元素，才有机会被外界取用。stack不提供遍历功能，也不提供迭代器。
stack常用API
stack构造函数
cpp
stack<T> stkT;//stack采用模板类实现， stack对象的默认构造形式：
stack(const stack &stk);//拷贝构造函数stack赋值操作
cpp
stack& operator=(const stack &stk);//重载等号操作符stack数据存取操作
cpp
push(elem);//向栈顶添加元素
pop();//从栈顶移除第一个元素
top();//返回栈顶元素stack大小操作
cpp
empty();//判断堆栈是否为空
size();//返回堆栈的大小手动实现stack
int类型的顺序栈
点击查看代码
cpp
#include <iostream>
class SeqStack {
public:
SeqStack() {
this->_pstack = new int[_defaultSize];
this->_top = -1;
this->_size = _defaultSize;
}
~SeqStack() {
delete[] _pstack;
this->_pstack = nullptr;
}
// 栈操作
void push(int num) {
if (full()) {
resize();
}
this->_pstack[++this->_top] = num;
}
void pop() {
if (this->_top == -1) {
std::__throw_overflow_error("栈为空");
}
this->_top--;
}
void reserve(int num) {
if (num < this->_top + 1) {
std::__throw_length_error("预留空间小于栈中现有元素个数");
}
resize(num);
}
// 查看栈信息
bool full() const { return this->_top == this->_size - 1; }
bool empty() const { return this->_top == -1; }
int size() const { return this->_size; }
int useSize() const { return this->_top + 1; }
int top() const {
if (this->_top == -1) {
std::__throw_overflow_error("栈为空");
}
return this->_pstack[this->_top];
}
private:
void resize(int size = 0) {
int *newStack = nullptr;
if (size != 0) {
newStack = new int[size];
} else {
newStack = new int[this->_size * this->_defaultResize];
}
for (int i = 0; i < this->_top + 1; ++i) {
newStack[i] = this->_pstack[i];
}
delete[] this->_pstack;
this->_pstack = newStack;
if (size != 0) {
this->_size = size;
} else {
this->_size *= this->_defaultResize;
}
}
private:
const int _defaultSize = 10; // 默认栈大小
const int _defaultResize = 2; // 默认扩容倍数
int *_pstack; // 存放数据的数据
int _top; // 栈顶的索引
int _size; // 栈大小
};
int main() {
try {
SeqStack s;
std::cout << "s.size " << s.size() << std::endl;
for (int i = 0; i < 15; ++i) {
s.push(rand() % 100);
}
std::cout << "s.useSize " << s.useSize() << "\ts.size " << s.size() << std::endl;
s.reserve(30);
std::cout << "s.useSize " << s.useSize() << "\ts.size " << s.size() << std::endl;
for (int i = 0; i < 20; ++i) {
s.pop();
}
std::cout << "s.useSize " << s.useSize() << "\ts.size " << s.size() << std::endl;
} catch (const std::exception &e) {
std::cout << "Error:" << e.what() << std::endl;
}
return 0;
}泛型的顺序栈
点击查看代码
cpp
#include <iostream>
template <class T>
class SeqStack {
public:
SeqStack() {
try {
this->_pstack = new T[_defaultSize];
} catch (const std::bad_alloc &e) {
throw std::runtime_error("new error 内存分配失败");
}
this->_top = -1;
this->_size = _defaultSize;
}
// 禁用拷贝构造，防止浅拷贝
SeqStack(const SeqStack &) = delete;
SeqStack &operator=(const SeqStack &s) = delete;
~SeqStack() {
delete[] _pstack;
this->_pstack = nullptr;
}
// 栈操作
void push(const T &data) {
if (full()) {
resize();
}
this->_pstack[++this->_top] = data;
}
void pop() {
if (this->_top == -1) {
throw std::underflow_error("pop error 栈为空");
}
this->_top--;
}
void reserve(int num) {
if (num < this->_top + 1) {
std::__throw_length_error("reserve error 预留空间小于栈中现有元素个数");
}
resize(num);
}
// 查看栈信息
bool full() const { return this->_top == this->_size - 1; }
bool empty() const { return this->_top == -1; }
int size() const { return this->_size; }
int useSize() const { return this->_top + 1; }
T top() const {
if (this->_top == -1) {
throw std::underflow_error("top error 栈为空");
}
return this->_pstack[this->_top];
}
private:
void resize(int size = 0) {
T *newStack = nullptr;
if (size != 0) {
try {
newStack = new T[size];
} catch (const std::bad_alloc &e) {
throw std::runtime_error("new error 内存分配失败");
}
} else {
try {
newStack = new T[static_cast<int>(this->_size * this->_defaultResize)];
} catch (const std::bad_alloc &e) {
throw std::runtime_error("new error 内存分配失败");
}
}
for (int i = 0; i < this->_top + 1; ++i) {
newStack[i] = std::move(this->_pstack[i]);
}
delete[] this->_pstack;
this->_pstack = newStack;
if (size != 0) {
this->_size = size;
} else {
this->_size *= this->_defaultResize;
}
}
private:
const int _defaultSize = 10; // 默认栈大小
const float _defaultResize = 1.5; // 默认扩容倍数
T *_pstack; // 存放数据的数据
int _top; // 栈顶的索引
int _size; // 栈大小
};
int main() {
try {
// 测试字符串类型
SeqStack<std::string> strStack;
strStack.push("Hello");
strStack.push("Generics");
std::cout << "Top element: " << strStack.top() << std::endl;
strStack.pop();
std::cout << "Top element: " << strStack.top() << std::endl;
strStack.pop();
std::cout << "Top element: " << strStack.top() << std::endl;
strStack.pop();
std::cout << "Top element: " << strStack.top() << std::endl;
} catch (const std::exception &e) {
std::cout << e.what() << std::endl;
}
return 0;
}