C++模板类实现栈、队列

​ 准备复习一下C++模板的知识，先手写一个栈和队列来熟悉一下。

栈

栈类的声明：

template <typename T>
class Stack{
private:
	T *data;
	int top;  //栈顶指针
	int maxsize; //最大可容纳的元素个数 
public:
	Stack(int size=100);
	~Stack();
	void Push(const T x); //新元素进栈
	bool Pop();  //栈顶出栈
	T getTop() const;
	bool isEmpty() const;
	int getSize() const;
};

函数实现代码：

const int stackIncreament = 100;

template <typename T>
Stack<T>::Stack(int size):top(-1),maxsize(size){
	data = new T[size];
	if (data==NULL){
		cerr << "存储空间分配失败！" << endl;
		exit(1);
	}
}

template <typename T>
Stack<T>::~Stack(){
	delete []data;
}

template <typename T>
void Stack<T>::Push(const T x){
	if (top==maxsize-1){
		T* newArray = new T[maxsize+stackIncreament];
		if (newArray == NULL){
			cerr << "存储空间分配失败！" << endl;
			exit(1);
		}
		for (int i=0; i<=top; i++)
			newArray[i] = data[i];
		maxsize += stackIncreament;
		delete []data;
		data = newArray;
	}
	
	data[++top] = x;
}

template <typename T>
bool Stack<T>::Pop(){
	if (isEmpty()) return false;
	top--;
	return true;
}

template <typename T>
T Stack<T>::getTop()const{
	if (isEmpty()) {
		cerr << "Error, stack is empty!" << endl;
		return T();
	}
	return data[top];
} 

template <typename T>
bool Stack<T>::isEmpty()const{
	if (top==-1) return true;
	else return false;
}

template <typename T>
int Stack<T>::getSize()const{
	return top+1;
}

主函数测试：

int main(){
	Stack<int> s(10);
	for (int i=0; i<20; i++)
		s.Push(i);
	while (!s.isEmpty()){
		cout << s.getTop() << " ";
		s.Pop();
	}
	cout << endl;
	return 0;
}

队列

节点声明：

template<typename T>
struct Node{
    T val;
    Node* next;
};

队列类的声明：

template<typename T>
class Queue{
private:
    int cnt;
    Node<T>* front;
    Node<T>* rear;
public:
    Queue();
    ~Queue();
    void EnQueue(T num);
    void DeQueue();
    int size() const{return cnt;}
    bool isEmpty() const{return cnt==0?true:false;}
    T getHead() const;
};

函数实现：

template<typename T>
Queue<T>::Queue():cnt(0){
    front = new Node<T>;
    if (!front){
        cerr << "空间分配error" << endl;
        exit(1);
    }
    front->next = NULL;
    rear = front;
}

template<typename T>
Queue<T>::~Queue(){
    while (front){
        rear = front->next;
        delete front;
        front = rear;
    }
    front = NULL;
    rear = NULL;
}

template<typename T>
void Queue<T>::EnQueue(T num){
    Node<T>* anode = new Node<T>;
    anode->val = num;
    anode->next = NULL;
    rear->next = anode;
    rear = rear->next;
    cnt++;
}

template<typename T>
void Queue<T>::DeQueue(){
    if (front==rear){
        cerr << "The queue is empty!" << endl;
        return;
    }
    Node<T>* temp = front->next;
    front->next = front->next->next;
    if (temp==rear){
        rear = front;
    }
    cnt--;
    delete temp;
}

template<typename T>
T Queue<T>::getHead() const{
    if (front==rear){
        cerr << "queue is empty!" << endl;
        return T();
    }
    return front->next->val;
}

主函数测试：

int main(){
    Queue<int> q;
    for (int i=0; i<10; i++){
        q.EnQueue(i);
    }
    while (!q.isEmpty()){
        cout << q.getHead() << " ";
        q.DeQueue();
    }
    return 0;
}