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