C++栈（stack）

向右看齐 2022-08-20 15:11 229阅读 0赞

栈：栈是一种数据结构，存储以及查找数据时只能访问栈的一端。栈后进先出（LIFO, last in first out）

栈的操作包括：

Clear() ——清空栈

IsEmpty()——判断栈是否为空

Push(el)——将元素el放到栈的顶部

Pop——弹出栈顶部的元素

TopEL()——获取栈顶部的元素，但不删除该元素

一、栈的向量实现，直接代码

Stack.h

//Stack.h
    #ifndef STACK_H
    #define STACK_H
    #include <vector>
    using namespace std;
    
    template<class T, int capacity = 30>
    class Stack
    {
    public:
    	Stack();
    
    	void clear();
    
    	bool IsEmpty();
    
    	T& TopEL();
    
    	T Pop();
    
    	void Push(const T& el);
    
    private:
    	vector<T> pool;
    };
    #endif

Stack.cpp

//Stack.cpp
    #include "Stack.h"
    
    template<class T, int capacity>
    Stack<T, capacity>::Stack()
    {
    	pool.reserve(capacity);
    }
    
    template<class T, int capacity>
    void Stack<T, capacity>::clear()
    {
    	pool.clear();
    }
    
    template<class T, int capacity>
    bool Stack<T, capacity>::IsEmpty()
    {
    	return pool.empty();
    }
    
    template<class T, int capacity>
    T& Stack<T, capacity>::TopEL()
    {
    	return pool.back();
    }
    
    template<class T, int capacity>
    T Stack<T, capacity>::Pop()
    {
    	T el = pool.back();
    	pool.pop_back();
    	return el;
    }
    
    template<class T, int capacity>
    void Stack<T, capacity>::Push(const T& el)
    {
    	pool.push_back(el);
    }

//main

//MainProcess.cpp
    #include "Stack.cpp"
    #include <iostream>
    using namespace std;
    
    
    void Print(Stack<int> tempstack)	//仅用于测试用
    {
    	while (!tempstack.IsEmpty())
    	{
    		cout << tempstack.Pop() << " ";
    	}
    	cout << endl;
    }
    
    int main()
    {
    	Stack<int> tempstack;
     	tempstack.Push(1);
     	tempstack.Push(2);
     	tempstack.Push(3);
    
    	cout << tempstack.TopEL() << endl;
    	Print(tempstack);
    
    	return 0;
    }

备注：MainProcess.cpp头文件包含的是Stack.cpp而不是Stack.h，因为模板类不能分开编译。可以参考下面链接

[http://blog.csdn.net/bichenggui/article/details/4207084][http_blog.csdn.net_bichenggui_article_details_4207084]

[http://www.cnblogs.com/lscheng/archive/2011/10/18/2216569.html][http_blog.csdn.net_bichenggui_article_details_4207084]

二、栈的链表实现

代码

LLStack.h

//LLStack.h
    #ifndef LLSTACK_H
    #define LLSTACK_H
    #include <list>
    using namespace std;
    
    template<class T>
    class LLStack
    {
    public:
    	LLStack() = default;
    
    	void Clear();
    
    	bool IsEmpty();
    
    	T TopEl();
    
    	T Pop();
    
    	void Push(const T& el);
    
    private:
    	list<T> lst;
    };
    #endif

LLStack.cpp

#include "LLStack.h"
    template<class T>
    void LLStack<T>::Clear()
    {
    	lst.clear();
    }
    
    template<class T>
    bool LLStack<T>::IsEmpty()
    {
    	return lst.empty();
    }
    //LLStack.cpp
    template<class T>
    T LLStack<T>::TopEl()
    {
    	return lst.back();
    }
    
    template<class T>
    T LLStack<T>::Pop()
    {
    	T el = lst.back();
    	lst.pop_back();
    	return el;
    }
    
    template<class T>
    void LLStack<T>::Push(const T& el)
    {
    	lst.push_back(el);
    }

MainProcess.cpp

//栈的链表实现
    //MainProcess.cpp
    #include <iostream>
    #include "LLStack.cpp"
    using namespace std;
    
    template<class T>
    void Print(LLStack<T> lls)
    {
    	while (!lls.IsEmpty())
    	{
    		cout << lls.Pop() << " ";
    	}
    
    	cout << endl;
    }
    
    int main()
    {
    	LLStack<int> lls;
    	lls.Push(1);
    	lls.Push(2);
    	lls.Push(3);
    	lls.Push(4);
    
    	Print(lls);
    
    
    	return 0;
    }

[http_blog.csdn.net_bichenggui_article_details_4207084]: http://blog.csdn.net/bichenggui/article/details/4207084