C++实现栈和队列

栈的实现

#include 
using namespace std;
#include 


template 
class stack
{
private:
	T* p;
	int _size;
	int _capacity;
public:
	stack() :p(NULL), _size(0), _capacity(0) { ; }
	~stack() { delete[]p; _size = 0; _capacity = 0; }
	void Checkcapacity()
	{
		if (_size == _capacity)
		{
			T* newp = new T[_capacity == 0 ? 4 : _capacity * 2];
			for (int i = 0; i < _size; i++)
			{
				newp[i] = p[i];
			}
			delete[]p;
			p = newp;
			_capacity = _capacity == 0 ? 4: _capacity * 2;
		}
	}
	// 入栈
	void push(T val)
	{
		Checkcapacity();
		p[_size++] = val;
	}
	// 获取栈顶元素
	T top()
	{
		assert(_size);
		return p[_size - 1];
	}
	// 出栈
	T pop()
	{
		assert(_size);
		_size--;
		return p[_size];
	}
	// 检测栈是否为空 
	bool empty()
	{
		return _size == 0;
	}
	// 获取栈中有效元素个数
	int size() { return _size; }
	int capacity() { return _capacity; }
};

由于是由C++中的模板实现的所以将函数的实现放在了类的里面，技术有限还请见谅，

队列也是一样。

队列的实现

#include 
using namespace std;
#include 


template 
class Node
{
public:
	T val;
	Node* next;
	Node(T v) :val(v) ,next(NULL){ ; }
};

template 
class queue
{
private:
	Node* head;
	Node* tail;
	int num;
public:
	queue() {
		head = new Node(0);
		tail = head;
		num = 0;
	}
	// 队尾入队列
	void push(T val) {

		Node* newnode = new Node(val);
		// 用来进行判空
		assert(newnode);
		tail->next = newnode;
		tail = newnode;
		num++;
	}
	// 队头出队列 
	T pop()
	{
		assert(num);
		Node* cur = head->next;
		head->next = cur->next;
		T top = cur->val;
		delete cur;
		num--;
		return top;
	}
	// 获取队列头部元素 
	T front()
	{
		assert(num);
		return head->next->val;
	}
	// 获取队列队尾元素 
	T back()
	{
		assert(num);
		return tail->val;
	}
	// 获取队列中有效元素个数 
	int size() { return num; }
	// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
	bool empty()
	{
		return num == 0;
	}

	~queue(){
		Node* cur = head;
		while (cur != NULL)
		{
			head = head->next;
			delete cur;
			cur = head;
		}
		num = 0;
	}
};