目錄
結構特性
結構實現
結構容器
結構設計
順序棧
鏈式棧
結構特性
-
棧(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();}}};
