久久久久久久999_99精品久久精品一区二区爱城_成人欧美一区二区三区在线播放_国产精品日本一区二区不卡视频_国产午夜视频_欧美精品在线观看免费

標題: 數據結構=>隊列（JAVA實現） [打印本頁]

作者: liuyy 時間: 2015-1-11 20:19
標題: 數據結構=>隊列（JAVA實現）
隊列又是一種比較特殊的線性表，和棧一樣在線性表的基礎上進行了一些限制操作。就是隊列了。顧名思義，隊列就是咱們排隊買火車票一樣，排在最前面的先買到，排到后面的后買到。先進先出、后進后出。
隊列的操作
隊列的操作一般包括：進隊列、出隊列，訪問隊列頭元素、刪除隊列頭元素、判斷隊列是否為空、獲得隊列大小這些核心操作。
隊列的順序實現
和棧結構一樣隊列也有兩種實現方式相對于順序實現方式，鏈式實現相對比較簡單，只需要利用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();
}

}

歡迎光臨 (http://m.zg4o1577.cn/bbs/)