栈的实例C++代码实现

àì夳堔傛蜴生んèń 2022-10-26 03:52 138阅读 0赞

**栈是限定仅在表尾进行插入和删除操作的线性表**

**允许插入和删除的一端为栈顶，另一端为栈底，不含任何数据元素的栈称为空栈，栈是一种后进先出的线性表结构。**

*Stack.h*

#pragma once
    #include<iostream>
    
    
    #define Stack_DataType int
    #define Init_StackData 99
    
    class Stack_Node
    {
        
    public:
    	Stack_Node()
    	{
        
    		data = Init_StackData;
    		next = NULL;
    	}
    	Stack_Node(Stack_DataType element) : data(element), next(NULL) 
    	{
        
    	}
    
    	Stack_DataType data;
    	Stack_Node *next;
    
    };
    
    class MyStack
    {
        
    public:
    	MyStack();
    	MyStack(int size);
    	~MyStack();
    
    	void Init_Stack();	//初始化栈
    	void Destory_Stack();	//摧毁栈
    	void Clear_Stack();		//清空栈
    	bool Stack_Empty();		//栈是否为空
    	int Stack_length();		//栈的长度
    		
    	int Top_Stack();							//获取栈顶元素
    	bool Push_Stack(Stack_DataType &value);		//插入栈顶元素
    
    	bool Pop_Stack();							//出栈
    	bool Pop_Stack(Stack_DataType &value);		//删除栈顶元素
    
    	void Print_Stack();
    
    private:
    	Stack_Node *top;		//栈顶
    	Stack_Node *bottom;		//栈底
    };

*Stack.cpp*

#include"Sequence_Stack.h"
    #include<iostream>
    
    MyStack::MyStack()
    {
        
    	Init_Stack();
    }
    
    MyStack::MyStack(int size)
    {
        
    	Init_Stack();
    	Stack_DataType temp_data = Init_StackData;
    	for (int i = 0; i < size; i++)
    	{
        
    		std::cout << "输入第" << i+1 << "元素" << std::endl;
    		std::cin >> temp_data;
    		Push_Stack(temp_data);
    	}
    }
    
    MyStack::~MyStack()
    {
        
    	Clear_Stack();
    	Destory_Stack();
    }
    
    void MyStack::Init_Stack()
    {
        
    	Stack_Node *temp = new Stack_Node;
    	if (temp == 0)
    	{
        
    		std::exit(1);
    	}
    	top = temp;
    	bottom = temp;
    }
    
    void MyStack::Destory_Stack()
    {
        
    	delete(bottom);
    }
    
    void MyStack::Clear_Stack()
    {
        
    	if (bottom == top)
    	{
        
    		return;
    	}
    	Stack_Node*cur = bottom->next;
    	Stack_Node*next = cur->next;
    
    	while (cur!=NULL)
    	{
        
    		delete(cur);
    		if (next == NULL)
    		{
        
    			break;
    		}
    		cur = next;
    		next = next->next;
    	}
    	top = bottom;
    }
    
    bool MyStack::Stack_Empty()
    {
        
    	return (bottom == top) ? true : false;
    }
    
    int MyStack::Stack_length() {
        
    
    	int num = 0;
    	Stack_Node *cur = bottom;
    
    	while (cur != top) {
        
    		num++;
    		cur = cur->next;
    	}
    	return num;
    }
    
    int MyStack::Top_Stack()
    {
        
    	if (bottom == top)
    		return false;
    	int value = top->data;
    	return value;
    }
    
    bool MyStack::Push_Stack(Stack_DataType &value)
    {
        
    	Stack_Node *temp = new(std::nothrow) Stack_Node(value);
    	if (temp == 0) {
        
    		return false;
    	}
    
    	top->next = temp;
    	top = temp;
    	return true;
    }
    
    bool MyStack::Pop_Stack()
    {
        
    	if (top == bottom)    
    		return false;
    	Stack_Node *prior = bottom;
    	while (prior->next != top) {
            //  找到栈顶第二个元素
    		prior = prior->next;
    	}
    
    	delete(top);
    	top = prior;
    	top->next = NULL;  
    	return true;
    }
    
    bool MyStack::Pop_Stack(Stack_DataType &value)
    {
        
    	if (top == bottom)    
    		return false;
    	Stack_Node *prior = bottom;
    
    	while (prior->next != top) {
            
    		prior = prior->next;
    	}
    	value = top->data;
    	delete(top);
    	top = prior;
    	top->next = NULL;  
    	return true;
    }
    
    void MyStack::Print_Stack()
    {
        
    	Stack_Node *cur = bottom->next;
    
    	while (cur != top) {
        
    		std::cout << cur->data << std::endl;
    		cur = cur->next;
    	}
    
    	std::cout << top->data << std::endl;
    }

*test.cpp*

#include"Sequence_Stack.h"
    #include<iostream>
    
    using namespace std;
    
    int main()
    
    {
        
    	MyStack a(3);
    	a.Print_Stack();		//遍历栈元素
    
    	int b = 10;
    	a.Push_Stack(b);		//插入栈顶元素
    
    	cout << "插入后遍历:" << endl;
    	a.Print_Stack();
    
    	cout << "栈顶元素:" << a.Top_Stack()<<endl;
    	a.Pop_Stack();			//	出栈
    
    	a.Pop_Stack(b);
    
    	cout << "删除后遍历:" << endl;
    	a.Print_Stack();
    
    	cout << "栈的大小:" << a.Stack_length()<<endl;
    	system("pause");
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0NTI4MQ_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0NTI4MQ_size_16_color_FFFFFF_t_70]: /images/20221024/8268b8c21ae145c19d294123095d2ac5.png