静态IP Eclipse 阿里巴巴 wavedorm 工厂模式 loops canvas vuejs 教程 软件测试项目实战案例 bootstrap中文api文档 jq入口函数 div字体加粗 bootstrap居中对齐 python插件 python中import用法 python传参 java教程 java日期格式化 linux如何安装 vb编程 超级煎蛋卷 linux解压tar robotstudio netreflector 特战英雄辅助 selinux关闭 红巨人插件 medcalc 计算机科学概论 文件分割 死从天降成就 炫舞爱的惊喜 su镜像 dbgview origin柱状图 ps魔棒快捷键 pr怎么消除杂音 cad合并成块 决战者加点 打印机怎么换色带
当前位置: 首页 > 学习教程  > 编程语言

两栈共享空间(数组)

2020/10/8 18:38:50 文章标签:

两栈共享空间(数组) 本文参考资料:《大话数据结构》 两栈共享空间的结构代码 /* 两栈共享空间结构 */ typedef struct {SElemType data[MAXSIZE];int top1; //栈1栈顶指针int top2; //栈2栈顶指针 }SqDoubleStack;对于两栈共享空间的push方法,除了要插入…

两栈共享空间(数组)

本文参考资料:《大话数据结构》

两栈共享空间

两栈共享空间的结构代码

/* 两栈共享空间结构 */
typedef struct
{
    SElemType data[MAXSIZE];
    int top1;	//栈1栈顶指针
    int top2;	//栈2栈顶指针
}SqDoubleStack;

对于两栈共享空间的push方法,除了要插入元素值参数外,还需要有一个判断是栈1还是栈2的栈号参数stackNumber;

/* 插入元素e为新的栈顶元素 */
Status Push(SqDoubleStack *S, SElemType e, int stackNumber)
{
    if(S->top1+1 == S->top2)	//栈已满,不能再push新元素了
        return ERROR;
    if(stackNumber == 1)	//栈1有元素进栈
        S->data[++S->top1] = e;	//若栈1则先top1+1后给数组元素赋值
    else if(stackNumber == 2)	//栈2有元素进栈
        S->data[--S->top2] = e;	//若栈2则先top2-1后给数组元素赋值
    return OK;
}

​ 因为在开始已经判断了是否有栈满的情况,所以后面的top1+1或top2-1是不担心溢出问题的。

​ 对于两栈共享空间的pop方法,参数就只是判断栈1栈2的参数stackNumber,代码如下:

/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
Status Pop(SqDoubleStack *S,SElemType *e, int stackNumber)
{
    if(stackNumber == 1)
    {
        if(S->top1 == -1)
            return ERROR;	//说明栈1已经是空栈,溢出
        *e = S->data[S->top1--];	//将栈1的栈顶元素出栈
    } else if(stackNumber == 2){
        if(S->top2 == MAXSIZE)
            return ERROR;	//说明栈2已经是空栈,溢出
        *e = S->data[S->top2++];	//将栈2的栈顶元素出栈
    }
    return OK;
}

​ 事实上,使用这样的数据结构,通常是当两个栈的空间需求有相反关系时,也就是一个栈增长时另一个栈在缩短的情况。就像买买股票,你买入时,一定是有一个你不知道的让人在做卖出操作。有人赚钱,就一定是有人赔钱。这样使用两栈共享空间存储方法才有比较大的意义。否则两个栈都在不停地增长,那很快就会因栈满而溢出了。

​ 当然了,这只是针对两个具有相同数据类型的栈的一个设计上的技巧,如果不是相同的数据类型,这种方法不但不能更好地处理问题,反而会使问题变得更复杂。

#include <stdio.h>
#include <stdbool.h>
#define MAXSIZE 100
#define ERROR 0
#define OK 1
typedef int SElemType;
typedef int Status;
typedef struct{
	SElemType data[MAXSIZE];
	int top1;	//栈1栈顶指针
	int top2;	//栈2栈顶指针 
}SqDoubleStack;

/* 入栈 */
Status push(SqDoubleStack* S, int stackNum, SElemType e){
	if(S->top1+1 == S->top2)	//栈满 
		return ERROR;
	if(stackNum == 1){
		S->data[++S->top1] = e;
	}else{
		S->data[--S->top2] = e;
	}
	return OK;
}

/* 出栈 */
Status pop(SqDoubleStack* S, int stackNum, SElemType *e){
	if(stackNum == 1){
		if(S->top1 == -1){	//栈空 
			return ERROR;
		}
		*e = S->data[S->top1--];
		return OK;
	}else{
		if(S->top2 == MAXSIZE){	//栈空 
			return ERROR;
		}
		*e = S->data[S->top2++];
		return OK;
	}
}

/* 返回栈顶元素 */
SElemType getTop(SqDoubleStack* S, int stackNum, SElemType* e){
	if(stackNum == 1){
		if(S->top1 == -1){	//栈空 
			return ERROR;
		}
		*e = S->data[S->top1];
		return OK;
	}else{
		if(S->top2 == MAXSIZE){	//栈空 
			return ERROR;
		}
		*e = S->data[S->top2];
		return OK;
	}
}

/* 栈空 */
bool stackEmpty(SqDoubleStack* S, int stackNum){
	if(stackNum == 1){
		if(S->top1 == -1)
			return true;
		return false;
	}else{
		if(S->top2 == MAXSIZE)
			return true;
		return false;
	}
}

/* 栈满 */
bool stackFull(SqDoubleStack* S){
	if(S->top1+1 == S->top2)
		return true;
	return false;
} 

/* 栈元素遍历 */
void printStack(SqDoubleStack* S){
	if(stackEmpty(S, 1) && stackEmpty(S, 2)){
		printf("栈空!\n");
		return;
	}
	int i = 0;
	printf("栈中元素遍历:\n");
	printf("栈1元素集:\n");
	while(i<=S->top1)
		printf("%d\n", S->data[i++]);
	printf("栈2元素集:\n");
	i=MAXSIZE-1;
	while(i>=S->top2)
		printf("%d\n", S->data[i--]);
}

/* 栈长度 */
int stackLength(SqDoubleStack* S, int stackNum){
	if(stackNum == 1)
		return S->top1+1;
	else
		return MAXSIZE-S->top2;
}

int main(){
	
	bool continueFlag = true;
	SElemType popNum, pushNum;
	SqDoubleStack doubleStack, *S = &doubleStack;
	doubleStack.top1 = -1;
	doubleStack.top2 = MAXSIZE;
	int stackNum;
	int functionNum;
	while(continueFlag){
		printf("-----------菜单------------\n");
		printf("-----------1.入栈----------\n");
		printf("-----------2.出栈----------\n");
		printf("-----------3.返回栈顶元素--\n");
		printf("-----------4.栈元素遍历----\n");
		printf("-----------5.栈元素个数----\n");
		printf("-----------6.判断栈是否为空\n");
		printf("-----------7.判断栈是否已满\n");
		printf("-----------8.退出----------\n");
		printf("输入功能号:\n");
		scanf("%d",&functionNum);
		printf("-----------------------\n");
		switch(functionNum){
			case 1:
				printf("选择栈(1或2):\n");
				scanf("%d", &stackNum);
				printf("请输入要入栈的元素:\n");
				scanf("%d", &pushNum);
				if(push(S, stackNum, pushNum))
					printf("入栈成功!\n");
				else
					printf("入栈失败!\n");
				break;
			case 2:
				printf("选择栈(1或2):\n");
				scanf("%d", &stackNum);
				if(pop(S, stackNum, &popNum))
					printf("出栈元素:%d\n",popNum);
				else
					printf("栈空!\n");
				break;
			case 3:
				printf("选择栈(1或2):\n");
				scanf("%d", &stackNum);
				if(getTop(S, stackNum, &popNum))
					printf("栈顶元素:%d!\n",popNum);
				else
					printf("栈空!\n");
				break;
			case 4:
				printStack(S);
				break;
			case 5:
				printf("选择栈(1或2):\n");
				scanf("%d", &stackNum);
				printf("栈元素个数:%d\n",stackLength(S, stackNum));
				break;
			case 6:
				printf("选择栈(1或2):\n");
				scanf("%d", &stackNum);
				if(stackEmpty(S, stackNum))
					printf("栈空!\n");
				else
					printf("栈非空!\n");
				break;
			case 7:
				if(stackFull(S))
					printf("栈满!\n",popNum);
				else
					printf("栈不满!\n");
				break;
			case 8:
				continueFlag = false;
				printf("欢迎使用!\n");
				break;
			default:
				printf("功能号不存在!\n");
				break;
		}
		printf("-----------------------\n");
	}
	return 0;
} 

本文链接: http://www.dtmao.cc/news_show_250076.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?