|
|
队列又是一种比较特殊的线性表，和栈一样在线性表的基础上进行了一些限制操作。就是队列了。顾名思义，队列就是咱们排队买火车票一样，排在最前面的先买到，排到后面的后买到。先进先出、后进后出。
队列的操作
队列的操作一般包括：进队列、出队列，访问队列头元素、删除队列头元素、判断队列是否为空、获得队列大小这些核心操作。
队列的顺序实现
和栈结构一样队列也有两种实现方式相对于顺序实现方式，链式实现相对比较简单，只需要利用Node结构，记录下队列的头Node和尾巴Node，在记录下元素个数就可以了。实现代码如下：
package dateStructer.queue;
public class MyQueue implements Queue {
/**
* 双向链表结构
*/
public class LinkNode {
// 真正的数据域
private E date;
// 记录上一个节点
private LinkNode prevLinkNode;
// 记录下一个节点
private LinkNode nextLinkNode;
public LinkNode() {
}
public LinkNode(E date, LinkNode prevLinkNode, LinkNode nextLinkNode) {
this.date = date;
this.prevLinkNode = prevLinkNode;
this.nextLinkNode = nextLinkNode;
}
}
// 结点个数
private int nodeSize;
// 头结点
private LinkNode headNode;
// 尾巴节点
private LinkNode tailNode;
public MyQueue(){
headNode = null;
tailNode = null;
}
/**
* 添加元素
*/
@Override
public boolean add(E element) {
if (nodeSize == 0) {
headNode = new LinkNode(element, null, tailNode);
}else {
if (tailNode == null) {
tailNode = new LinkNode(element, headNode, null);
headNode.nextLinkNode = tailNode;
nodeSize++;
return true;
}
LinkNode linkNode = tailNode;
tailNode = new LinkNode(element, linkNode, null);
linkNode.nextLinkNode = tailNode;
}
nodeSize++;
return true;
}
/**
* 访问队列头元素
*/
@Override
public E element() {
return headNode.date;
}
/**
* 返回头元素，不删除头元素
*/
@Override
public E peek() {
return headNode.date;
}
/**
* 返回头元素，删除头元素
*/
@Override
public E poll() {
LinkNode headNodeTemp = headNode;
E date = headNodeTemp.date;
if(headNode.nextLinkNode == null){
headNode.date = null;
headNode = null;
nodeSize--;
return date;
}else{
headNode = headNode.nextLinkNode;
if(headNode == tailNode){
tailNode = null;
}
}
nodeSize--;
return headNodeTemp.date;
}
/**
* 清除所有元素
*/
@Override
public void clear() {
LinkNode linkNodeNowTemp = headNode;
for (int i = 0; i < nodeSize; i++) {
if (linkNodeNowTemp != tailNode && linkNodeNowTemp != headNode) {
linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
linkNodeNowTemp.prevLinkNode.nextLinkNode = null;
linkNodeNowTemp.prevLinkNode.prevLinkNode = null;
linkNodeNowTemp.prevLinkNode.date = null;
linkNodeNowTemp.prevLinkNode = null;
} else if (linkNodeNowTemp == tailNode) {
linkNodeNowTemp.prevLinkNode = null;
} else if (linkNodeNowTemp == headNode) {
linkNodeNowTemp.nextLinkNode = null;
}
}
headNode = null;
tailNode = null;
nodeSize = 0;
}
/**
* 判断是否存在
*/
@Override
public boolean contains(Object object) {
LinkNode linkNodeNowTemp = headNode;
for (int i = 0; i < nodeSize; i++) {
if (object == linkNodeNowTemp.date) {
return true;
}
linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
}
return false;
}
/**
* 队列是否为空
*/
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return nodeSize == 0;
}
@Override
public int size() {
// TODO Auto-generated method stub
return nodeSize;
}
/**
* 根据索引号查找节点
*
* @param index
* @return
*/
public LinkNode findLinkNodeByIndex(int index) {
LinkNode linkNodeNowTemp = headNode;
for (int i = 0; i < nodeSize; i++) {
if (i == index) {
return linkNodeNowTemp;
}
linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
}
return null;
}
@Override
public String toString() {
StringBuffer str = new StringBuffer("[");
LinkNode linkNode = null;
for (int i = 0; i < nodeSize; i++) {
linkNode = findLinkNodeByIndex(i);
str.append("[" + linkNode.date + "],");
}
if (nodeSize > 0) {
return str.substring(0, str.lastIndexOf(",")) + "]";
}
return str.append("]").toString();
}
} |
|
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
