两种栈顶指针指示方法实现各种基本功能
**文件名后缀应为.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 ) );
}