我的网络日志，记录生活的点点滴滴
利用双向链表实现双端队列（基于Java实现）
author: ZJ 07-9-17
1．双向链表
双向链表可以很好地解决单链表删除末节点需开销O(n)时间的问题。这类链表有一个next引用和一个prev引用分别指向它的后继节点与前驱节点。
2．哨兵
在基于双向链表节点类的实现中，在最前端和最后端设置一个哑元节点（dummy node）。这两个节点分别称作头节点（header node）和尾节点（tailer node），起哨兵的作用。也就是说它们并不存储任何实质的数据对象。
头节点的next引用指向首节点，prev引用为空；尾节点的prev引用指向末节点，next引用为空。
搞清楚头尾与首末节点的含义。头尾节点是哨兵节点，不存储实际的数据对象。首末节点为实际存储数据对象的一般节点，只不过一个在链表前端，一个在链表末端。
3．双向链表数据节点
DLNode.java
|
public class DLNode implements Position{
private Object element;
private DLNode prev;
private DLNode next;
public DLNode(){
this(null,null,null);
}
public DLNode(Object o, DLNode p, DLNode n) {
element = o;
prev = p;
next = n;
}
/*************Position Interface**********************/
public Object getElem() {
return element;
}
public Object setElem(Object o) {
Object ldElem = element;
element = o;
return oldElem;
}
/*************DoubleLinked List************************/
public DLNode getNext() {
return next;
}
public DLNode getPrev() {
return prev;
}
public void setNext(DLNode newNode) {
next = newNode;
}
public void setPrev(DLNode newNode) {
prev = newNode;
}
} |
4.双端队列
双端队列（double-ended queue）是指在队列的前端与后端都支持插入与删除操作的队列。它区别于一般意义上的队列，只能执行在前端删除后端插入操作。
5．双端队列接口
Deque.java
|
public interface Deque {
public int getSize();
public boolean isEmpty();
// to get the first element but not delete it.
public Object first() throws ExceptionQueueEmpty;
// to get the last element but not delete it.
public Object last() throws ExceptionQueueEmpty;
// to add the element to the queue head.
public void insertFirst(Object obj);
// to add the element to the queue rear.
public void insertLast(Object obj);
// to delete the element from the queue head.
public Object removeFirst() throws ExceptionQueueEmpty;
// to delete the element from the queue rear.
public Object removeLast() throws ExceptionQueueEmpty;
public void Traversal();// to traversal the queue.
} |
6．利用双向链表实现双端队列
Deque_DList.java
|
public class Deque_DLNode implements Deque{
protected DLNode head;
protected DLNode tail;
private int size;
public Deque_DLNode() {
head = new DLNode();
tail = new DLNode();
head.setNext(tail);
tail.setPrev(head);
size = 0;
}
public void Traversal() {
DLNode p = head.getNext();
while (p != tail) {
System.out.print(p.getElem() + " ");
p = p.getNext();
}
}
public Object first() throws ExceptionQueueEmpty {
if(isEmpty())
throw new ExceptionQueueEmpty("DoubleQueue Empty");
return head.getNext().getElem();
}
public int getSize() {
return size;
}
public void insertFirst(Object obj) {
DLNode second = head.getNext();
DLNode first = new DLNode(obj, head, second);
second.setPrev(first);
head.setNext(first);
size++;
}
public void insertLast(Object obj) {
DLNode second = tail.getPrev();
DLNode first = new DLNode(obj, second, tail);
second.setNext(first);
tail.setPrev(first);
size++;
}
public boolean isEmpty() {
return (0 == size) ? true : false;
}
public Object last() throws ExceptionQueueEmpty {
if(isEmpty())
throw new ExceptionQueueEmpty(
TAG:
我的栏目标题搜索日历
我的存档数据统计
RSS订阅 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
