链栈的实现

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

#include <iostream>#include <stdlib.h>using namespace std;typedef int Elemtype;typedef struct Node {    Node *lNext;    Elemtype eData;} *LinkedStack;//函数声明LinkedStack initNode();void showStack(LinkedStack);void initStack(LinkedStack , int);int stackLength(LinkedStack);bool isEmptyStack(LinkedStack);Elemtype getTop(LinkedStack);void push(LinkedStack , Elemtype);Elemtype pop(LinkedStack);void clearStack(LinkedStack);int main(){    LinkedStack ls = initNode();    cout << "输入要初始化栈空间的元素个数：" << endl;    int iSize;    cin >> iSize;    cout << "输入各个元素值：" << endl;    initStack(ls , iSize);    cout << "栈内元素有：" << endl;    showStack(ls);    //测试求栈空间元素个数函数    //cout << "栈空间元素个数为：" << stackLength(ls) << endl;    //判断栈空间是否为空    /*bool bEmpty = isEmptyStack(ls);    if(bEmpty) {        cout << "栈空间里面没有任何元素！" << endl;    } else {        cout << "栈非空！" << endl;    }*/    //测试获取栈顶元素    /*Elemtype eReturn = getTop(ls);    cout << "栈顶元素为：" << eReturn << endl;*/    //测试入栈函数    /*Elemtype eValue;    cout << "输入要入栈的元素值：" << endl;    cin >> eValue;    push(ls , eValue);    cout << "入栈后，栈空间元素值为：" << endl;    showStack(ls);*/    //测试出栈函数    Elemtype eDelete = pop(ls);    cout << "被删除元素为：" << eDelete << endl;    cout << "栈空间剩余元素：" << endl;    showStack(ls);    //测试置空栈    cout << "置空栈……" << endl;    clearStack(ls);    showStack(ls);    return 0;}//初始化结点LinkedStack initNode() {    LinkedStack lReturn = (LinkedStack)malloc(sizeof(Node));    lReturn->lNext = NULL;    return lReturn;}//初始化栈void initStack(LinkedStack lHead , int iSize) {    if(lHead->lNext != NULL) {        lHead->lNext = NULL;    }    for(int i = 0; i < iSize; i++) {        Elemtype eValue;        cin >> eValue;        push(lHead , eValue);    }}//求栈空间元素个数int stackLength(LinkedStack lHead) {    int length = 0;    while(lHead->lNext != NULL) {        length++;        lHead = lHead->lNext;    }    return length;}//显示栈空间所有值void showStack(LinkedStack lHead) {    if(isEmptyStack(lHead)) {        cout << "栈空间里面没有元素！" << endl;        return;    }    lHead = lHead->lNext;    while(lHead != NULL) {        cout << lHead->eData << "  ";        lHead = lHead->lNext;    }    cout << endl;}//判断栈空间是否为空bool isEmptyStack(LinkedStack lHead) {    if(lHead->lNext == NULL) {        return true;    }    return false;}//读取栈顶元素Elemtype getTop(LinkedStack lHead) {    if(isEmptyStack(lHead)) {        cout << "栈空间没有任何元素！" << endl;        return -1;    }    return lHead->lNext->eData;}//入栈void push(LinkedStack lHead , Elemtype eValue) {    LinkedStack lNew = initNode();    lNew->eData = eValue;    lNew->lNext = lHead->lNext;    lHead->lNext = lNew;}//出栈Elemtype pop(LinkedStack lHead) {    if(isEmptyStack(lHead)) {        cout << "栈空间没有任何元素！" << endl;        return -1;    }    LinkedStack lDelete = lHead->lNext;    lHead->lNext = lDelete->lNext;    Elemtype eReturn = lDelete->eData;    free(lDelete);    return eReturn;}//置空栈void clearStack(LinkedStack lHead) {    if(isEmptyStack(lHead)) {        return;    }    while(!isEmptyStack(lHead)) {        LinkedStack lDelete = lHead->lNext;        lHead->lNext = lDelete->lNext;        free(lDelete);    }}//销毁栈void destoryStack(LinkedStack lHead) {    clearStack(lHead);    free(lHead);}