顺序栈-链式栈的实现

「爱情、让人受尽委屈。」 2024-04-06 13:57 84阅读 0赞

/*
    * 顺序栈的实现
    */
    #include<iostream>
    using namespace std;
    
    const int Maxsize = 10;
    //template<class T>
    //struct Node {
    //	T data[Maxsize];
    //	Node<T>* next;
    //};
    
    template<class T>
    class SeqStack {
    private:
    	T date[Maxsize];
    	int top;
    public:
    	SeqStack();
    	~SeqStack();
    	void Push(T x);
    	T Pop();
    	T GetTop();
    	int empty();
    };
    //初始化栈
    template<class T>
    SeqStack<T>::SeqStack() {
    	top = -1;
    }
    
    template<class T>
    SeqStack<T>::~SeqStack() {}
    
    //判断栈是否为空
    template<class T>
    int SeqStack<T>:: empty() {
    	if (top == -1)
    		throw"空栈！";
    		return 1;
    }
    
    //入栈
    template<class T>
    void SeqStack<T>::Push(T x) {
    	if (top == Maxsize - 1)
    		throw"上溢！";
    		top+=1;
    		data[top] = x;
    		/*data[++top] = x;*/
    }
    
    //出栈
    template<class T>
    T SeqStack<T>::Pop() {
    	T x;
    	if (top == -1)
    		throw"下溢！";
    	//x = data[top--];
    	return x;
    }
    
    //取栈顶元素
    template<class T>
    T SeqStack<T>::GetTop() {
    	return data[top];
    }
    
    int mian()
    {
    	int x;
    	SeqStack<int> s;
    	cout << "对15和20进行入栈操作：" << endl;
    	s.Push(15);
    	cout << "当前的栈顶元素为：" << s.GetTop() << endl;
    	s.Push(20);
    	cout << "当前的栈顶元素为：" << s.GetTop()<< endl;
    
    	try {
    		x=s.Pop();
    		cout << "执行一次出栈，删除元素：" << x << endl;
    
    	}
    	catch (char* str) { cout << str << endl; }
    
    	try {
    		cout << "请输入一个要入栈的数：";
    		cin >> x;
    		s.Push(x);
    		cout << "执行一次入栈，栈顶元素：" << s.GetTop()<< endl;
    	}
    	catch (char* str) { cout << str << endl; }
    	return 0;
    }

> 链式栈

#include<iostream>
    using namespace std;
    struct Node {
    	int data;
    	Node* next;
    };
    class LinkStack {
    private:
    	Node* top;
    public:
    	LinkStack();
    	~LinkStack();
    	void Push(int x);
    	int Pop();
    	int  GetTop();
    	int Empty();
    };
    LinkStack::LinkStack() {
    	top = new Node;
    	top->next = nullptr;
    }
    LinkStack::~LinkStack() {
    	Node* p = top;
    	while (top != nullptr) {
    		top = top->next;
    		delete p;
    		p = top;
    	}
    }
    void LinkStack::Push(int x) {
    	Node* s = nullptr;
    	s = new Node;
    	s->data = x;
    	s->next = top;
    	top = s;//将结点s插在栈顶
    }
    int LinkStack::Pop() {
    	Node* p = nullptr;
    	int x;
    	if (top == nullptr) {
    		cout << "下溢！" << endl;
    		return 0;
    	}
    	x = top->data; p = top;
    	top = top->next;//将栈顶结点摘链
    	delete p;
    	return x;
    }
    int LinkStack::GetTop() {
    	return top->data;
    }
    int LinkStack::Empty() {
    	if (top == nullptr) {
    		return 0;
    	}
    }
    int mian() {
    	int x;
    	LinkStack s{};
    	cout << "入栈：" << endl;
    	s.Push(20);
    	s.GetTop();
    	try {
    		x = s.Pop();
    		cout << "出栈一个元素：" << x;
    		cout << endl;
    	}
    	catch (char* str) { cout << str; }
    	try {
    		cout << "请输入插入的元素：";
    		cin >> x;
    		s.Push(x);
    	}
    	catch (char* str) { cout << str; }
    	if (s.Empty() == 0) {
    		cout << "空栈！" << endl;
    	}
    	else {
    		cout << "非空！" << endl;
    	}
    	return 0;
    }