1)。#ifndef STACK_H
#define STACK_H
#include <exception>
//当对空栈进行一些不合法的操作的时候会抛出这个异常
class CallEmptyStack: public std::exception
{
public:
virtual const char* what() const
{
return "你要访问的是个空栈";
}
};
//对于栈的设计首先动态分配的资源的第一个位置我没有存储数据,主要是用来判断栈
//是否为空。所以在进行重分配的时候就要注意。当栈进行重新分配的时候将最大值×2
template <typename T>
class Stack
{
public:
Stack(int maxSize = 10);
~Stack();
Stack(const Stack &s);
const Stack<T>& operator = (const Stack &s);
bool empty() const;
int lengh() const;
void push(const T &value);
void pop();
T& top();
private:
T *m_base;
T *m_top; //对于栈中所有的操作都要确保它指向的都是栈顶的数据位置
int m_size;
int m_maxSize;
void newallot();
void copy(const Stack &s);
};
template <typename T>
void Stack<T>::newallot()
{
m_maxSize *= 2;
T *fp = m_base;
T *sp = m_base;
m_base = new T[m_maxSize];
m_top = m_base;
for (int i = 0; i != m_size; ++i)
{
++m_top;
++sp;
*m_top = *sp;
}
delete [] fp;
}
template <typename T>
void Stack<T>::copy(const Stack &s)
{
T *p = s.m_base;
for (int i = 0; i != m_size; ++i)
{
++m_top;
++p;
*m_top = *p;
}
}
template <typename T>
Stack<T>::Stack(int maxSize):m_maxSize(maxSize)
{
m_base = new T[m_maxSize];
m_top = m_base;
m_size = 0;
}
template <typename T>
Stack<T>::~Stack()
{
delete [] m_base;
}
template <typename T>
Stack<T>::Stack(const Stack &s)
{
m_maxSize = s.m_maxSize;
m_size = s.m_size;
m_base = new T[m_maxSize];
m_top = m_base;
copy(s);
}
template <typename T>
const Stack<T>& Stack<T>::operator = (const Stack &s)
{
if (this != &s)
{
delete [] m_base;
m_maxSize = s.m_maxSize;
m_size = s.m_size;
m_base = new T[m_maxSize];
m_top = m_base;
copy(s);
}
return *this;
}
template <typename T>
inline bool Stack<T>::empty() const
{
return m_base == m_top;
}
template <typename T>
inline int Stack<T>::lengh() const
{
return m_size;
}
template <typename T>
void Stack<T>::push(const T &value)
{
if (m_size + 2 <= m_maxSize) //这里之所以要加2是因为我在分配的时候第一个位置
//并没有存数据所以实际分配的是m_maxSize-1个单元
{
++m_top;
*m_top = value;
++m_size;
}
else
{
newallot();
++m_top;
*m_top = value;
++m_size;
}
}
template <typename T>
inline void Stack<T>::pop()
{
if (!empty())
{
--m_size;
--m_top;
}
else
throw CallEmptyStack();
}
template <typename T>
inline T& Stack<T>::top()
{
if (!empty())
return *m_top;
else
throw CallEmptyStack();
}
#endif
2)。#ifndef STACK_H
#define STACK_H
#include <vector>
#include <exception>
using namespace std;
//用vector实现的一个栈,使用已经有的STL实现的时候就是要看看这些操作是否会引发异常
class CallEmptyStack :public exception
{
public:
virtual const char* what() const
{
return "你访问的是一个空栈!";
}
};
template <typename T>
class Stack
{
public:
Stack(){};
~Stack(){};
vector<T>::size_type lengh() const;
bool empty() const;
T& top();
void pop();
void push(const T &value);
private:
vector<T> m_vec;
};
template <typename T>
inline vector<T>::size_type Stack<T>::lengh() const
{
return m_vec.size();
}
template <typename T>
inline bool Stack<T>::empty() const
{
return m_vec.empty();
}
template <typename T>
T& Stack<T>::top()
{
if (!m_vec.empty())
return m_vec.back();
else
throw CallEmptyStack();
}
template <typename T>
void Stack<T>::pop()
{
if (!m_vec.empty())
{
vector<T>::iterator ite = m_vec.end() - 1;
m_vec.erase(ite);
}
else
throw CallEmptyStack();
}
template <typename T>
void Stack<T>::push(const T &value)
{
m_vec.push_back(value);
}
#endif