栈(Stack) -- C++ 实现


实现了大小自适应的stack

实现代码

// Stack.h
#ifndef STACK_H
#define STACK_H

#include<iostream>
using namespace std;

namespace jay{
	template<typename T>
	class Stack
	{
	public:
		Stack(int maxsize = 100);
		Stack(const Stack<T>& rhs);
		Stack<T>& operator=(const Stack<T>& rhs);
		~Stack();

		void Push(const T& data);
		void Pop();

		T& Top();
		T  Top() const;

		bool IsEmpty() const;
		int Size() const;
	private:
		// 存放T的内存区域
		T *m_array;
		// 首元素
		int m_nFront;
		// 最后一个入队列的元素[的下一个内存地址]
		int m_nLast;
		// 当前队列的大小[动态变化]
		int m_ncapacity;
	};

	template<typename T>
	Stack<T>::Stack(int nMaxsize) :
	m_nFront(0), m_nLast(0),m_ncapacity(nMaxsize)
	{
		m_array = NULL;
		m_array = new T[nMaxsize+1];

		if (m_array == NULL)
		{
			throw "Failed to allocate memory!";
		}
	}

	template<typename T>
	Stack<T>::Stack(const Stack<T>& rhs) :
	m_nFront(rhs.m_nFront), m_nLast(rhs.m_nLast),m_ncapacity(rhs.m_ncapacity)
	{
		m_array = new T[m_ncapacity+1];
		if (m_array == NULL)
		{
			throw "Failed to allocate memory!";
		}
		for (int i = 0; i <= rhs.m_nLast; i++)
			m_array[i] = rhs.m_array[i];
	}

	template<typename T>
	Stack<T>& Stack<T>::operator=(const Stack<T>& rhs)
	{
		if (this != &rhs)
		{
			delete[] m_array;
			m_ncapacity = rhs.m_ncapacity;
			m_nFront = rhs.m_nFront;
			m_nLast = rhs.m_nLast;
			m_array = new T[m_ncapacity+1];
			for (int i = 0;i <= rhs.m_nLast; i++)
				m_array[i] = rhs.m_array[i];
		}

		return *this;
	}

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

	template<typename T>
	bool Stack<T>::IsEmpty() const
	{
		return 0 == m_nLast;
	}

	template<typename T>
	int Stack<T>::Size() const
	{
		return m_nLast;
	}

	template<typename T>
	void Stack<T>::Push(const T& data)
	{
		// 当队列Size大于m_ncapacity的1/2时 队列 m_ncapacity = m_ncapacity *2
		if (m_nLast <= m_ncapacity /2)
		{
			m_array[m_nLast] = data;
			m_nLast = m_nLast + 1;

		}
		else
		{
			T *arraybuf=new T[ 2*m_ncapacity ];
			for (int i = 0; i < m_nLast; i++)
			{
				arraybuf[i] = m_array[i];
			}
			delete [] m_array;
			m_array = arraybuf;
			m_nFront = 0;

			
			m_array[m_nLast] = data;
			m_nLast = m_nLast + 1;

			m_ncapacity = 2*m_ncapacity;
		}
	}

	template<typename T>
	void Stack<T>::Pop()
	{
		if (!IsEmpty())
		{
			m_nLast = m_nLast - 1;

			if (m_ncapacity > 1024)
			{
				// 当队列Size小于m_ncapacity的1/4时 队列m_ncapacity = m_ncapacity/2
				if (m_nLast <= m_ncapacity /4)
				{
					T *arraybuf=new T[ m_ncapacity/2];
					for (int i = 0; i < m_nLast; i++)
					{
						arraybuf[i] = m_array[i];
					}
					delete [] m_array;
					m_array = arraybuf;

					m_ncapacity = m_ncapacity/2;
				}
			}

		}
		else
		{
			throw "empty Stack";
		}
	}

	template<typename T>
	T& Stack<T>::Top()
	{
		if (IsEmpty())
			throw "empty Stack";

		return m_array[m_nLast-1];
	}

	template<typename T>
	T Stack<T>::Top() const
	{
		if (IsEmpty())
			throw "empty Stack";

		return m_array[m_nLast-1];
	}

};

#endif

测试代码

//main.cpp
#include "Stack.h"

using namespace jay;

int main(int argc, char* argv[])
{
	Stack<int> mystack; 

	int nSize;
	cout << "请输入栈的大小:";
	cin >> nSize;

	cout << "入栈顺序:";
	for (int i=0; i<nSize; i++)
	{
		mystack.Push(i + 1);
		cout << i + 1 << " ";
	}

	cout << endl;

	cout << "当前栈的大小:";
	cout << mystack.Size() << endl;
	cout << "出栈顺序: ";

	while (!mystack.IsEmpty())
	{
		cout << mystack.Top() << " ";
		mystack.Pop();
	}

	cout << endl;

	return 0;
}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。