数据结构 C++ 链式栈

节点结构

// 结点类 
class Node
{
public:// 构造函数 Node(int val): next_(nullptr), data_(val) {}public:// 节点的下一个节点 Node* next_;// 节点的值 int data_;	
};

方法

入栈

    // 入栈 void push(int val){if(this->isFull())  {std::cout << "Stack capacity is full!" <<std::endl;return;}Node* current = new Node(val);current->next_ = this->head_;this->head_ = current;this->size_++;}

出栈

	// 出栈int pop(){if(isEmpty()){std::cout << "Stack is Empty!" << std::endl; return -1;		}Node* temp = this->head_;int val = temp->data_;this->head_ = temp->next_;delete temp;this->size_--;return val;} 

获取栈顶元素

	// 获取栈顶元素 int top() const{if(isEmpty()){std::cout << "Stack is Empty!" << std::endl; return -1;		}return this->head_->data_;}

遍历栈

	// 遍历栈 void printfStack(){if(isEmpty()) {std::cout << "Stack is Empty!" << std::endl; return;		} Node* current = this->head_;int index = 0;while(current != nullptr){std::cout << "Stack[" << index << "]" << current->data_ << std::endl;current= current->next_;++index; } }

清空栈

	// 清空栈void clear(){while(!isEmpty()) {pop();} }

获取栈大小

	// 获取栈大小 int size() const{return this->size_;}

判断栈空

	// 判断栈空 bool isEmpty() const {return this->size_ == 0;}

判断栈满

	// 判断栈满bool isFull() const {return this->size_ == this->capacity_;} 

完整代码

#pragma once#include <iostream>// 结点类 
class Node
{
public:// 构造函数 Node(int val): next_(nullptr), data_(val) {}public:// 节点的下一个节点 Node* next_;// 节点的值 int data_;	
};// 链式栈 
class LinkStack
{
public:// 默认构造LinkStack() : head_(nullptr), size_(0), capacity_(100){}// 有参构造 LinkStack(int value) : head_(nullptr), size_(0), capacity_(value){}~LinkStack(){clear();	} // 入栈 void push(int val){if(this->isFull()){std::cout << "Stack capacity is full!" <<std::endl;return;}Node* current = new Node(val);current->next_ = this->head_;this->head_ = current;this->size_++;}// 出栈int pop(){if(isEmpty()){std::cout << "Stack is Empty!" << std::endl; return -1;		}Node* temp = this->head_;int val = temp->data_;this->head_ = temp->next_;delete temp;this->size_--;return val;} // 获取栈顶元素 int top() const{if(isEmpty()){std::cout << "Stack is Empty!" << std::endl; return -1;		}return this->head_->data_;}// 遍历栈 void printfStack(){if(isEmpty()) {std::cout << "Stack is Empty!" << std::endl; return;		} Node* current = this->head_;int index = 0;while(current != nullptr){std::cout << "Stack[" << index << "]" << current->data_ << std::endl;current= current->next_;++index; } }// 清空栈void clear(){while(!isEmpty()) {pop();} }// 获取栈大小 int size() const{return this->size_;}// 判断栈空 bool isEmpty() const {return this->size_ == 0;}// 判断栈满bool isFull() const {return this->size_ == this->capacity_;} private:// 头节点 Node* head_;// 栈大小 int size_;// 栈容量int capacity_; 
};

测试代码

#include <iostream>#include "LinkStack.h" int main() 
{LinkStack *link_ = new LinkStack(5);// 测试栈大小 std::cout << "size: " << link_->size() << std::endl; // 测试为空 std::cout << "isEmpty: " << link_->isEmpty() << std::endl; // 测试插入 link_->push(1);link_->push(2);link_->push(3);link_->push(4);link_->push(5);link_->printfStack();std::cout << "isEmpty: " << link_->isEmpty() << std::endl; std::cout << "size: " << link_->size() << std::endl; // 测试栈顶 std::cout << "top: " << link_->top() << std::endl; // 测试清除 link_->clear();link_->printfStack();// 测试栈容量 std::cout << "isFull: " << link_->isFull() << std::endl;// 测试满栈 link_->push(1);link_->push(2);link_->push(3);link_->push(4);link_->push(5);link_->push(6);std::cout << "isFull: " << link_->isFull() << std::endl;return 0; 
}