数据结构系列教程（三）

第三讲 堆栈和队列

堆栈和队列都是特殊的线性表，他们的逻辑关系完全相同，差别是线性表的插入和删除操作不受限制，而堆栈只能在栈顶插入和删除，队列只能在队尾插入、队头删除，堆栈和队列都可以分别用顺序储存结构和链式存储结构，堆栈的操作主要有入栈、出栈、取栈顶元素、是否为空，可以设计通用接口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)，队列就是一种从队尾进入队头删除的特殊的顺序表，设计时还考虑了一种优先级队列，就是给队列中的每个元素添加一个优先级标示，出队列时按优先级从高到低的顺序进行，这就是优先级队列，在系统进程管理中的应用很广泛，这个优先级队列这里不做过多的阐述，有兴趣的同学可以研究研究，也可以和我一起探讨！下一讲：串！