數據結構-棧的一些基礎操作c++代碼

數據結構-棧的一些基礎操作c++代碼

template 
struct SLNode
{
	T data;                     //數據域
	SLNode *next;            //指針域

	SLNode(SLNode *nextNode = NULL)                      //構造函數
	{
		next = nextNode;
	}
	
	SLNode(const T &item, SLNode *nextNode = NULL)      //構造函數
	{
		data = item;
		next = nextNode;
	}
};

//順序棧
template 
class AStack
{
	public:
		AStack(int MaxStackSize)                              //構造函數
		{
			size = MaxStackSize;
			stackArray = new T[MaxStackSize];
			top = -1;
		}

		~AStack()                              //析構函數
		{
			delete []stackArray;
		}

		bool Push(const T &item)              //向棧頂壓入一個元素
		{
			if (IsFull())
			{
				cout << "Pushing into a full stack!" << endl;
				return false;
			}
			stackArray[++top] = item;
			return true;
		}

		bool Pop(T &item)                     //從棧頂彈出一個元素
		{
			if (IsEmpty())
			{
				cout << "Poping from an empty stack!" << endl;
				return false;
			}
			item = stackArray[top--];
			return true;
		}

		bool Peek(T &item) const              //存取棧頂元素
		{
			if (IsEmpty())
			{
				cout << "Peeking from an empty stack!" << endl;
				return false;
			}
			item = stackArray[top];
			return true;
		}

		int IsEmpty() const                    //檢測棧是否為空
		{
			return top == -1;
		}

		int IsFull() const                     //檢測是否滿棧
		{
			return top == size-1;
		}

		void clear()                           //清空棧
		{
			top = -1;
		}

	private:
		int size;                              //數組的規模
		T *stackArray;                         //存放堆棧元素的數組
		int top;                               //棧頂所在數組元素的下標
};

//鏈式棧類LStack的定義和實現
template 
class LStack
{
	public:
		LStack()                             //構造函數
		{
			top = NULL;
		}

		~LStack()                           //析構函數
		{
			clear();
		}
		
		void clear()                       //清空棧
		{
			SLNode *temp;
			while(!IsEmpty())
			{
				temp = top->next;
				delete top;
				top = temp;
			}
		}

		bool Push(const T &item)          //向棧頂壓入一個元素
		{
			top = new SLNode(item, top);
			return true;
		}

		bool Pop(T &item)                 //從棧頂彈出一個元素
		{
			if(IsEmpty())
			{
				cout << "Poping from an empty stack!" << endl;
				return false;
			}
			item = top->data;
			SLNode *temp = top;
			top = top->next;

		}

		bool Peek(T &item) const         //讀取棧頂元素
		{
			if(IsEmpty())
			{
				cout << "Poping from an empty stack!" << endl;
				return false;
			}
			item = top->data;
			return true;
		}

		int IsEmpty() const
		{
			return top == NULL;
		}
	private:
		SLNode *top;
		
};