专栏首页开心的学习之路线性结构------共享栈

线性结构------共享栈

如果一个程序需要使用多个栈,使用顺序栈就会造成栈空间大小难以估计,从而造成有的栈溢出有的栈空闲,此时可以建立一个共享栈,通俗地讲就是将两个栈的栈底设置在同一个数组的两端,栈顶位置用top1、top2表示。如图:

所以共享栈的数据结构类型为:

#include <cstdio>
#define MAX 10
#define INF 0xfffffff
typedef int DataType;

struct DStack
{
	DataType data[MAX];
	int top1;               //top1从数组头部向尾部移动 
	int top2;               //top2从数组尾部向头部移动 
};

基本操作实现:

void InitDStack(DStack &s)
{
	s.top1 = 0;
	s.top2 = MAX - 1;
}

bool isFull(DStack &s)
{
	/*与top的走动方式有关,我这里top1从0开始,
	用top1++,所以判断栈满标志为top2跑到top1前面 */ 
	return s.top1 > s.top2 ? true : false;
}

void Push(DStack &s, DataType e, int tag)
{
	if(isFull(s))
	{
		printf("Full!\n");
		return ;		
	}
	if(tag)
		s.data[s.top1++] = e;
	else
		s.data[s.top2--] = e;
}

bool isEmpty(DStack &s, int tag)
{
	if(tag)
		return s.top1 == 0 ? true : false;
	else
		return s.top2 == MAX - 1 ? true : false;
}

DataType Pop(DStack &s, int tag)
{
	if(isEmpty(s, tag))
	{
		printf("Empty!\n");
		return INF;
	}
	if(tag)
		return s.data[--s.top1];
	else
		return s.data[++s.top2];
}

测试代码:

int main()
{
	DStack s;
	int t1, t2;
	InitDStack(s);
	
	//测试Push
	 
	for(int i = 0; i < 5; i++)
	{
		Push(s, i, 1); 
		Push(s, 10 - i, 0);
	}
	for(int i = 0; i < 10; i++)
	{
		printf("%d ", s.data[i]);
	}	
	printf("\n");
	
	Push(s, 100, 1);
	Push(s, 100, 0);
	
	printf("\n\n");
	
	//测试Pop
	for(int i = 0; i < 5; i++)
	{
		t1 = Pop(s, 1); 
		t2 = Pop(s, 0);
		printf("t1 = %d\nt2 = %d\n", t1, t2);
	}
	
	t1 = Pop(s, 1);
	t2 = Pop(s, 0);
	return 0 ;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基础练习 十六进制转十进制

      从键盘输入一个不超过8位的正的十六进制数字符串,将它转换为正的十进制数后输出。   注:十六进制数中的10~15分别用大写的英文字母A、B、C、D、E、F...

    刘开心_1266679
  • 算法训练 Hanoi问题

      如果将课本上的Hanoi塔问题稍做修改:仍然是给定N只盘子,3根柱子,但是允许每次最多移动相邻的M只盘子(当然移动盘子的数目也可以小于M),最少需要多少次?...

    刘开心_1266679
  • 基础练习 矩阵乘法

      给定一个N阶矩阵A,输出A的M次幂(M是非负整数)   例如:   A =   1 2   3 4   A的2次幂   7 10   15 2...

    刘开心_1266679
  • HDU 3499 Flight(分层图最短路)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3499

    Ch_Zaqdt
  • Golang Leetcode 662. Maximum Width of Binary Tree.go

    更多内容请移步我的repo:https://github.com/anakin/golang-leetcode

    anakinsun
  • 图像裁剪后缩放到某个尺寸,不变形

    用户2930595
  • hadoop基础入门教程--DKHadoop配置安装教程

    使用hadoop版本是DKH标准三节点发行版,DKHadoop版本的易用性比较好,环境部署要简单的多,参考此篇安装前请先下载DKHadoop版本,网盘链接:ht...

    IT小白龙
  • wordpress调用文章摘要,若无摘要则自动截取文章内容字数做为摘要

    以下是调用指定分类文章列表的一个方法,作者如果有填写文章摘要则直接调用摘要;如果文章摘要忘记写了则自动截取文章内容字数做为摘要。这个方法也适用于调用descri...

    ytkah
  • (翻译)LearnVSXNow!-#4 创建一个带有工具窗的Package

    上一次我们实现了一个带有命令(Command)的package,这一次让我们更进一步:创建一个被称为工具窗(Tool Window)的界面。那么,什么是工具窗...

    明年我18
  • 平面检测-搜索真实世界的表面

    现在我们已经完成了正确运行ARKit项目的所有基本设置,我们希望我们的设备能够坐在水平表面上。这是飞机检测。在本节中,我们将学习如何激活平面检测。我们将熟悉锚点...

    iOSDevLog

扫码关注云+社区

领取腾讯云代金券