數據結構之通過類模板實現棧，數據結構類模板

數據結構之通過類模板實現棧，數據結構類模板

　　閒來無事,寫了一段通過類模板實現一個簡單棧的代碼,分享給大家.....

　　(關於棧的更多的詳細信息,詳見:http://www.cplusplus.com/reference/stack/stack/?kw=stack)

棧的聲明及實現

//Stack.h
//代碼量太少,就不分文件實現了
//溫馨提示:模板程序分文件時,請將頭文件後綴名修改為.hpp
#ifndef __STACK_H__
#define __STACK_H__
template<typename T>
class Stack{
public:
	//構造函數
	Stack()
	:_pBase(NULL)
	,_uSize(0)
	,_uCapacity(0){}
	//析構函數
	~Stack(){
		if(_pBase!=NULL){
			delete[] _pBase;
			_pBase = NULL;
		}
		_uSize = 0;
		_uCapacity = 0;
	}
public:
	//判斷是否為空
	bool Empty(){
		return _uSize==0;
	}

	//獲取棧內有效元素個數
	size_t Size(){
		return _uSize;
	}

	//獲取棧頂元素
	T &Top(){
		return _pBase[_uSize-1];
	}
	//獲取棧頂元素const版本
	const T &Top()const{
		return _pBase[_uSize-1];
	}

	//入棧
	void Push(const T &x){
		_CheckCapacity();		//檢測是否需要進行擴容操作,並進行擴容
		_pBase[_uSize++] = x;	//插入數據、有效元素個數自增
	}

	//出棧
	void Pop(){
		if(!Empty()){	//棧非空
			_uSize--;	//有效元素自減
		}
	}
private:
	//檢測是否擴容
	void _CheckCapacity(){
		if( _uSize>=_uCapacity ){
			size_t NewCapacity = _uCapacity*2+10;	//擴容後容量
			T * NewBase = new T[NewCapacity];		//新空間
			if(_pBase!=NULL){						//不是空棧
				for(size_t i=0; i<_uSize; ++i){		//拷貝數據
					NewBase[i] = _pBase[i];
				}
				delete[] _pBase;		//釋放原有空間
			}
			_pBase = NewBase;			//更新棧的數據指針
			_uCapacity = NewCapacity;	//更新棧的容量
		}
	}
private:
	T * _pBase;			//基址
	size_t _uSize;		//有效元素
	size_t _uCapacity;	//大小
};
#endif

測試代碼

#include<iostream>
#include"Stack.h"
//測試函數,測試基本接口
void StackTest(){
	Stack<int> s1;
	s1.Pop();		//測試對空棧進行Pop
	s1.Push(1);		//第一次擴容
	s1.Pop();
	s1.Push(1);
	s1.Push(2);
	s1.Push(3);
	s1.Push(4);
	s1.Push(5);
	s1.Push(6);
	s1.Push(7);
	s1.Push(8);
	s1.Push(9);
	s1.Push(10);
	std::cout<<"目前棧內有 "<<s1.Size()<<" 個元素"<<std::endl;
	s1.Push(11);	//第二次擴容
	std::cout<<"棧頂元素為:"<<s1.Top()<<std::endl;
	s1.Top() = 20;
	std::cout<<"修改後:"<<s1.Top()<<std::endl;
}
int main(){
	StackTest();
	return 0;
}

總結:

　　以上代碼,僅供個人娛樂.

　　在STL中的棧(stack)和隊列(queue)的模板參數列表裡除了類型(T)以外還有一個容器(Container).

　　棧(stack)和隊列(queue)在這裡都默認使用了雙向隊列(deque)作為容器(Container).

　　關於雙向隊列的更多詳細信息詳見:http://www.cplusplus.com/reference/deque/deque/