栈-顺序栈

SeqStack.h

#ifndef SEQSTACK_H
#define SEQSTACK_H

#include<iostream>
#include<assert.h>
#include"Stack.h"
using namespace std;

const int stackIncrement = 20;
template<typename T>
class SeqStack:public Stack<T>{
public:
    SeqStack(int sz=50);
    ~SeqStack(){delete[]elements;}
    void Push(const T &x);
    bool Pop(T &x);
    bool getTop(T &x) const;
    bool IsEmpty() const{
        return top==-1?true:false;
    }
    bool IsFull() const{
        return top==maxSize-1?true:false;//如果栈顶指针top==maxSize-1说明已满
    }
    int getSize() const{
        return top+1;
    }
    void makeEmpty(){
        top = -1;
    }
    friend ostream& operator<<(ostream& os,SeqStack<T>& s){
        for(int i=0;i<=s.top;++i)
            os << s.elements[i] << " ";
        os << endl;
        return os;
    }

private:
    T *elements;
    int top;//指示最后加入的元素的位置
    int maxSize;
    void overflowProcess();//栈溢出处理
};
#endif // SEQSTACK_H

SeqStack.cpp

#include"SeqStack.h"

template<typename T>
SeqStack<T>::SeqStack(int sz):top(-1),maxSize(sz)
{
    elements = new T[maxSize];
    assert(NULL!=elements);
}

/*
  栈溢出处理
 */
template<typename T>
void SeqStack<T>::overflowProcess()
{
    T *newArray = new T[maxSize+stackIncrement];
    assert(NULL!=newArray);
    for(int i=0;i<=top;++i){//top是从0开始的
        newArray[i] = elements[i];
    }
    maxSize+=stackIncrement;
    delete []elements;
    elements = newArray;
}

template<typename T>
void SeqStack<T>::Push(const T &x)
{
    if(IsFull()){
        overflowProcess();
    }
    top++;
    elements[top]=x;
}

template<typename T>
bool SeqStack<T>::Pop(T &x)
{
    if(not IsEmpty()){
        x = elements[top];
        top--;
        return true;
    }else{
        return false;
    }
}

template<typename T>
bool SeqStack<T>::getTop(T &x) const
{
    if(not IsEmpty()){
        x = elements[top];
        return true;
    }else{
        return false;
    }
}

int main()
{
    SeqStack<int> ss(10);
    for(int i=0;i<10;++i)
        ss.Push(i);
    cout<<ss;
    int num = 0;
    ss.Pop(num);
    cout << ss;
    for(int i=10;i<=20;++i)
        ss.Push(i);
    cout << ss;
}

0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 
0 1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 18 19 20