栈采用链式存储，编程实现读取、进栈、出栈等基本操作。

Question

【问题描述】
栈采用链式存储，编程实现读取、进栈、出栈等基本操作。

Answer 1

相当于前插法

/*  链栈

          实现操作：
        *1 进栈
        *2 出栈
        *3 读栈顶元素
        *4 判空

代码使用不带头结点的单链表实现链栈，
入栈、出栈操作相当于单链表在表头的
插入、删除操作。
                            */
#include <iostream>
#include <cstdio>
using namespace std;

typedef int ElemType;
struct Node {
    ElemType data;  //栈中元素
    Node* next;     //下一个元素的指针
};
typedef Node* LinkStack;

//初始化一个链栈
void InitLinkStack( LinkStack& S )
{
    //S永远指向栈顶元素，初始化时栈为空，S初始化为NULL
    S = NULL;
}

//判空
bool StackEmpty( LinkStack S )
{
    if( S == NULL )
        return true;
    return false;
}

//进栈:将元素x压入堆栈
bool Push( LinkStack& S, ElemType x )
{
    Node* temp = new Node;
    temp->data = x;
    if( S == NULL ) {
        S = temp;
        S->next = NULL;
        return true;
    }
    temp->next = S;
    S = temp;
    return true;
}

//出栈:将栈顶元素出栈，并将其值用x带回
bool Pop( LinkStack& S, ElemType& x )
{
    if( S == NULL )
        return false;
    x = S->data;
    Node* toFree = S;
    S = S->next;    //新栈顶
    delete toFree;
    return true;
}

bool GetTop( LinkStack S, ElemType x )
{
    if( S == NULL )
        return false;
    x = S->data;
    return true;
}

void test1()
{
    LinkStack S;
    InitLinkStack(S);
    for( int i=1; i<=50; i++ ) {
        if( Push(S,i) ) {
            cout << "入栈成功，入栈的元素是：" << i << endl;
        }
        else cout << "入栈失败 " << endl;
    }

    cout << "-------------------------------" << endl;
    while( !StackEmpty(S) ) {
        int x = 0;
        Pop(S,x);
        cout << x << endl;
    }

}

int main()
{
    test1();
    return 0;
}