-
考研数据结构之栈(2.5)——练习题之设计一个共享栈s0和s1以及有关入栈和出栈操作的算法(C表示)
2020-05-31 15:54:55为了充分利用空间,顺序栈s0、s1共享一个存储区elem[0, ... , maxSize-1]。试着设计一个共享栈s0、s1以及有关入栈和出栈操作的算法,假设栈中元素是int型。 分析 算法思想: 1)顺序栈栈底固定不变,因此将栈底设...题目
为了充分利用空间,顺序栈s0、s1共享一个存储区elem[0, ... , maxSize-1]。试着设计一个共享栈s0、s1以及有关入栈和出栈操作的算法,假设栈中元素是int型。
分析
算法思想:
1)顺序栈栈底固定不变,因此将栈底设在存储区的两端,即s0栈底设在0处,sI栈底设在maxSize-1处,栈顶在0~maxSize-1的范围内变动。当两栈栈顶相遇时为栈满,这样可以尽可能地利用空间。
2) sO的栈项为top0,s0 入栈操作为: top0 先自增1,然后存入元素:出栈操作为:先取出栈项元素,top0再自减1. sI的栈顶为top1, s1入栈操作为: top1 先自减1,然后存入元素:出栈操作为:先取出栈顶元素,topl 再自增1.图解:
代码
#include<stdio.h> #include<stdlib.h> #define maxSize 20 /* 定义共享栈结构体 */ typedef struct { int elem[maxSize];// 栈空间 int top[2];// top[0]为s0栈顶,top[1]为s1栈顶 } SqStack; /* 初始化栈 */ void initStack(SqStack &st) { st.top[0]=-1;// st0栈的栈底是-1 st.top[1]=maxSize;// st1栈的栈底是maxSize } /* 入栈 */ /* &st指的是共享栈;stNo指的是栈的编号,指元素入哪个栈;x指的是要入栈的元素 */ int push(SqStack &st,int stNo,int x) { if(st.top[0]+1<st.top[1]) { // 栈不满,则元素可以入栈 if(stNo==0) { // 元素入st0 ++(st.top[0]);// 栈顶指针先加1 st.elem[st.top[0]]=x;// 将新的元素压入st0栈中 return 1;// 入栈成功返回1 } else if(stNo==1) { // 元素入st1 --(st.top[1]);// 由于st1栈的栈顶元是从数组尾部开始向前的,所以需要减1 st.elem[st.top[1]]=x;// 将元素压入st1栈中 return 1;// 入st1栈成功返回1 } else { return -1;// 输入栈编号有误,返回-1 } } else { return 0;// 栈满后元素不能入栈,返回0 } } /* 出栈 */ /* &st指的是共享栈;stNo指的是栈的编号,指元素要出哪个栈;&x接收要栈的栈顶元素 */ int pop(SqStack &st,int stNo,int &x) { if(stNo==0) { // 表示st0栈的元素出栈 if(st.top[0]!=-1) { // st0不空,则可以出栈 x=st.elem[st.top[0]];// 出栈st0的栈顶元素 --(st.top[0]);// 栈顶指针减1 return 1;// 出栈成功返回1 } else { return 0;// 栈空,出栈失败返回0 } } else if(stNo==1) { // 表示st1栈的元素出栈 if(st.top[1]!=maxSize) { // 栈不空,可以出栈 x=st.elem[st.top[1]];// 出栈st1的栈顶元素 ++(st.top[1]);// 由于st1栈是从数组尾部开始的,所以需要加1才能表示出栈 return 1;// 出栈成功返回1 } else { return 0;// 出栈失败返回0 } } else { return -1;// 栈编号输入有误,返回-1 } } /* 打印共享栈 */ void printStack(SqStack st) { printf("\n"); for(int i=0; i<=st.top[0]; i++) { printf("%d\t",st.elem[i]); } for(int i=st.top[1]; i<maxSize; i++) { printf("%d\t",st.elem[i]); } printf("\n"); } int main() { SqStack st;// 定义共享栈 initStack(st);// 初始化栈 push(st,0,1);// 将元素1压入st0栈 push(st,0,2);// 将元素2压入st0栈 push(st,1,6);// 将元素6压入st1栈 push(st,1,5);// 将元素5压入st1栈 push(st,1,4);// 将元素4压入st1栈 printStack(st); int x1; pop(st,0,x1);// 将st0栈中的栈顶元素出栈 printStack(st);// 打印当前栈 int x2; pop(st,1,x2);// 将st1栈中的栈顶元素出栈 printStack(st); return 0; }
运行结果:
-
算法与数据结构之栈和队列篇
2020-10-18 22:34:17重要概念 1. 在栈的ADT定义中,除初始化操作外,其他基本操作的初始条件都要求栈已存在。...5. 当两个栈共享一存储区时,栈利用一维数组stack(1,n)表示,两栈顶指针为top[1]与top[2],则当栈1空时,top[1]为0,top[2]重要概念
1. 在栈的ADT定义中,除初始化操作外,其他基本操作的初始条件都要求栈已存在。
2. 栈是操作受限(或限定仅在表尾部进行插入和删除操作)的线性表,其运算遵循的是先进后出原则。
3. 堆栈是一种操作受限的线性表,它只能在线性表的一端进行插入和删除操作,对栈的访问是按照先进后出的原则进行的。
4. 向栈中压入元素的操作是先进栈,后退栈。
5. 当两个栈共享一存储区时,栈利用一维数组stack(1,n)表示,两栈顶指针为top[1]与top[2],则当栈1空时,top[1]为0,top[2]为n+1,栈满时为top[1]+1=top[2]。
6. 两个栈共享空间时栈满的条件为两栈顶指针值相减的绝对值为1(或两栈顶指针相邻)。
7. 在进行入栈运算时应先判断栈是否满;在进行出栈运算时应先判断栈是否为空;当栈中元素为n个,作进栈运算时发生上溢时,则说明该栈的最大容量为n。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享的一片连续的空间时,应将两个栈的栈底分别设置在内存空间的两端,这样只有当两栈顶指针值相减的绝对值为1(或两栈顶指针相邻)时才产生溢出。
8. 多个栈共享时,最好使用链式存储结构作为存储结构。
9. 队列又称作先进先出表。
10. 队列的特点是先进先出。
11. 在具有n个元素的非空队列中插入一个或者删除一个元素的操作时间复杂度为O(1)
12. 循环队列是一种顺序(物理)结构。
13. 循环队列的目的时为了解决假溢出时大量移动数据元素。
14. 区分循环队列的满与空,只有两种方法,它们是牺牲一个存储单元,设标记(设计数器等方法)。
15. 用循环队列表示队列的长度为n,若只设头指针,则出队和入队的时间复杂度分别是O(1)和O(n);若只设置尾指针,则出队和入队的时间复杂度分别是O(1)和O(1)。
-
栈的应用
2017-09-28 00:17:42栈的应用篇2:共享栈的应用描述:本篇为共享栈的另一应用,试想如何能提高栈的空间利用率,共享栈便不失为一个好的想法,两个栈共享一个内存空间,动态操作数据,以下为具体过程:基本设计思想:顺序栈的栈底固定不...栈的应用篇2:共享栈的应用
描述:本篇为共享栈的另一应用,试想如何能提高栈的空间利用率,共享栈便不失为一个好的想法,两个栈共享一个内存空间,动态操作数据,以下为具体过程:
基本设计思想:
顺序栈的栈底固定不动,我们将其设置在存储区的两端,假设s0为0处,s1设置在maxSize-1处,栈顶在0~maxSize-1活动,当两栈栈顶相遇便为栈满;s0的栈顶为top[0],进栈时规定先自增,再存入元素,出栈时先取元素,指针再自减1;s1入栈时top先自减,再存入元素,出栈时先取元素,指针再自增1。
#include<stdio.h> #include <iostream> using namespace std; #define MAXSIZE 100 //定义栈的结构体 typedef struct { //栈的数据 int data[MAXSIZE]; //top[0],top[1]分别表示栈1和栈2的栈顶坐标 int top[2]; }Sqstack; //入栈操作 int push(Sqstack &st,int stNo,int x) //stNo为栈编号 { if(top[0]+1 < top[1])//栈不满,元素入栈 { if(stNo == 0) { ++(st.top[0]); st.data[st.top[0]]=x; return 1; //入栈成功 } else if(stNo == 1) { --(st.top[1]); st.data[st.top[1]]=x; return 1; //入栈成功 } else return -1; } else return 0; //栈满后元素不能入栈 } //出栈操作 int pop(Sqstack &st,int stNo,int &x) //stNo为栈编号 { if(stNo == 0)//st0元素入栈 { if(st.top[0] != -1) { x = st.data[st.top[0]]; --(st.top[0]); return 1; //出栈成功 } else return 0; //st0栈空,出栈失败 } else if(stNo == 1) { if(st.top[1] != MAXSIZE) //st1不空,可以出栈 { x = st.data[st.top[1]]; ++(st.top[1]); return 1; //出栈成功 } else return 0; //s0栈空,出栈失败 } else return -1; }
-
不可不知的JVM 中堆 Heap、栈 Stack、方法区 Method area 、本地方法区 Native method area
2014-05-29 20:19:12这两个区域被jvm中的线程共享。当JVM加载了一个class文件后,则class中的参数、类型等信息会存储在方法区中。程序运行时所有创建的对象存储在堆中。 当每一个新线程启动时会有自己的程序计数器pcregister ...每个jvm实例都有方法区和一个堆(hasone method area and one heap)。这两个区域被jvm中的线程共享。当JVM加载了一个class文件后,则class中的参数、类型等信息会存储在方法区中。程序运行时所有创建的对象存储在堆中。
当每一个新线程启动时会有自己的程序计数器pcregister (program counter)和栈,如果线程调用方法,则程序计数器表明下一条执行的指令。线程栈存储线程的方法调用状态(包括局部变量、和被调用的参数、返回值、中间结果)。上面所说本地方法(见下图)调用相独立,本地方法调用存储在独立的本地方法栈中,或其他独立的内存区域。
每个线程都有一个程序计数器,也就是会说每创建一个线程时就会创建一个程序计数器,JVM中所说的程序技术器区域就是所有线程程序计数器取得总称。
栈区域是由栈桢组成,每个栈桢就是每个调用的方法的栈。当方法调用结束时JVM会POPS栈,即抛弃此方法的栈桢。
-
数据结构 栈和队列 算法设计题
2013-05-25 10:10:351. 设有两个栈S1,S2都采用顺序栈方式,并且共享一个存储区[O..maxsize-1],为了尽量利用空间,减少溢出的可能,可采用栈顶相向,迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。 【哈尔滨工业大学 2001 ... -
JVM内存模型详解
2020-09-10 21:17:05本地方法栈:它和栈中存储的内容基本一致,主要不同是:当线程执行Java方法时使用方法栈,执行本地方法时使用本地方法栈。 程序计数器:主要用于记录线程执行时的字节码位置,每一个线程都有一个独立的程序计数器,... -
双端堆栈的实现
2013-06-01 20:59:43原题:设有两个栈S1和S2,都采用顺序表示,并且共享一个存储区V[0...分析:将两个栈底置在数组V[0:maxsize]的两端,迎面增长,只有当两个栈相遇时才会溢出,另外一个变量tag(=1,2)来表示S1和S2的操作。 #include #defin -
大话数据结构三个版本
2018-09-10 09:39:38两个大学室友毕业同时到北京工作,他们都希望租房时能找到独自住的一室户或一室一厅,可找来找去发现,实在是承受不起。 4.6栈的链式存储结构及实现 97 4.6.1栈的链式存储结构 97 4.6.2栈的链式存储结构进栈操作 98 ... -
JVM内存管理机制
2020-05-04 06:21:27jvm包括一套字节码指令集、一组寄存器、一个栈、一个垃圾回收、堆和一个存储方法域。 运行时内存模型,分为线程私有、共享数据区两大类。 线程私有 线程私有的数据区包含:程序计数器、虚拟机栈、本地方法区。 程序... -
java小知识
2017-03-23 12:26:291:当比较数值是否相等用equals()方法,当测试两个类的引用是否指向同一个对象时用== 2:栈 保存局部变量的值,1用来保存基本数据类型的值2:保存类的实例,即堆区对象的引用 3:堆,用来存放动态产生的数据,比如... -
大话数据结构
2019-01-10 16:35:22两个大学室友毕业同时到北京工作,他们都希望租房时能找到独自住的一室户或一室一厅,可找来找去发现,实在是承受不起。 4.6栈的链式存储结构及实现 97 4.6.1栈的链式存储结构 97 4.6.2栈的链式存储结构进栈操作 98 ... -
大话数据结构 程杰
2018-09-01 10:06:43两个大学室友毕业同时到北京工作,他们都希望租房时能找到独自住的一室户或一室一厅,可找来找去发现,实在是承受不起。 4.6栈的链式存储结构及实现 97 4.6.1栈的链式存储结构 97 4.6.2栈的链式存储结构进栈操作 98 ... -
《大话数据结构》( 程杰 编著)
2018-02-15 10:00:21两个大学室友毕业同时到北京工作,他们都希望租房时能找到独自住的一室户或一室一厅,可找来找去发现,实在是承受不起。 4.6栈的链式存储结构及实现 97 4.6.1栈的链式存储结构 97 4.6.2栈的链式存储结构进栈操作 98 ... -
大话数据结构(中文高清版)
2017-04-19 11:57:0989 4.2.2 进栈出栈变化形式 90 4.3 栈的抽象数据类型 91 4.4 栈的顺序存储结构及实现 92 4.4.1 栈的顺序存储结构 92 4.4.2 栈的顺序存储结构进栈操作 93 4.4.3 栈的顺序存储结构出栈操作 94 4.5 两栈共享空间 ... -
大话数据结构-程杰
2014-07-13 23:45:52两个大学室友毕业同时到北京工作,他们都希望租房时能找到独自住的一室户或一室一厅,可找来找去发现,实在是承受不起。 4.6 栈的链式存储结构及实现 97 4.6.1 栈的链式存储结构 97 4.6.2 栈的链式存储结构进栈... -
1.1.8 NFS 和 SMB 是最常见的两种 NAS(Network Attached Storage)协议,当把一个文件系统同时通过 NFS 和 SMB 协议共享给多个主机访问时,以下哪些说法是错误的 1.1.9 输入 ping IP 后敲回车,发包前会发生什么?...
-
计算机网络复习题
2014-12-29 19:01:35(2)在面向连接的TCP协议中,TCP包中有一个Window size 字段,接收方可以通过该字段告诉发送方,自己还有多少个接收缓冲区,极端情况下,当接收方不能再接收数据时,把该字段设置为0,从而发送方可以根据该字段的值... -
微软技术丛书: Windows核心编程 第5版 [美] Jeffrey Richter 等 著 - 周靖 等 译(2008.9出版, PDF格式, 附...
2019-07-22 11:40:4617.2.2 方法2:两个文件,一块缓存 17.2.3 方法3:一个文件,两块缓存 17.2.4 方法4:一个文件,零个缓存 17.3 使用内存映射文件 17.3.1 第1步:创建或打开文件内核对象 17.3.2 第2步:创建文件映射内核对象 17.3.3 ... -
操作系统(内存管理)
2009-09-20 12:55:25(映射是一个表示一一对应关系的数学术语 —— 当内存的虚拟地址有一个对应的物理地址来存储内存内容时,该内存将被映射。) 基于 UNIX 的系统有两个可映射到附加内存中的基本系统调用: brk: brk() 是一个非常... -
Oracle 数据库管理艺术:11g新特性(世界级Oracle专家权威力作)--详细书签版
2013-02-06 17:57:47本书是经典名著《oracle 10g数据库管理艺术》一书的姊妹篇,通过示例全面而又详细地讲述了oracle 11g的新特性,讲述了更改管理、数据库自动化、性能管理、故障诊断、存储管理、安全管理、性能管理、应用开发、数据... -
c语言编写单片机技巧
2009-04-19 12:15:17当开发一个较复杂而又开发时间短的项目时,用C还是用汇编开发好? 答:对于复杂而开发时间紧的项目时,可以采用C语言,但前提是要求对该MCU系统的C语言和C编译器非常熟悉,特别要注意该C编译系统所能支持的数据... -
精通Qt4编程(第二版)源代码
2014-01-19 13:07:18\两年前,当我们准备在Linux系统下开发GUI应用软件时,首先想到的就是选择一个GUI应用框架来简化开发。在三大GUI框架GTK+、Qt和wxWidgets 之间,我们选择了Qt 4工具包。作为重量级桌面系统KDE多年的坚实基础,Qt应该... -
getHiddenAlphaAnimation : 获取一个由完全显示变为不可见的透明度渐变动画 getShowAlphaAnimation : 获取一个由不可见变为完全显示的透明度渐变动画 getLessenScaleAnimation : 获取一个缩小动画 ...
-
精通qt4编程(源代码)
2010-03-17 19:10:40\两年前,当我们准备在Linux系统下开发GUI应用软件时,首先想到的就是选择一个GUI应用框架来简化开发。在三大GUI框架GTK+、Qt和wxWidgets 之间,我们选择了Qt 4工具包。作为重量级桌面系统KDE多年的坚实基础,Qt应该... -
《CSDN开发助手》是一款依托开发者社区开发的小工具,运营得当,会有极好的发展前景,有人说《CSDN开发助手》就是一个缝合怪,但如果《CSDN开发助手》愿意把 tampermonkey 的功能也能缝合进来,真的会成为一款老少皆...
-
Visual C++ 2010入门经典(第5版)--详细书签版
2012-10-16 21:04:29·分享c++程序的错误查找技术,并介绍通用的调试原则讨论每一个windows应用程序的结构和基本元素 ·举例说明如何使用mfc开发本地windows应用程序 ·指导读者用c++和c++/cli设计和创建大量的windows应用程序 ... -
Visual C++ 2010入门经典(第5版)--源代码及课后练习答案
2012-12-15 16:45:23·分享c++程序的错误查找技术,并介绍通用的调试原则讨论每一个windows应用程序的结构和基本元素 ·举例说明如何使用mfc开发本地windows应用程序 ·指导读者用c++和c++/cli设计和创建大量的windows应用程序 ... -
Java开发技术大全 电子版
2013-04-10 12:44:5510.3带两个类型参数的泛型类308 10.4有界类型309 10.5通配符参数311 10.6泛型方法313 10.7泛型接口315 10.8泛型类的继承317 10.8.1以泛型类为父类317 10.8.2以非泛型类为父类319 10.8.3运行时类型识别320 ...