数据结构(4)：链栈的表示和实现

/* 语言：C++ 编译环境：Visual C++6.0 链栈的表示和实现 */
#include <iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
// Status是函数返回值类型，其值是函数结果状态代码
typedef int Status;
// 自定义数据类型别名
typedef int ElemType;
using namespace std;

// 链栈的存储结构
typedef struct StackNode
{
    ElemType data;
    struct StackNode *next;
}StackNode,*LinkStack;

// 链栈的初始化
Status InitStack(LinkStack &S)
{   // 构造一个空栈S，栈顶指针置空
    S = NULL;
    return OK;
}

Status Push(LinkStack &S,ElemType e)
{
    LinkStack p;        
    p = new StackNode;  // 生成新结点
    p->data = e;        // 将新结点数据域置为e
    p->next = S;        // 将新结点插入栈顶
    S = p;              // 修改栈顶指针为p
    return OK;
}

// 链栈的出栈
Status Pop(LinkStack &S,ElemType &e)
{   // 删除S的栈顶元素，用e返回其值
    LinkStack p;
    if(S==NULL) return ERROR;   // 栈空
    e = S->data;                // 将栈顶元素赋给e
    p=S;                        // 用p临时保存栈顶元素空间，以备释放
    S=S->next;                  // 修改栈顶指针
    delete p;                   // 释放原栈顶元素的空间
    return OK;
}

// 取链栈的栈顶元素
ElemType GetTop(LinkStack S)
{   // 返回S的栈顶元素，不修改栈顶指针
    if(S != NULL)           // 栈非空
        return S->data;     // 返回栈顶元素的值，栈顶指针不变
    return ERROR;
}

int main()
{
    LinkStack S;
    // 列表菜单
    cout<<"1 InitStack"<<endl;
    cout<<"2 Push"<<endl;
    cout<<"3 Pop"<<endl;
    cout<<"4 GetTop"<<endl;

    int choice,e;
    while(1)
    {
        cout<<"Input a choice: ";
        cin>>choice;

        // 选择
        switch(choice)
        {
            case 1:
                InitStack(S);
                continue;
            case 2:
                Push(S,3);
                continue;
            case 3:
                Pop(S,e);
                continue;
            case 4:
                cout<<"Get: "<<GetTop(S)<<endl;
                continue;
            default:
                cout<<"End..."<<endl;
                break;
        }
        break;

    }
    return 0;
}