數(shù)據(jù)結(jié)構(gòu)（一）數(shù)組實(shí)現(xiàn)一個(gè)簡(jiǎn)單的ArrayList
數(shù)據(jù)結(jié)構(gòu)（二）鏈表實(shí)現(xiàn)LinkedList
數(shù)據(jù)結(jié)構(gòu)（三）用兩種方式簡(jiǎn)單實(shí)現(xiàn)棧
數(shù)據(jù)結(jié)構(gòu)（四）棧和隊(duì)列的簡(jiǎn)單應(yīng)用
數(shù)據(jù)結(jié)構(gòu)（五）用兩種方式簡(jiǎn)單實(shí)現(xiàn)隊(duì)列
數(shù)據(jù)結(jié)構(gòu)（六）BST二分搜索樹(shù)（上）
數(shù)據(jù)結(jié)構(gòu)（六）BST二分搜索樹(shù)（下）
數(shù)據(jù)結(jié)構(gòu)（七）兩種方式實(shí)現(xiàn)set
數(shù)據(jù)結(jié)構(gòu)（八）兩種方式實(shí)現(xiàn)map
數(shù)據(jù)結(jié)構(gòu)（九）set解決LeetCode349號(hào)問(wèn)題
概念
隊(duì)列（queue）：只允許在一端進(jìn)行插入操作断楷，而在另一端進(jìn)行刪除操作的線(xiàn)性表燃乍。
隊(duì)列是一種先進(jìn)先出（First In First Out）的線(xiàn)性表痕钢，簡(jiǎn)稱(chēng)FIFO挑童。
允許插入的一端稱(chēng)為隊(duì)尾，允許刪除的一端稱(chēng)為隊(duì)頭
實(shí)現(xiàn)隊(duì)列的簡(jiǎn)單的幾個(gè)方法：
public interface Queue<E> {
int getSize();
boolean isEmpty();
//插入隊(duì)列
void enqueue(E e);
//刪除隊(duì)列隊(duì)首元素
E dequeue();
/ /獲取隊(duì)首元素
E getFront();
}
實(shí)現(xiàn)隊(duì)列
1.array實(shí)現(xiàn)隊(duì)列源碼如下：
public class ArrayQueue<E> implements Queue<E>{
private Array<E> array;
public ArrayQueue(int capacity){
array = new Array<>(capacity);
}
public ArrayQueue(){
array = new Array<>();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
public int getCapacity(){
return array.getCapacity();
}
@Override
public void enqueue(E e) {
array.addLast(e);
}
@Override
public E dequeue() {
return array.removeFirst();
}
@Override
public E getFront() {
return array.getFirst();
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("queue ");
res.append("front [");
for (int i = 0; i<array.getSize() ; i ++){
res.append(array.get(i));
if (i != array.getSize() - 1){
res.append(",");
}
}
res.append("] tail");
return res.toString();
}
public static void main(String[] args) {
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
for (int i = 0; i < 10; i++) {
arrayQueue.enqueue(i);
System.out.println(arrayQueue);
if (i % 3 == 2){
arrayQueue.dequeue();
System.out.println(arrayQueue);
}
}
}
}
這幾個(gè)方法很簡(jiǎn)單沒(méi)有什么需要解釋的糕非，array里直接實(shí)現(xiàn)了蒙具。下邊我們來(lái)看看鏈表實(shí)現(xiàn)隊(duì)列
2.鏈表實(shí)現(xiàn)隊(duì)列
public class LinkedListQueue<E> implements Queue<E> {
private class Node {
private E e;
private Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
public Node() {
this(null, null);
}
@Override
public String toString() {
return e.toString();
}
}
private Node head, tail;
private int size = 0;
public LinkedListQueue() {
head = null;
tail = null;
size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void enqueue(E e) {
if (tail == null) {
tail = new Node(e);
head = tail;
} else {
tail.next = new Node(e);
tail = tail.next;
}
size++;
}
@Override
public E dequeue() {
if (isEmpty()) {
throw new IllegalArgumentException("can not dequeue from a empty queue");
}
Node retNode = head;
head = head.next;
retNode.next = null;
if (head == null) {
tail = null;
}
size--;
return retNode.e;
}
@Override
public E getFront() {
if (isEmpty()) {
throw new IllegalArgumentException("can not dequeue from a empty queue");
}
return head.e;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("queue :front ");
Node cur = head;
while (cur.next != null) {
res.append(cur.e);
cur = cur.next;
}
res.append("NULL tail");
return res.toString();
}
這里定義了一個(gè)頭節(jié)點(diǎn)，一個(gè)尾節(jié)點(diǎn)朽肥，
- enqueue插入元素的時(shí)候先判斷當(dāng)前鏈表是否為空店量，如果為空，這個(gè)元素的節(jié)點(diǎn)賦值給頭尾節(jié)點(diǎn)鞠呈；如果鏈表不為空融师，創(chuàng)建一個(gè)節(jié)點(diǎn)插入到尾結(jié)點(diǎn)，把尾結(jié)點(diǎn)賦值成剛才創(chuàng)建的節(jié)點(diǎn)蚁吝。
- dequeue 首先判斷一下這個(gè)鏈表是否為空旱爆，如果是空的則拋一個(gè)異常，如果不為空就然后創(chuàng)建一個(gè)臨時(shí)節(jié)點(diǎn)把頭節(jié)點(diǎn)賦值給他窘茁，頭結(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)怀伦，臨時(shí)節(jié)點(diǎn)賦值為null；如果刪除之前鏈表里只有一個(gè)節(jié)點(diǎn)山林，那么刪除之后鏈表就為空了房待，頭尾節(jié)點(diǎn)都為null，所以后邊加了一個(gè)判斷。
- getFront 獲取頭結(jié)點(diǎn)的元素這個(gè)方法很簡(jiǎn)單桑孩，只需要判斷一下當(dāng)前鏈表是否為空拜鹤。
- toString方法也很簡(jiǎn)單，只是要在頭和尾節(jié)點(diǎn)拼接一寫(xiě)我們可以看清楚的提示性文字流椒，剩下的就是遍歷一下鏈表敏簿。
到這里兩種隊(duì)列的實(shí)現(xiàn)方式已經(jīng)介紹完了，下邊會(huì)為大家分析一下他們的時(shí)間復(fù)雜度宣虾。希望大家多多支持惯裕。
