数据结构-第三章-顺序栈-两种栈顶指针指示方法实现各种基本功能

两种栈顶指针指示方法实现各种基本功能

**文件名后缀应为.cpp
文件名后缀应为.cpp
文件名后缀应为.cpp**

法一：
规定为栈顶指针指向有效栈首元素

法二：
规定为栈顶指针指向下一个要存储的元素的位置

Cpp代码如下

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MaxSize 20
#define ElemType int

typedef struct {
    ElemType data[MaxSize];
    int top;
} SqStack;

void InitStack( SqStack &S );                //定义 初始化顺序栈 函数
bool StackEmpty( SqStack S );                //定义 判断顺序栈空 函数
bool StackFull( SqStack S );                //定义 判断顺序栈满 函数
int StackLength( SqStack S );                //定义 返回栈的长度 函数
bool Push( SqStack &S, ElemType x );        //定义 推入栈 函数
bool Pop( SqStack &S, ElemType &x );        //定义 弹出栈 函数
bool GetTop( SqStack S, ElemType &x );        //定义 获取栈顶元素 函数
bool ClearStack( SqStack &S );                //定义 清空顺序栈 函数

void PrintStack( SqStack S );
int main() {

    srand( ( unsigned )time( NULL ) );

    SqStack S; //定义一个顺序栈
    InitStack( S ); //初始化顺序栈

    //测试栈空和满函数
    printf( "\n推入前：\n" );
    printf( "空结果：%d\n", StackEmpty( S ) );
    printf( "满结果：%d\n", StackFull( S ) );

    //测试推入栈函数
    for( int i = 0; i < 20; i++ ) {
        Push( S, i );
    }
    PrintStack( S );

    //测试栈空和满函数
    printf( "\n推入后：\n" );
    printf( "空结果：%d\n", StackEmpty( S ) );
    printf( "满结果：%d\n", StackFull( S ) );

    //测试 弹出栈函数
    printf( "弹出元素依次为：\n" );
    for( int i = 0; i < 5; i++ ) {
        int x;
        Pop( S, x );
        printf( "%d ", x );
    }
    printf( "\n" );
    PrintStack( S );

    //测试读取栈顶元素函数
    int x;
    if( GetTop( S, x ) ) {
        printf( "S.data[S.top]=%d\n", x );
    } else {
        printf( "栈空，读取失败！\n" );
    }

    //测试清空栈函数
    ClearStack( S );
    PrintStack( S );

    return 0;
}

//实现 初始化顺序栈 函数
void InitStack( SqStack &S ) {
    //法一：
//    S.top = -1;            //规定：栈顶指针指向有效栈首元素
    //法二：
    S.top = 0;        //规定：栈顶指针指向下一个要放的元素的位置

//    此处法一、法二 与以下函数中法一法二配套使用 ！！！！！！！！
}

//实现 判断顺序栈空 函数
bool StackEmpty( SqStack S ) {
//    法1
//    if( S.top == -1 )
//        return true;
//    else
//        return false;
//  法二
    if( S.top == 0 )
        return true;
    else
        return false;
}

//实现 判断顺序栈满 函数
bool StackFull( SqStack S ) {
    //法一
//    if( S.top == MaxSize - 1 )
//        return true;
//    else
//        return false;

    //法二
    if( S.top == MaxSize )
        return true;
    else
        return false;
}

//实现 返回栈的长度 函数
int StackLength( SqStack S ) {
//    法一:
//    return S.top + 1;
//    法二:
    return S.top;
}

//实现 推入栈 函数
bool Push( SqStack &S, ElemType x ) {
    if( StackFull( S ) )    //判断栈是否满，若满则推入失败，返回false
        return false;
//    法一：
//    S.top++;
//    S.data[S.top] = x;

//    S.data[++S.top] = x;        //以上两句可由本句代替

//法二:
//    S.data[S.top] = x;
//    S.top++;

    S.data[S.top++] = x;        //以上两句可由本句代替

    return true;
}

//实现 弹出栈 函数
bool Pop( SqStack &S, ElemType &x ) {
    if( StackEmpty( S ) )
        return false;
//    法一：
//    x = S.data[S.top];
//    S.top--;

//    x = S.data[S.top--];        //以上两句可由本句代替

//    法二：
//    S.top--;
//    x = S.data[S.top];

    x = S.data[--S.top];        //以上两句可由本句代替
    return true;
}

//实现 获取栈顶元素 函数
bool GetTop( SqStack S, ElemType &x ) {
    if( StackEmpty( S ) )
        return false;
    //法一：
//    x = S.data[S.top];

    //法二：
    x = S.data[S.top - 1];
    return true;
}

//实现 清空顺序栈 函数
bool ClearStack( SqStack &S ) {
    //法一：
    S.top = -1;
    //法二：
    S.top = 0;
    return true;
}

void PrintStack( SqStack S ) {
    if( StackEmpty( S ) ) {
        printf( "栈空\n" );
        return;
    }

    printf( "当前栈元素为：\n" );

    //法一：
//    for( int i = 0; i <= S.top; i++ ) {
//        printf( "%d ", S.data[i] );
//    }

    //法二：
    for( int i = 0; i < S.top; i++ ) {
        printf( "%d ", S.data[i] );
    }

    printf( "\n共%d个元素\n", StackLength( S ) );
}