[C++]数据结构：栈之顺序栈

顺序栈

/*
 * Sequence Stack 顺序栈
 */
#include<stdio.h>
#include<iostream>
using namespace std;

#include"base.h" // 引入 基本数据类型 以及 表函数处理结果的状态码结构体 Status
#include<string> // main函数中需要测试调用 (string类)
#define MAXSIZE_STACK 100 //栈内最大元素数
typedef struct {
    DataType *base; // 栈底指针 (NULL:栈结构不存在； 初始化后，始终指向栈底)
    DataType *top;  //栈顶指针 （初始时：top==base; top所指处无任何元素）
    int stackSize;  //栈可用的最大容量
}SeqStack;

Status InitStack(SeqStack &S){
    S.base = new DataType [MAXSIZE_STACK];
    if(S.base==NULL){
        exit(OVERFLOW);
    }
    S.top = S.base;
    S.stackSize = MAXSIZE_STACK; // 设置栈的可用最大容量
    return OK;
}

Status Push(SeqStack &S, DataType e){//入栈
    if(S.top - S.base == S.stackSize){ // 栈满
        return ERROR;
    }
    *S.top = e;
    S.top++;
    return OK;
}

Status Pop(SeqStack &S, DataType &e){//出栈
    if(S.top==S.base){//栈空
        return ERROR;
    }
    S.top--;
    e = *(S.top-1); //返回栈顶元素的值 【易错】top所指处系栈顶元素的后一位，而非直接指向栈顶元素
    return OK;
}

Status GetTop(SeqStack S, DataType &e){//取栈顶元素
    if(S.top==S.base){//栈空
        return ERROR;
    }
    e = *(S.top-1); //【易错】
    return OK;
}

Status StackTraverse(SeqStack S){//遍历
    if(S.base == NULL){ // 栈结构不存在
        return ERROR;
    }
    if(S.base == S.top){//栈空
        return ERROR;
    }
    DataType *p = S.top;
    while(p!=S.base){
        cout<<p<<"\t";
        p--;
    }
    cout<<p<<endl;
    return OK;
}

bool StackEmpty(SeqStack S){ // 栈空?
    if(S.base==S.top){ // 栈空
        return true;
    }
    return false; //栈不为空
}

bool StackFull(SeqStack S){ //栈满?
    if(S.top-S.base == S.stackSize){
        return true;//栈满
    }
    return false; //栈未满
}

int main(){
    SeqStack S;
    InitStack(S);
    string instruction="-"; // string 在 cmd | 标准I/O 模式中输入时，将会以空格隔断字符串
    DataType data;
    cout<<"Please Input Your Instructions:"<<endl;
    cout<"Format: \n1.\"#\":Stop Execute.\n2.\"PUSH\" 'H':Push a element 'H'. 3.\"POP\" 'T':Pop a element 'T'.\n";
    while(instruction!= "#"){
        cout<<"[INSTRUCTION]";
        cin>>instruction;
        if(instruction=="PUSH"){
            Push(S, data);
            if(!StackFull(S)){
                cout<<"[PUSH DATA]";
                cin>>data;
            } else {
                cout<<"<ERROR: Stack is full!So, it doesn't allow 'PUSH' operation!>"<<endl;
            }
        } else if(instruction=="POP"){
            Status status = Pop(S, data);
            if(status==OK){
                cout<<"[POP DATA]"<<data<<endl;
            } else {
                cout<<"<ERROR: 'POP' operation handle error!>"<<endl;
            }
        } else {
            cout<<"<ERROR: INSTRUCTION is error!)>"<<endl;
        }
    }
    StackTraverse(S);
    return 0;
}

参考文献

• 《数据结构(C语言版/ 严蔚敏 李冬梅 吴伟民 编)》