线性表之stack

父类Stack ADT

template <class T> // 栈的元素类型为 T
class Stack
{
public:						 // 栈的运算集
	void clear();			 // 变为空栈
	bool push(const T item); // item入栈，成功则返回真，否则返回假
	bool pop(T &item);		 // 返回栈顶内容并弹出，成功返回真，否则返回假,
	bool getTop(T &item);	 // 返回栈顶内容但不弹出成功返回真，否则返回假,
	bool isEmpty();			 // 若栈已空返回真
	bool isFull();			 // 若栈已满返回真
};

顺序栈的ADT（Array-based Stack）

template <class T>
class arrStack : public Stack<T>
{
private:	   // 栈的顺序存储
	int mSize; // 栈中最多可存放的元素个数
	T *st;	   // 存放栈元素的数组
	int top;   // 栈顶位置，应小于mSize
public:		   // 栈的运算的顺序实现
	arrStack(int size);
	arrStack();
	~arrStack();
	void clear();
	bool push(const T item);
	bool pop(T *item);
	bool getTop(T *item);
	bool isEmpty();
	bool isFull();
};

链式栈（Linked Stack）

链式栈节点ADT

template <class T>
class Link
{
public:
    T data;     // 用于保存结点元素的内容
    Link *next; // 指向后继结点的指针
    Link(const T info, Link *nextValue);
    Link(Link *nextValue = NULL);
};

链式栈ADT

template <class T>
class lnkStack : public Stack<T>
{
private:          // 栈的链式存储
    Link<T> *top; // 指向栈顶的指针
    int size;     // 存放元素的个数
public:           // 栈运算的链式实现
    lnkStack(int defSize);
    ~lnkStack();
    void clear();
    bool push(const T item);
    bool pop(T *item);
    bool getTop(T *item);
};