目录
结构特性
栈(stack)是线性表的一种形式，限定仅在表的一端进行插入或者删除的操作。
栈顶 - 表中允许插入、删除的一端称为栈顶(top)，栈顶位置是可以发生变化的。
插入 - 进栈、入栈、压栈。
删除 - 出栈。
栈底 - 表中不允许插入、删除的一端称为栈底(bottom)，栈底位置通常是固定不变的。
空栈 - 表中不存在任何元素。
LIFO - last in first out - 先进后出、后进先出。
结构实现
- 顺序栈
int Arr[5] = {0};
[栈顶] - Arr[4]
[元素] - Arr[x]
[元素] - Arr[x]
[元素] - Arr[x]
[栈底] - Arr[0]
顺序栈使用连续的内存空间来存储元素，通常使用数组来实现。
栈底指向数组起始地址(下标为0的元素)。
栈顶指向当前栈中最后一个压入的元素位置。
链式栈
[栈顶元素 | 指针] -> [下一个元素 | 指针] -> ... -> [栈底元素 | 空指针]
结构容器
#include <iostream>
#include <stack>
int main()
{
std::stack<int> myStack;
std::cout << myStack.size() << std::endl;
std::cout << myStack.empty() << std::endl;
//入栈
myStack.push(1);
myStack.push(2);
myStack.push(3);
std::cout << myStack.size() << std::endl;
std::cout << myStack.empty() << std::endl;
//获取栈顶元素
std::cout << myStack.top() << std::endl;
//出栈
myStack.pop();
std::cout << myStack.top() << std::endl;
return 0;
}
结构设计
顺序栈
#include <iostream>
class Stack
{
public:
int* data; //栈的数组
int topIndex; //栈顶索引
int capacity; //栈的容量
public:
Stack(); //默认构造函数
Stack(int Size); //有参构造函数
Stack(const Stack& other); //拷贝构造函数
~Stack(); //默认析构函数
public:
void Push(int value); //入栈函数
void Pop(); //出栈函数
int Top(); //栈顶元素
public:
bool IsEmpty(); //是否为空
int Size(); //元素个数
};
Stack::Stack() : data(nullptr), topIndex(-1), capacity(0)
{
}
Stack::Stack(int Size) : topIndex(-1), capacity(Size)
{
this->data = new int[capacity] {};
}
Stack::Stack(const Stack& other) : data(new int[other.capacity]), topIndex(other.topIndex), capacity(other.capacity)
{
for (size_t i = 0; i < capacity; i++)
{
this->data[i] = other.data[i];
}
}
Stack::~Stack()
{
if (data != NULL)
{
delete[] data;
data = nullptr;
}
}
void Stack::Push(int value)
{
if (Size() == capacity)
{
//默认容量
int size = capacity;
//动态扩容
capacity = (capacity == 0) ? 5 : capacity * 2;
//申请内存
int* newData = new int[capacity] {};
//数据拷贝
memcpy(newData, this->data, size * sizeof(int));
//释放数据
if (this->data != NULL)
{
delete[] this->data;
}
//修正指向
this->data = newData;
}
data[++topIndex] = value;
}
void Stack::Pop()
{
if (IsEmpty())
{
return;
}
--topIndex;
}
int Stack::Top()
{
return this->data[topIndex];
}
bool Stack::IsEmpty()
{
return this->topIndex == -1 ? true : false;
}
int Stack::Size()
{
return topIndex + 1;
}
链式栈
class Node
{
public:
int value;
Node* Next;
Node(int Num) : value(Num), Next(nullptr) {}
};
class Stack
{
public:
Node* Head;
public:
Stack() : Head(nullptr)
{
}
Stack(const Stack& other)
{
if (other.Head == nullptr)
{
Head = nullptr;
}
else
{
Head = new Node(other.Head->value);
Node* head = Head;
Node* node = other.Head->Next;
while (node != nullptr)
{
head->Next = new Node(node->value);
head = head->Next;
node = node->Next;
}
}
}
~Stack()
{
Clear();
}
public:
void Push(int value)
{
Node* node = new Node(value);
node->Next = Head;
Head = node;
}
void Pop()
{
if (!IsEmpty())
{
Node* temp = Head;
Head = Head->Next;
delete temp;
}
}
int Top()
{
if (!IsEmpty())
{
return Head->value;
}
}
public:
bool IsEmpty()
{
return Head == nullptr;
}
void Clear()
{
while (!IsEmpty())
{
Pop();
}
}
};