#define __SQ_STACK_H__
#include "utility.h"// 实用程序软件包
// 顺序栈类模板
template<class ElemType>
class SqStack
{
protected:
// 顺序栈的数据成员:
int count // 元素个数
int maxSize// 栈最大元素个数
ElemType *elems // 元素存储空间
// 辅助函数模板:
bool Full() const // 判断栈是否已满
void Init(int size) // 初始化栈
public:
// 抽象数据类型方法声明及重载编译系统默认方法声明:
SqStack(int size = DEFAULT_SIZE) // 构造函数模板
virtual ~SqStack() // 析构函数模板
int Length() const // 求栈长度
bool Empty() const // 判断栈是否为空
void Clear()// 将栈清空
void Traverse(void (*visit)(const ElemType &)) const// 遍历栈
StatusCode Push(const ElemType &e) // 入栈
StatusCode Top(ElemType &e) const // 返回栈顶元素
StatusCode Pop(ElemType &e)// 出栈
SqStack(const SqStack<ElemType>©) // 复制构造函数模板
SqStack<ElemType>&operator =(const SqStack<ElemType>©)// 重载赋值运算符
}
// 顺序栈类模板的实现部分
template <class ElemType>
bool SqStack<ElemType>::Full() const
// *** 作结果：如栈已满，则返回true，否则返回false
{
return count == maxSize
}
template <class ElemType>
void SqStack<ElemType>::Init(int size)
// *** 作结果：初始化栈为最大元素个数为size的空栈
{
maxSize = size // 最大元素个数
if (elems != NULL) delete []elems// 释放存储空间
elems = new ElemType[maxSize] // 分配存储空间
count = 0 // 空栈元素个数为0
}
template<class ElemType>
SqStack<ElemType>::SqStack(int size)
// *** 作结果：构造一个最大元素个数为size的空栈
{
elems = NULL // 未分配存储空间前,elems为空
Init(size) // 初始化栈
}
template<class ElemType>
SqStack<ElemType>::~SqStack()
// *** 作结果：销毁栈
{
delete []elems// 释放存储空间
}
template <class ElemType>
int SqStack<ElemType>::Length() const
// *** 作结果：返回栈元素个数
{
return count
}
template<class ElemType>
bool SqStack<ElemType>::Empty() const
// *** 作结果：如栈为空，则返回true，否则返回false
{
return count == 0
}
template<class ElemType>
void SqStack<ElemType>::Clear()
// *** 作结果：清空栈
{
count = 0
}
template <class ElemType>
void SqStack<ElemType>::Traverse(void (*visit)(const ElemType &)) const
// *** 作结果：从栈底到栈顶依次对栈的每个元素调用函数(*visit)
{
for (int curPosition = 1curPosition <= Length()curPosition++)
{ // 从栈底到栈顶对栈的每个元素调用函数(*visit)
(*visit)(elems[curPosition - 1])
}
}
template<class ElemType>
StatusCode SqStack<ElemType>::Push(const ElemType &e)
// *** 作结果：将元素e追加到栈顶,如成功则返加SUCCESS,如栈已满将返回OVER_FLOW
{
if (Full())
{ // 栈已满
return OVER_FLOW
}
else
{ // *** 作成功
elems[count++] = e// 将元素e追加到栈顶
return SUCCESS
}
}
template<class ElemType>
StatusCode SqStack<ElemType>::Top(ElemType &e) const
// *** 作结果：如栈非空,用e返回栈顶元素,返回SUCCESS,否则返回UNDER_FLOW
{
if(Empty())
{ // 栈空
return UNDER_FLOW
}
else
{ // 栈非空, *** 作成功
e = elems[count - 1] // 用e返回栈顶元素
return SUCCESS
}
}
template<class ElemType>
StatusCode SqStack<ElemType>::Pop(ElemType &e)
// *** 作结果：如栈非空,删除栈顶元素,并用e返回栈顶元素,返回SUCCESS,否则
// 返回UNDER_FLOW
{
if (Empty())
{ // 栈空
return UNDER_FLOW
}
else
{ // *** 作成功
e = elems[count - 1] // 用e返回栈顶元素
count--
return SUCCESS
}
}
template<class ElemType>
SqStack<ElemType>::SqStack(const SqStack<ElemType>©)
// *** 作结果：由栈copy构造新栈——复制构造函数模板
{
elems = NULL // 未分配存储空间前,elems为空
Init(copy.maxSize) // 初始化新栈
count = copy.count // 栈元素个数
for (int curPosition = 1curPosition <= Length()curPosition++)
{ // 从栈底到栈顶对栈copy的每个元素进行复制
elems[curPosition - 1] = copy.elems[curPosition - 1]
}
}
template<class ElemType>
SqStack<ElemType>&SqStack<ElemType>::operator = (const SqStack<ElemType>©)
// *** 作结果：将栈copy赋值给当前栈——重载赋值运算符
{
if (© != this)
{
Init(copy.maxSize)// 初始化当前栈
count = copy.count// 复制栈元素个数
for (int curPosition = 1curPosition <= Length()curPosition++)
{ // 从栈底到栈顶对栈copy的每个元素进行复制
elems[curPosition - 1] = copy.elems[curPosition - 1]
}
}
return *this
}
#endif
#include <stdio.h>#include <stdlib.h>
#include <string.h>
struct CHAP5
{
char * pName
bool Gender
int Age
struct CHAP5 * next
}
struct Node_int{
int i
struct Node_int * next
}
/*由于两种栈在结构的高度相似性，用宏代替重复的语句进行栈 *** 作函数声明*/
#define DECLARE_STACK_PUSH(function_name, node_type) void function_name(node_type ** top, node_type * data) {\
node_type * x = (node_type *)malloc(sizeof(node_type))\
memcpy(x, data, sizeof(node_type))\
x->next = *top*top = xreturn }
#define DECLARE_STACK_POP(function_name, node_type) int function_name(node_type **top, node_type * data) {\
node_type * x = *topif (!x) return 0\
*top = x->nextmemcpy(data, x, sizeof(node_type))\
data->next = 0free(x)return 1}
/*这里才是真正声明四个栈 *** 作函数*/
DECLARE_STACK_PUSH(stack_int_push, struct Node_int)
DECLARE_STACK_POP (stack_int_pop, struct Node_int)
DECLARE_STACK_PUSH(stack_chap5_push,struct CHAP5)
DECLARE_STACK_POP (stack_chap5_pop, struct CHAP5)
void test_stack_int(void)
{
int x = 0struct Node_int y, * top = 0
printf("请输入一些数字检测堆栈，输入0结束\n")
do {
scanf("%d", &x)
y.i = x
stack_int_push(&top, &y)
}while(x)
printf("退栈结果:\n")/*相当于栈清空 *** 作*/
do {
x = stack_int_pop(&top, &y)
if (x) printf("%d\t", y.i )
}while(x)
printf("\n")
}
void test_stack_chap5(void)
{
int x = 0struct CHAP5 y, * top = 0
printf("请输入几个姓名、年龄、性别用于检测堆栈，年龄输入0表示结束\n")
do {
y.pName = (char *)malloc(64)
scanf("%s %d %d", y.pName , &(y.Age), &x)
y.Gender = x==0?true:false
stack_chap5_push(&top, &y)
}while(y.Age )
printf("退栈结果:\n姓名\t年龄\t性别\n")/*相当于栈清空 *** 作*/
do {
x = stack_chap5_pop(&top, &y)
if (x) printf("%s\t%d\t%s\n", y.pName , y.Age, y.Gender?"男":"女")
}while(x)
}
int main(void)
{
test_stack_int()
test_stack_chap5()
system("pause")
return 0
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）