链式队列
链式存储结构的队列称作链式队列。
链式队列的存储结构如下图所示
链式队列的实现
//结点类
public class Node {
Object element; //数据域
Node next; //指针域
//头结点的构造方法
public Node(Node nextval)
{
this.next = nextval;
}
//非头结点的构造方法
public Node(Object obj,Node nextval)
{
this.element = obj;
this.next = nextval;
}
//获得当前结点的后继结点
public Node getNext()
{
return this.next;
}
//获得当前的数据域的值
public Object getElement()
{
return this.element;
}
//设置当前结点的指针域
public void setNext(Node nextval)
{
this.next = nextval;
}
//设置当前结点的数据域
public void setElement(Object obj)
{
this.element = obj;
}
public String toString()
{
return this.element.toString();
}
}
//队列接口
public interface Queue {
//入队
public void append(Object obj) throws Exception;
//出队
public Object delete() throws Exception;
//获得队头元素
public Object getFront() throws Exception;
//判断对列是否为空
public boolean isEmpty();
}
//链式队列
public class LinkQueue implements Queue {
Node front; //队头
Node rear; //队尾
int count; //计数器
public LinkQueue()
{
init();
}
public void init()
{
front=rear=null;
count=0;
}
@Override
public void append(Object obj) throws Exception {
// TODO Auto-generated method stub
Node node = new Node(obj,null);
//如果当前队列不为空。
if(rear!=null)
{
rear.next = node; //队尾结点指向新结点
}
rear = node; //设置队尾结点为新结点
//说明要插入的结点是队列的第一个结点
if(front==null)
{
front = node;
}
count++;
}
@Override
public Object delete() throws Exception {
// TODO Auto-generated method stub
if(isEmpty())
{
new Exception("队列已空！");
}
Node node = front;
front = front.next;
count--;
return node.getElement();
}
@Override
public Object getFront() throws Exception {
// TODO Auto-generated method stub
if(!isEmpty())
{
return front.getElement();
}
else
{
return null;
}
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return count==0;
}
}
链式队列的应用
思路：设字符数组str中存放了要判断的字符串。把字符数组中的字符逐个分别存入一个队列和栈中，然后逐个出队和出栈比较出队的字符与出栈的字符是否相同，若全部相等则该字符串为回文。
//栈接口
public interface Stack {
//入栈
public void push(Object obj) throws Exception;
//出栈
public Object pop() throws Exception;
//获得栈顶元素
public Object getTop() throws Exception;
//判断栈是否为空
public boolean isEmpty();
}
public class LinkStack implements Stack {
Node head; //栈顶指针
int size; //结点的个数
public LinkStack()
{
head = null;
size = 0;
}
@Override
public Object getTop() throws Exception {
// TODO Auto-generated method stub
return head.getElement();
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return head==null;
}
@Override
public Object pop() throws Exception {
// TODO Auto-generated method stub
if(isEmpty())
{
throw new Exception("栈为空！");
}
Object obj = head.getElement();
head = head.getNext();
size--;
return obj;
}
@Override
public void push(Object obj) throws Exception {
// TODO Auto-generated method stub
head = new Node(obj,head);
size++;
}
}
public class Test {
/**
* @param args
*/
public static boolean isHuiWen(String str)throws Exception
{
int n = str.length();
LinkStack stack = new LinkStack();//创建堆栈
LinkQueue queue = new LinkQueue();//创建队列
for(int i=0;i<n;i++)
{
stack.push(str.subSequence(i, i+1)); //把字符串每个字符压进堆栈
queue.append(str.subSequence(i, i+1));//把字符串每个字符压入队列
}
while(!queue.isEmpty()&&!stack.isEmpty())
{
if(!queue.delete().equals(stack.pop()))
{
return false;
}
}
return true;
}
public static void main(String[] args)throws Exception {
String str1= "ABCDCBA" ;
String str2 = "ABCDECAB" ;
try
{
if(Test.isHuiWen(str2))
{
System.out.println(str2+":是回文！");
}
else
{
System.out.println(str2+":不是回文！");
}
}
catch(Exception ex)
{
ex.printStackTrace();
}
}
}
优先级队列
优先级队列是带有优先级的队列。
用顺序存储结构实现的优先级队列称作顺序优先级队列。
用链式存储结构存储的优先级队列称作链式优先级队列。
顺序优先级队列
顺序优先级队列和顺序循环队列相比主要有两点不同：
（1）对于顺序优先级队列来说，出队列操作不是把队头数据元素出队列，而是把队列中优先级最高的数据元素出队列。
（2）对于顺序优先级队列来说，数据元素由两部分组成，一部分是原先意义上的数据元素，另一部分是优先级。通常设计优先级为int类型的数值，并规定数值越小优先级越高。
设计顺序优先级队列（分为两个类）
数据元素类
优先级队列类
//优先级队列元素类
public class Element {
private Object element; // 数据
private int priority; // 优先级
public Element(Object obj,int priority)
{
this.element = obj;
this.priority = priority;
}
public Object getElement() {
return element;
}
public void setElement(Object element) {
this.element = element;
}
public int getPriority() {
return priority;
}
public void setPriority(int priority) {
this.priority = priority;
}
}
//队列接口
public interface Queue {
//入队
public void append(Object obj) throws Exception;
//出队
public Object delete() throws Exception;
//获得队头元素
public Object getFront() throws Exception;
//判断对列是否为空
public boolean isEmpty();
}
//优先级队列
public class PrioritySequenceQueue implements Queue {
static final int defaultSize = 10; //默认队列长度
int front ; //队头
int rear; //队尾
int count; //计数器
int maxSize; //队列最大长度
Element[] queue; //队列
public PrioritySequenceQueue()
{
init(defaultSize);
}
public PrioritySequenceQueue(int size)
{
init(size);
}
public void init(int size)
{
maxSize = size;
front= rear = 0;
count=0;
queue = new Element[size];
}
@Override
public void append(Object obj) throws Exception {
// TODO Auto-generated method stub
//如果队列已满
if(count>=maxSize)
{
throw new Exception("队列已满！");
}
queue[rear]=(Element)obj;
rear++;
count++;
}
@Override
public Object delete() throws Exception {
// TODO Auto-generated method stub
if(isEmpty())
{
throw new Exception("队列为空！");
}
//默认第一个元素为优先级最高的。
Element min = queue[0];
int minIndex = 0;
for(int i=0;i<count;i++)
{
if(queue[i].getPriority()<min.getPriority())
{
min = queue[i];
minIndex = i;
}
}
//找的优先级别最高的元素后，把该元素后面的元素向前移动。
for(int i=minIndex+1;i<count;i++)
{
queue[i-1]=queue[i]; //移动元素
}
rear--;
count--;
return min;
}
@Override
public Object getFront() throws Exception {
// TODO Auto-generated method stub
if(isEmpty())
{
throw new Exception("队列为空！");
}
//默认第一个元素为优先级最高的。
Element min = queue[0];
int minIndex = 0;
for(int i=0;i<count;i++)
{
if(queue[i].getPriority()<min.getPriority())
{
min = queue[i];
minIndex = i;
}
}
return min;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return count==0;
}
}
public class Test {
/**
* @param args
*/
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
PrioritySequenceQueue queue = new PrioritySequenceQueue();
Element temp;
//五个进程入队
queue.append(new Element(1,30));
queue.append(new Element(2,20));
queue.append(new Element(3,40));
queue.append(new Element(4,20));
queue.append(new Element(5,0));
//按照优先级出队。
System.out.println("编号 优先级");
while(!queue.isEmpty())
{
temp =(Element)queue.delete();
System.out.println(temp.getElement()+" "+temp.getPriority());
}
}
}