顺序栈的实现

编程技术  /  houtizong 发布于 3年前   51

#include <iostream>#include <stdlib.h>#define INIT_SIZE 3#define INCREASE_SIZE 1using namespace std;typedef int Elemtype;typedef struct {    Elemtype *base;    Elemtype *top;    int iStackSize;} myStack;//函数声明void initStack(myStack &);void showStack(myStack &);void push(myStack & , Elemtype);void addStackValues(myStack & , int);Elemtype getTopValue(myStack &);Elemtype pop(myStack &);Elemtype searchStack(myStack & , int);int main(){    //初始化一个空的栈空间    myStack ms;    initStack(ms);    //给栈空间添加元素    int iAddCount;    cout << "输入要添加的元素个数：" << endl;    cin >> iAddCount;    cout << "输入要添加元素的值：" << endl;    addStackValues(ms , iAddCount);    //输出栈空间里面的元素值    cout << "栈里面的元素值为：" << endl;    showStack(ms);    //删除栈顶元素    Elemtype ePop = pop(ms);    cout << "删除值为：" << ePop << endl;    cout << "删除后，栈空间的元素值为：" << endl;    showStack(ms);    //获取栈顶元素    cout << "栈顶元素值为：" << getTopValue(ms) << endl;    //向栈空间中添加元素    cout << "输入要添加的元素：" << endl;    Elemtype eInput;    cin >> eInput;    push(ms , eInput);    cout << "添加后元栈空间元素值为：" << endl;    showStack(ms);    //查找栈空间元素    int iSearchIndex;    cout << "输入要查找元素的地址值：" << endl;    cin >> iSearchIndex;    Elemtype eSearchResult = searchStack(ms , iSearchIndex);    cout << "第" << iSearchIndex << "位的元素为：" << eSearchResult << endl;    return 0;}//显示栈里面所有元素void showStack(myStack &ms) {    Elemtype *curr = ms.top;    while(curr > ms.base) {        curr--;        cout << *(curr) << " ";    }    cout << endl;}//初始化栈空间void initStack(myStack &ms) {    ms.base = (Elemtype *)malloc(INIT_SIZE * sizeof(Elemtype));    ms.top = ms.base;    ms.iStackSize = INIT_SIZE;}//给栈空间加入元素值void addStackValues(myStack &ms , int times) {    Elemtype value;    for(int i = 0; i < times; i++) {        cin >> value;        push(ms , value);    }}//向栈空间中添加一个元素值void push(myStack &ms , Elemtype elem) {    //length记住元素的个数，判断栈空间的内存是否已满，若已满则再开辟空间    int length = ms.top - ms.base;    if(length >= ms.iStackSize) {        ms.base = (Elemtype *)realloc(ms.base , (ms.iStackSize + INCREASE_SIZE) * sizeof(Elemtype));        if(!ms.base) {            cout << "元素添加失败！" << endl;        }        ms.top = ms.base + length;        ms.iStackSize = ms.iStackSize + INCREASE_SIZE;    }    //将元素加入栈空间    *(ms.top) = elem;    ms.top++;}//获得栈顶元素Elemtype getTopValue(myStack &ms) {    return *(ms.top - 1);}//移除栈顶元素Elemtype pop(myStack &ms) {    //判断栈是否为空    if(ms.top == ms.base) {        cout << "栈空间没有元素存在！" << endl;        return -1;    }    //移除栈顶元素，并把栈顶元素做返回值返回    ms.top--;    return *(ms.top);}//查找相应位置的元素值Elemtype searchStack(myStack &ms , int index) {    Elemtype *curr = ms.top;    if(index > ms.top - ms.base) {        cout << "查找的元素不存在！" << endl;    }    //移动到相应的元素位置    for(int i = 0; i < index; i++) {        curr--;    }    return *(curr);}