利用栈的基本运算返回指定栈中的栈底元素,要求仍保持栈中元素不变

标签: 顺序栈

一、栈的基本运算:

  • InitStack(&st):初始化栈,构造一个空栈st。
  • StackEmpty(st):判断栈是否为空,若栈st为空,则返回真;否则返回假。
  • Pusth(&st ,x):进栈。将元素x插入到栈st中作为栈顶元素。
  • Pop(&st, &x):出栈。从栈st中退出栈顶元素,并将其值赋给x。
  • GetTop(st, &x):取栈顶元素。返回当前的栈顶元素,并将其值赋给x。

  在设计函数参数类型的时候,如果要求形参可改变实参,那么将形参类型设置为指针或者是引用;如果不希望形参改变实参或者形参不允许改变实参,那就采用值传递的方式。注意体会上述5个栈基本运算函数的参数类型。

二、实现:

#include<stdio.h>
typedef int ElemType;
#define MaxSize 10

/*顺序栈*/
typedef struct
{
	ElemType data[MaxSize];
	int top;
}SqStack;

/*初始化顺序栈*/
void InitStack(SqStack &st)
{
	st.top = -1;
}

/*判断栈是否为空*/
bool StackEmpty(SqStack st)
{
	return(st.top == -1);
}

/*进栈算法*/
bool Pusth(SqStack &st, ElemType x)
{
	if (st.top == MaxSize - 1) //栈满的情况,即栈上溢出
		return false;

	st.top++;
	st.data[st.top] = x;
	return true;
}

/*出栈算法*/
bool Pop(SqStack &st, ElemType &x)
{
	if (st.top == -1) //栈空的情况,即栈下溢出
		return false;

	x = st.data[st.top];
	st.top--;
	return true;
}

/*取栈顶元素算法*/
bool GetTop(SqStack st, ElemType &x)
{
	if (st.top == -1) //栈空的情况,即栈下溢出
		return false;

	x = st.data[st.top];
	return true;
}

三、思路:

       假定采用顺序栈结构。先退栈st中所有元素,利用一个临时栈tmpst存放从st栈中退栈的元素,最后一个元素即为所求,然后将临时栈tmpst中的元素逐一出栈并进栈到st中,这样就恢复st栈中原来的元素。

/*****************************************************************
*函数名:GetBottom
*函数功能描述:取得顺序栈中栈底元素,利用栈的基本运算
*函数参数:st-顺序栈的引用,x-元素的引用
*函数返回值:成功获得栈底元素,返回true,否则返回false
*作者:王赋睿
*函数创建日期:2018.5.28
*函数修改日期:尚未修改
*修改人:尚未修改
*修改原因:尚未修改
*版本:1.0
*历史版本:无
*****************************************************************/
bool GetBottom(SqStack st, ElemType &x)
{
	ElemType e;
	SqStack tmpst; //定义临时栈
	InitStack(tmpst); //初始化临时栈
	
	if (StackEmpty(st)) //空栈返回false
		return false;

	while (!StackEmpty(st)) //临时栈tmpst包含st栈中的逆转元素
	{
		Pop(st, x);
		Pusth(tmpst, x);
	}
	
	while (!StackEmpty(tmpst)) //恢复st栈中原来的内容
	{
		Pop(tmpst, e);
		Pusth(st, e);
	}
	return true;
}

四、测试用例:

int main()
{
	SqStack st;
	InitStack(st);
	ElemType data[] = { 1,2,3,4,5 };
	ElemType x;
	int n = sizeof(data) / sizeof(ElemType);
	for (int i = 0; i < n; i++)
	{
		Pusth(st, data[i]);
	}
	GetBottom(st, x);

	printf("%d\n", x);
}

五、运行结果:

本程序在VS2017下运行通过

原文链接:加载失败,请重新获取