实训C++语言设计——Stack 栈运算

#include <iostream>
#include <string>
using namespace std;

//---------------抽象数据类型顺序栈的定义------------------//
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
typedef char SElemType,QElemType;
typedef struct {
SElemType *base;
SElemType *top;
int StackSize;
}SqStack;

//---------------------顺序栈的接口函数声明-----------------------//
//构造一个空栈
bool InitStack(SqStack &S);

//销毁栈,释放栈所占内存空间
void DestroyStack(SqStack &S);

//把S置为空栈
bool ClearStack(SqStack &S);

//若栈S为空栈,返回true,否则返回false
bool StackEmpty(SqStack &S);

//返回栈S的元素个数
int StackLength(SqStack &S);

//若栈不空,则用e返回S的栈顶元素,并返回ok;否则返回error
bool GetTop(SqStack &S,SElemType &e);

//插入新元素e为新的栈顶元素
bool Push(SqStack &S,SElemType e);

//若栈不空,删除S的栈顶元素,并用e返回其值,并返回true,否则返回false
bool Pop(SqStack &S,SElemType& e);

//-----------接口函数的实现部分-------------------//
bool InitStack(SqStack &S)
{//构造一个空栈
S.base = new SElemType[STACK_INIT_SIZE];
if(!S.base) return false;
S.top = S.base;
S.StackSize = STACK_INIT_SIZE;
return true;
}//InitStack

void DestroyStack(SqStack &S)
{//销毁栈,释放栈所占内存空间
if( S.base ) delete []S.base;
}//DestroyStack

bool ClearStack(SqStack &S)
{//把S置为空栈
if(!S.base) return false;
S.top = S.base;
return true;
}//ClearStack

bool StackEmpty(SqStack &S)
{//若栈S为空栈,返回true,否则返回false
if( S.base == S.top ) return true;
else return false;
}//StackEmpty

int StackLength(SqStack &S)
{//返回栈S的元素个数,即栈的长度
return S.top - S.base;
}//StackLength

bool GetTop(SqStack &S, SElemType &e)
{//若栈不空,则用e返回S的栈顶元素,并返回ok;否则返回error
if ( S.top == S.base ) return false;
e = *(S.top - 1);//栈顶指针总是指向栈顶元素的下一个存储单元的
return true;
}//GetTop

bool Push(SqStack &S, SElemType e)
{//插入新元素e为新的栈顶元素
if((S.top - S.base)== S.StackSize){//栈满,追加存储空间
S.base = new(S.top) SElemType[STACK_INCREMENT];
if (S.base) return false;
S.top = S.base + S.StackSize;
S.StackSize += STACK_INCREMENT;
}
*S.top++ = e;
return true;
}//Push

bool Pop(SqStack &S,SElemType& e)
{//若栈不空,删除S的栈顶元素,并用e返回其值,并返回true,否则返回false
if( S.top == S.base ) return false;
e = *--S.top;
return true;
}//Pop

// SqStack.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "SqStack.h"

int _tmain(int argc, _TCHAR* argv[])
{

SqStack s; //发生了什么？
InitStack(s); //又发生了什么？
char str[40] = {"My name is Betty Dolsberry!"};
cout << str << endl; //print the string
int i = 0;
while (str[i])
//无需对栈满进行判断,SqStack在栈满时
//会自动增加栈空间
Push(s, str[i++]);
char c;
while (!StackEmpty(s)){ //print the reverse
Pop(s, c);
cout << c;
}
return 0;
}