/*

堆栈本身就是一种线性数据结构，说白了他与容器线性表是一种数据类型，不要认为他多高大上。

实时上他还没有线性表复杂，下面简单的实现一下堆栈。

事实上整个核心操作都是在操作指向堆栈的顶部元素的指针

*/

template <class T>
class BaseStack {
　　//出栈
　　virtual bool pop()  = 0;
　　//进栈
　　virtual bool push(T x) = 0;
　　//获取栈顶元素
　　virtual T top() const = 0;
　　//清空堆栈
　　virtual void clear() = 0;
};
template <class T>
class SeqStack :public BaseStack<T> {

public:
　　int _maxSize,_index;//确定容量，确定头部指针索引
　　T *_stack;
　　SeqStack(int maxSize) {
　　　　_maxSize = maxSize;
　　　　_index = -1;
　　　　_stack = new T(maxSize-1);
　　}
　　void clear() {
　　　　_index = -1;
　　}
　　T top() {
　　　　return _stack[_index];
　　}
　　bool push(T x) {
　　　　if (isFull()) {
　　　　　　printf("over flow");
　　　　　　return false;
　　　　}
　　　　else {
　　　　　　_index++;//让栈顶索引向上移动一个元素
　　　　　　_stack[_index] = x;
　　　　return true;
　　　　}
　　}
　　bool pop() {
　　　　if (isEmpty()) {
　　　　　　return false;
　　　　}
　　　　_index--;//让栈顶索引向下移动一个元素
　　　　return true;
　　}
　　// judge is the queue full?
　　bool isFull() {
　　　　if (_index < _maxSize) {
　　　　　　return false;
　　　　}
　　　　else {
　　　　　　return true;
　　　　}
　　}
　　//judge is the queue empty?
　　bool isEmpty() {
　　　　if (_index == -1) {
　　　　　　return true;
　　　　}
　　　　else {
　　　　　　return false;
　　　　}
　　}
};

int main()
{

　　SeqStack<int > *test = new SeqStack<int>(8);
　　test->push(1);
　　printf("%d",test->top());
　　while (1);
　　return 0;
}

数据结构之堆栈C++版