分享
 
 
 

数据结构系列教程(三)

王朝other·作者佚名  2006-10-26
窄屏简体版  字體: |||超大  

第三讲 堆栈和队列

堆栈和队列都是特殊的线性表,他们的逻辑关系完全相同,差别是线性表的插入和删除操作不受限制,而堆栈只能在栈顶插入和删除,队列只能在队尾插入、队头删除,堆栈和队列都可以分别用顺序储存结构和链式存储结构,堆栈的操作主要有入栈、出栈、取栈顶元素、是否为空,可以设计通用接口Stack..ava如下:

/**

* @author 张钰

*

*/

public interface Stack {

public void push(Object obj) throws Exception;//把数据元素obj插入堆栈

public Object pop()throws Exception;//出栈,删除栈顶元素并返回

public Object getTop()throws Exception;//获取栈顶元素

public boolean notEmpty();//判断是否为空

}

下面就不同的结构展开:

(一)顺序堆栈

具有顺序储存结构的堆栈称为顺序堆栈,顺序堆栈和顺序表的数据成员是相同的,只是顺序堆栈的入栈和出栈操作只能在当前栈顶进行,其结构可以参考下图:

栈底 栈顶

a0

a1

a2

a3

a4

satck top=5 maxStackSize-1

stack表示顺序堆栈储存数据的数组,a0、a1等表示已经入栈的数据,a0比a1先入栈,maxStackSize表示顺序堆栈数组stack的最大元素个数,top表示顺序堆栈的stack的当前栈顶的下标,设计顺序堆栈类如下SeqStack.java:

/**

* @author 张钰

*

*/

public class SeqStack implements Stack {

/*

* @see Stack#push(java.lang.Object)

*/

final int defaultSize=10;

int top;

Object[] stack;

int maxStackSize;

public SeqStack(){

initiate(defaultSize);

}

public SeqStack(int sz){

initiate(sz);

}

private void initiate(int sz) {

// 初始化

maxStackSize=sz;

top=0;

stack=new Object[maxStackSize];

}

public void push(Object obj) throws Exception {

// 插入堆栈

if(top==maxStackSize){

throw new Exception("堆栈已满!");

}

stack[top]=obj;

top++;

}

/*

* @see Stack#pop()

*/

public Object pop() throws Exception {

// 出栈

if(top==0){

throw new Exception("堆栈已空!");

}

top--;

return stack[top];

}

/*

* @see Stack#getTop()

*/

public Object getTop() throws Exception {

// 获取栈顶数据

if(top==0){

throw new Exception("堆栈已空!");

}

return stack[top-1];

}

/*

* @see Stack#notEmpty()

*/

public boolean notEmpty() {

// 判断是否为空

return (top>0);

}

}

(二) 链式堆栈

链式堆栈具有链式存储结构,用节点构造链,,每个节点由两个域组成,一个是存放数据元素的域element,另一个是存放下一个节点的对象引用域也就是指针域next,堆栈有两端,插入数据和删除元素的一端为栈顶,另一端为栈底,链式堆栈都不带头节点(大家可以思考一下为什么?),链式堆栈类的设计LinStack.java:

public class LinStack implements Stack{

Node head;//堆栈头

int size;//节点个数

public void LinStack(){

head=null;

size=0;

}

public void push(Object obj){//入栈

head=new Node(obj,head);//新节点为栈顶

}

public Object pop() throws Exception{ //出栈

if(size==0){

throw new Exception(“堆栈已空”);

}

Object obj=head.element;//取原栈顶元素

head=head.next;//原栈顶节点脱链

Size--;

Return obj;

}

public Boolean notEmpty(){

return head!=null; //是否空

}

public Object getTop(){

return head.element; //取栈顶元素

}

}

,堆栈由于其操作的特殊性而存在,在很多地方能起到独特的作用,比喻中缀表达式转换成后缀表达式,编译软件中的括号匹配问题(eclipse中就很好)都是使用堆栈的特殊性来设计算法,具体的问题大家可以和我一起交流!

下面讲讲队列,队列的特点就是从队尾插入、队头删除,也是一种特殊的线性表,队列的操作和堆栈一样主要有:入队列、出队列、取队头数据元素、是否为空,队列的接口类Queue.java可以设计如下:

/**

* @author 张钰

*

*/

public interface Queue{

public void append(Object obj) throws Exception;

public Object delete()throws Exception;

public Object getFront() throws Exception;

public Boolean notEmpty();

}

(三)顺序队列

具有顺序结构的队列就叫顺序队列,顺序队列存在假溢出问题,就是一个队列最大存储为6个元素,现在有a0 a1 a2 a3 a4 a5六个元素入队列了,然后又有a0 a1 a2三个元素出队列了,这样剩下的三个元素占据的还是队列的后三个位置,这时候要是有新的元素入队列就会出现数组越界,而事实上队列没有满,这就是假溢出问题,出现问题的原因就是队尾rear和队头front的值不能由所定义数组下界值自动转化成上界值而产生的,解决的办法就是把顺序队列所使用的储存空间构造成一个逻辑上首尾相连的循环队列,当队尾rear和队头front达到maxSize-1后,再自加1自动到0,这样就不会出现队列数组头部已空但队尾因数组下标越界而引起的溢出的假溢出问题,解决顺序循环队列的队列满和队列空状态判断问题通常三种方法:

1.少用一个储存空间,以队尾rear加1等于队头front为队列满的判断条件,即此时队列满的判断条件为:(rear+1)%maxSize=front,队列空的条件为:rear=front;

2.设置一个标志位,添加一个标志位,设标志位为tag,初始时置tag=0,每当入队列操作成功时就置tag=1,出队列操作成功时标志tag=0,那么此时队列满的判断条件是:

rear= =front && tag= =1,队列空的判断条件是:rear==front && tag= =0;

3.设置一个计数器,添加一个计数器count,初始count=0,每当入队列操作成功时count加1,每当出队列操作成功count减1,这样计数器不仅有标示功能还有计数功能,此时判断队列满的条件是:count>0 && rear= =front,队列空的条件是:count= =0;

上面三种方法很明显最好的是第三种使用计数器的方法,采用这种计数器的办法可以设计顺序循环队列的类SeqQueue.java如下:

public class SeqQueue implements Queue{

static final int defaultSize=10;

int front;

int rear;

int count;

int maxSize;

Object[] data;

public SeqQueue(){

initiate(defaultSize);

}

public SeqQueue(int sz){

initiate(sz);

}

public void initiate(int sz){

maxSize=sz;

front=rear=0;

count=0;

data=new Object[sz];

}

public void append(Object obj) throws Exception{

if(count>0 && front= =rear){

throw new Exception(“队列已满!”);

}

data[rear]=obj;

rear=(rear+1)%maxSize;

count++

}

public Object delelte() throws Exception{

if(count= =0){

throw new Exception(“队列已空!”);

}

Object temp=data[front];

front=(front+1)%maxSize;

count- -

return temp;

}

public Object getFront() throws Exception{

if(count= =0){

throw new Exception(“队列已空”);

}

return data[front];

}

public Boolean notEmpty(){

return count!=0;

}

}

以上就是顺序队列的java表示,大家可以自己做些例子测试一下,队列还有一种就是链式队列,链式队列就是具有链式结构的队列,链式队列通常设计成不带头节点的结构,结合以前的链式表可以很容易设计出链式队列的类,这个任务就留给大家了,如果有什么疑问的话可以到我们的论坛咨询(http://www.easyjf.com/bbs),队列就是一种从队尾进入队头删除的特殊的顺序表,设计时还考虑了一种优先级队列,就是给队列中的每个元素添加一个优先级标示,出队列时按优先级从高到低的顺序进行,这就是优先级队列,在系统进程管理中的应用很广泛,这个优先级队列这里不做过多的阐述,有兴趣的同学可以研究研究,也可以和我一起探讨!下一讲:串!

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有