本文共 2409 字,大约阅读时间需要 8 分钟。
首先,从大的概念上来看,队列和栈都是线性表;并且它们都是只允许在端点处进行插入或者删除操作;
栈:只允许在同一端进行插入或者删除的线性表叫做栈;它是一种具有First In Last Out (或者Last In First Out)特点的表;
队列:只允许在一端进行插入、另一端进行删除操作的线性表叫做队列;它是一种具有First In First Out (或者Last In Last Out)特点的表;
按照实现的方式不同,可以分为顺序栈、链式栈以及顺序队和链式队;
由于顺序存储比较方便(自然也有其缺点:线性表的容量不能动态扩张),队列、栈常常使用顺序存储完成;
使用顺序存储的队列为了提高存储空间的利用率也可以设计为循环队列;
链式栈:
使用空栈底元素时(类似使用空头元素实现链表):
不使用空栈底元素时:
顺序栈:(涉及判别栈满的情况,设size为申请的大小)
top指向实体元素;
top指向下一个元素的存储位置:
链式队列:
使用空队首元素:
不使用空队首元素:
顺序队列:(涉及判别栈满的情况,设size为申请的大小)
一般顺序队列:
head指向队首元素
head指向队首元素的上一个位置:
以上队列:出队列时head++;入队列时tail++(指针则向前移动一位);
以上两种顺序队列会产生假满现象,即队列里还有存储空间(这些空间为已经出队列的元素原来所占的空间),但是由于判满条件使得无法继续添加元素;解决该问题的方案为设计循环队列;
所谓循环队列,即要求改变队列判满条件,从而充分利用申请的空间;从逻辑上来看,类似单向循环链表;
如果我们使用head指向队首元素,tail指向队尾元素,初始时head=0; tail=-1; 由于我们会重复利用已经出队列的元素所占用的空间(这些空间位于head的左侧),所以tail有可能在到达数组边界后因为继续入队列操作而出现在head的左侧,所以也要修改判空条件;先总结队列为空的情景,假设此时head的值为1,tail的值为3,size的值为6,即0是空的,1,2,3为队列元素,4,5为空:
所以“使用head指向队首元素,tail指向队尾元素”是行不通的;
那么我们使用head指向队首元素的上一个位置,tail指向对尾元素;并且head所在的位置不存储元素;那么同样的场景(1,2,3为队列元素,4,5为空,head此时为0,tail此时为3),我们再看:
那么如何判满呢?
当tail循环一圈(不断入队列操作)后出现在了head的左边,此时若tail+1==head,则说明如果再入队列,那么head指向的空间就要被占了,而且此时如果再允许入队列,那么head==tail,又和判空条件冲突,所以这时候是不允许再入队列的,即判满!故结合循环,判满条件为(tail+1)%6==head;
循环队列:(head指向队首元素的前一个位置,tail指向队尾元素)
出队列:head=(head+1)%size;入队列:tail=(tail+1)%size;
(这是自己使用Java语言(部分细节参考了Java集合类源码)实现的一套数据结构API,包括链表,栈、队列、树、图等内容,为算法学习提供基础,完善ing~)
转载地址:http://jumsi.baihongyu.com/