C++数据结构：栈
一种线性存储结构，栈中元素遵守“先进后出”原则，限定只在栈顶删除插入操作。
使用标准库的栈时，应包含头文件#Include<stack>，定义如stack<int> mystack;
1、栈的抽象描述
抽象数据类型 stack
{
实例
线性表；一端称为底，另一端称为顶
操作
empty()://栈为空时返回true，否则返回false
size()://返回栈中元素个数
top()://返回栈顶个数
pop()://删除栈顶元素
push(x)://将元素x压如栈顶
};
2、栈的分类
（1）数组描述的栈：以数组为底层数据结构时，常以数组头为栈顶，数组头到数组尾为栈顶生长方向，有时为了关注删除插入操作性能，会以数组尾为栈底。
（2）链表描述的栈：以链表为底层的数据结构时，以链表头为栈顶，便于节点的插入与删除，压栈产生的节点将一直出现在链表的头部。（链表中删除栈顶指针，要先定义一个节点保存栈顶指针，再释放临时节点）
3、主要概念
（1）栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。
（2）压栈：栈的插入操作，叫做进栈，也称压栈、入栈。
（3）弹栈：栈的删除操作，也叫做出栈。
4、栈常用操作
（1）弹栈，通常命名为pop
（2）压栈，通常命名为push
（3）求栈的大小
（4）判断栈是否为空
（5）获取栈顶元素的值
5、标准库的栈使用
5、C++实现数组栈和链表栈：
#include "arrayList.h"
template<class T>
struct chainNode
{
//
T element;
chainNode<T>* next;
//
chainNode(){}
chainNode(const T& element, chainNode<T>* next)
{
this->element = element;
this->next = next;
}
};
template<class T>
class stack
{
public:
virtual ~stack(){}
virtual bool empty() = 0;
virtual int size() const = 0;
virtual T& top() = 0;//返回栈顶元素的引用
virtual void pop() = 0;//删除栈顶元素
virtual void push(const T&) = 0;
};
template<class T>
class derivedArrayStack :private arrayList<T>, public stack<T>
{
public:
derivedArrayStack(int initialCapacity=10)
:arrayList<T>(initialCapacity){}
bool empty() const
{
return arrayList<T>::empty();
}
int size() const
{
return arrayList<T>::size();
}
T& top()
{
try
{
return get(arrayList<T>::size() - 1);
}
catch (illegalIndex)
{
throw stackEmpty();
}
}
void pop()
{
if (arrayList<T>::empty())
throw stackEmpty();
erase(arrayList<T>::size() - 1);
}
void push(const T& theElement)
{
insert(arrayList<T>::size(), theElement);
}
protected:
void stackEmpty();
};
///数组栈///
template<class T>
class arrayStack : public stack<T>
{
public:
arrayStack(int initialCapacity = 10);
~arrayStack(){ delete[] stack; }
//
bool empty()const
{
return stackTop == -1;
}
int size()const
{
return stackTop + 1;
}
T& top()
{
if (stack == -1)
throw stackEmpty();
return stack[stackTop];
}
void pop()
{
if (stackTop == -1)
throw stackEmpty();
stack[stackTop--].~T();
}
void push(const T& theElement)
private:
void stackEmpty();
int stackTop;//当前栈顶
int arrayLength;//栈容量
T* stack;//元素数组
};
///
template<class T>
arrayStack<T>::arrayStack(int initialCapacity)
{
if (initialCapacity < 1)
{
ostringstream s;
s << "initial capacity =" << initialCapacity << "Must be >0";
throw illegalParameterValue(s.str());
}
arrayLength = initialCapacity;
stack = new T[arrayLength];
stackTop = -1;
}
template<class T>
void arrayStack<T>::push(const T& theElement)
{
if (stackTop == arrayLength - 1)
{
changeLengthlD(stack, arrayLength, 2 * arrayLength);
arrayLength *= 2;
}
stack[++stackTop] = theElement;
}
/链表栈///
template<class T>
class linkedStack :public stack<T>
{
public:
linkedStack(int initialCapacity = 10)
{
stackTop = NULL;
stackSize = 0;
}
~linkedStack();
bool empty() const
{
return stackSize == 0;
}
int size()const
{
return stackSize;
}
T& top()
{
if (stackSize == 0)
throw stackEmpty();
return stackTop->element;
}
void push(const T& theElement)
{
stackTop = new chainNode<T>(theElement, stackTop);
stackSize++;
}
void pop();
private:
void stackEmpty();
chainNode<T>* stackTop;//栈顶指针
int stackSize;//栈中元素个数
};
template<class T>
linkedStack<T>::~linkedStack()
{
while (stackTop != NULL)
{
chainNode<T>* nextNode = stackTop->next;
delete stackTop;
stackTop = nextNode;
}
}
template<class T>
void linkedStack<T>::pop()
{
if (stackSize == 0)
throw stackEmpty();
chainNode<T>* nextNode = stackTop->next;
delete stackTop;
stackTop = nextNode;
stackSize--;
}
