c++實現(xiàn)棧的基本操作

1. 棧的定義

       棧（Stack）又稱堆棧，是一種運算受限的線性表，其限制是僅允許在表的一端進行插入和刪除運算。

    棧有兩種實現(xiàn)的方式。一種是順序存儲，和數(shù)組類似；一種是鏈式存儲，和單鏈表類似。

   下面主要用順序存儲去實現(xiàn)它，和鏈式存儲相比，主要有下面幾個優(yōu)點：

    （1）方便我們進行管理；數(shù)組就是只可以在一邊進行操作。

    （2）應用順序存儲的效率比較高。假如用鏈式存儲的話，在插入刪除等操作時，需要遍歷整個鏈表，比較浪費時間；還有一點是CPU的高速緩存的利用率低，每次操作往高級緩存中加載時會多加載一些沒有用的空間，不僅浪費時間，還容易“污染”內(nèi)存。

2.棧的主要的函數(shù)接口

void Push(const T & s);//插入數(shù)據(jù)
void Pop();//刪除數(shù)據(jù)
bool empty();//判斷是否為空
size_t size();//元素個數(shù)
T & Top();//取出最后進入的元素但不刪除
void print();//輸出函數(shù)

3.棧的定義

template <typename T>//定義為模板類，實現(xiàn)不同的數(shù)據(jù)存儲

class Stack
{
    public:
        Stack()//構(gòu)造函數(shù)
		:_ptr(NULL)
		, _top(0)
		,_capacity(0)
	{

	}
	Stack(const Stack<T> & s)//拷貝構(gòu)造
	{
		_capacity = s._capacity;
		_top = s._top;
		_ptr = new T[_capacity];
		for (size_t i = 0; i < _top; i++)//不能使用memcpy函數(shù)，（必須考慮淺拷貝的                                                 //問題）
		{
		    _ptr[i] = s._ptr[i];
		}
	}
	Stack <T> & operator=(const Stack<T> & s)//賦值運算符的重載
	{
		if (_capacity < s._capacity)//判斷容量是否足夠
		{
		    _capacity = s._capacity;
		    _ptr = new T[_capacity];
		}
		_top = s._top;
		for (size_t i = 0; i < _top; i++)
		{
		    _ptr[i] = s._ptr[i];
		}
		return *this;
	}
	~Stack()//析構(gòu)函數(shù)
	{
		if (_ptr)
		{
		    delete _ptr;
		}
	}
    protected:
	T * _ptr;//保存數(shù)據(jù)的指針
	size_t _top;//存儲的數(shù)據(jù)個數(shù)
	size_t _capacity;//開辟的容量
｝

4.接口的實現(xiàn)

	void Push(const T & s)//插入數(shù)據(jù)
	{
		_Check_capacity();//使用這個函數(shù)判斷是否需要開辟空間
		_ptr[_top] = s;
		_top++;
	}
	
	void Pop()//刪除數(shù)據(jù)
	{
		if (_top)//必須保證數(shù)據(jù)個數(shù)不能為負數(shù)
		{
		        _top--;
		}
	}
	
	bool empty()//判空
	{
		return _top==0;
	}
	
	size_t size()//數(shù)據(jù)個數(shù)
	{
		return _top;
	}
	
	T & Top()//輸出最后插入的數(shù)據(jù)
	{
		if (!empty())
		{
			return _ptr[_top-1];
		}
	}
	
	void print()//輸出
	{
		for (size_t i = _top; i > 0; --i)
		{
			cout << _ptr[i-1] << " ";
		}
		cout << endl;
	}

5.測試結(jié)果

void testStack()
{
	Stack<int> s1;
	s1.Push(0);
	s1.Push(1);
	s1.Push(2);
	s1.Push(3);
	s1.print();//輸出結(jié)果3 2 1 0
	s1.Pop();
	s1.print();//輸出結(jié)果2 1 0
	cout << s1.empty() << endl;//輸出結(jié)果0
	cout << s1.size() << endl;//輸出結(jié)果 3
	cout << s1.Top() << endl;//輸出結(jié)果 2
}