569-顺序栈和链式栈的实现

╰+哭是因爲堅強的太久メ 2022-09-11 13:11 167阅读 0赞

## 顺序栈的实现 ##

**动态可扩容的数组的顺序栈**

#include <iostream>
    using namespace std;
    
    //顺序栈  C++容器适配器stack：push   pop   top   empty  size
    class SeqStack
    {
        
    public:
    	SeqStack(int size = 10)//构造函数 
    		: mtop(0)
    		, mcap(size)
    	{
        
    		mpStack = new int[mcap];
    	}
    	~SeqStack()//析构函数 
    	{
        
    		delete[]mpStack;
    		mpStack = nullptr;
    	}
    
    public:
    	//入栈
    	void push(int val)
    	{
        
    		if (mtop == mcap)//如果栈满了 
    		{
        
    			//栈扩容
    			expand(2 * mcap);
    		}
    		mpStack[mtop++] = val;
    	}
    	//出栈
    	void pop()
    	{
        
    		if (mtop == 0)
    			throw "stack is empty!";//抛异常，也是函数结束的方法 
    		mtop--;
    	}
    
    	//获取栈顶元素
    	int top() const
    	{
        
    		if (mtop == 0)
    			throw "stack is empty!";
    		return mpStack[mtop - 1];
    	}
    
    	//栈空
    	bool empty() const
    	{
        
    		return mtop == 0;
    	}
    	//栈中有效元素的个数
    	int size() const {
         return mtop; }
    
    private:
    	void expand(int size)//扩容 
    	{
        
    		int* p = new int[size];
    		memcpy(p, mpStack, mtop * sizeof(int));//拷贝元素
    		delete[]mpStack;
    		mpStack = p;
    		mcap = size;
    	}
    
    private:
    	int* mpStack;//可扩容的数组 
    	int mtop;//栈顶位置
    	int mcap;//栈空间的大小
    };
    
    int main()
    {
        
    	int arr[] = {
         12,4,56,7,89,31,53,75 };
    	SeqStack s;
    
    	for (int v : arr)
    	{
        
    		s.push(v);//入栈
    	}
    
    	while (!s.empty())
    	{
        
    		cout << s.top() << " ";//获取栈顶元素值
    		s.pop();//出栈
    	}
    	cout << endl;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**顺序栈的效率低**：因为扩容，要额外开辟更大的内存，然后把数据从老内存上一个一个拷贝到新内存上，然后释放旧内存，然后成员变量指针指向新的内存，其他成员变量进行合理的重置。如果数据量比较大，效率就低了。  
**时间复杂度是O(n）**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]

## 链式栈的实现 ##

**对于链表来说，不存在扩容不扩容，因为每个节点都是独立new创建出来的**  
**链表的头插法和栈的入栈很相似**  
**链表的头删就是栈的出栈**  
**链表的首元素就是栈顶**

#include <iostream>
    using namespace std;
    
    //链式栈
    class LinkStack
    {
        
    public:
    	LinkStack() : size_(0)//构造函数
    	{
        
    		head_ = new Node;
    	}
    	~LinkStack()//析构函数
    	{
        
    		Node* p = head_;
    		while (p != nullptr)
    		{
        
    			head_ = head_->next_;
    			delete p;
    			p = head_;
    		}
    	}
    
    public:
    	//入栈 O(1)   把链表头节点后面，即第一个有效节点的位置，当作栈顶位置
    	void push(int val)
    	{
        
    		//head_ -> 1
    		//head_ -> 2 -> 1
    		Node* node = new Node(val);
    		node->next_ = head_->next_;
    		head_->next_ = node;
    		size_++;
    	}
    	//出栈 O(1)
    	void pop()
    	{
        
    		if (head_->next_ == nullptr)
    			throw "stack is empty!";
    		Node* p = head_->next_;
    		head_->next_ = p->next_;
    		delete p;
    		size_--;
    	}
    	//获取栈顶元素
    	int top() const
    	{
        
    		if (head_->next_ == nullptr)
    			throw "stack is empty!";//结束函数的异常的类型不用和返回值一样
    		return head_->next_->data_;
    	}
    	//判空
    	bool empty() const
    	{
        
    		return head_->next_ == nullptr;
    	}
    	//返回栈元素个数 遍历一遍链表，记录节点个数O(n)    想达到O(1)
    	int size() const
    	{
        
    		return size_;
    	}
    
    private:
    	struct Node//节点的类型
    	{
        
    		Node(int data = 0) : data_(data), next_(nullptr) {
        }
    		int data_;
    		Node* next_;
    	};
    
    	Node* head_;
    	int size_;
    };
    
    int main()
    {
        
    	int arr[] = {
         12,4,56,7,89,31,53,75 };
    	LinkStack s;
    
    	for (int v : arr)
    	{
        
    		s.push(v);
    	}
    
    	cout << s.size() << endl;
    
    	while (!s.empty())
    	{
        
    		cout << s.top() << " ";
    		s.pop();
    	}
    	cout << endl;
    
    	cout << s.size() << endl;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c219f545a8684df1ab967a3e6515050c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/24175a0f3fd740c5bad1f80df31f0c47.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/e8c988f9c29a4494b41eb8f73f0cfb5f.png