隊列、連結清單
本總結主要是以“尚矽谷Java算法教程”的學習教程為主,加上一些個人的了解
目錄
- 隊列、連結清單
-
- 隊列
- 環形隊列
- 連結清單
-
- 單連結清單
- 雙向連結清單
- 單向環形連結清單(實作約瑟夫環)
隊列
-
隊列介紹
隊列是個有序清單,可以用數組和連結清單表示
遵循先入先出原則
示意圖如下:
-
數組模拟隊列
實作功能:出隊列、顯示隊列、檢視隊列頭元素
- 代碼實作:
package datastructure.queue;
import java.util.Scanner;
public class ArrayQueueDemo {
public static void main(String[] args) {
//測試一把
//建立一個隊列
ArrayQueue queue = new ArrayQueue(3);
char key = ' '; //接收使用者輸入
Scanner scanner = new Scanner(System.in);//
boolean loop = true;
//輸出一個菜單
while(loop) {
System.out.println("s(show): 顯示隊列");
System.out.println("e(exit): 退出程式");
System.out.println("a(add): 添加資料到隊列");
System.out.println("g(get): 從隊列取出資料");
System.out.println("h(head): 檢視隊列頭的資料");
key = scanner.next().charAt(0);//接收一個字元
switch (key) {
case 's':
queue.show();
break;
case 'a':
System.out.println("輸出一個數");
int value = scanner.nextInt();
queue.add(value);
break;
case 'g': //取出資料
try {
int res = queue.get();
System.out.printf("取出的資料是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': //檢視隊列頭的資料
try {
int res = queue.headQueue();
System.out.printf("隊列頭的資料是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': //退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程式退出~~");
}
}
// 使用數組模拟隊列-編寫一個ArrayQueue類
class ArrayQueue {
private int maxSize; // 表示數組的最大容量
private int front; // 隊列頭
private int rear; // 隊列尾
private int[] arr; // 該資料用于存放資料, 模拟隊列
// 建立隊列的構造器
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
front = -1;
rear = -1;
arr = new int[maxSize];
}
// 判斷隊列是否滿
public boolean isFull() {
return rear == maxSize - 1;
}
// 判斷隊列是否為空
public boolean isEmpty() {
return front == rear;
}
//增加元素
public void add(int n) {
if (isFull()) {
System.out.println("隊列已滿,無法再加入");
return;
}
rear += 1;
arr[rear] = n;
}
//擷取隊列元素,出隊列
public int get() {
if (isEmpty()) {
throw new RuntimeException("隊列已空,無法再出列");
}
front += 1;
return arr[front];
}
//顯示隊列所有的元素,不出隊列
public void show() {
if (isEmpty()) {
System.out.println("隊列空的,沒有資料~~");
return;
}
for(int i =front+1;i<=rear;i++){
System.out.printf("arr[%d]=%d\n", i, arr[i]);
}
}
// 顯示隊列的頭資料, 注意不是取出資料
public int headQueue() {
// 判斷
if (isEmpty()) {
throw new RuntimeException("隊列空的,沒有資料~~");
}
return arr[front + 1];
}
}
環形隊列
充分利用數組,實作環形隊列(取模)
代碼實作:
package datastructure.queue;
import java.util.Scanner;
public class circleQueueDemo {
public static void main(String[] args) {
//測試一把
System.out.println("測試數組模拟環形隊列的案例~~~");
// 建立一個環形隊列
CircleArray queue = new CircleArray(4); //說明設定4, 其隊列的有效資料最大是3
char key = ' '; // 接收使用者輸入
Scanner scanner = new Scanner(System.in);//
boolean loop = true;
// 輸出一個菜單
while (loop) {
System.out.println("s(show): 顯示隊列");
System.out.println("e(exit): 退出程式");
System.out.println("a(add): 添加資料到隊列");
System.out.println("g(get): 從隊列取出資料");
System.out.println("h(head): 檢視隊列頭的資料");
key = scanner.next().charAt(0);// 接收一個字元
switch (key) {
case 's':
queue.show();
break;
case 'a':
System.out.println("輸出一個數");
int value = scanner.nextInt();
queue.add(value);
break;
case 'g': // 取出資料
try {
int res = queue.get();
System.out.printf("取出的資料是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': // 檢視隊列頭的資料
try {
int res = queue.head();
System.out.printf("隊列頭的資料是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': // 退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程式退出~~");
}
}
class CircleArray {
private int maxSize; // 表示數組的最大容量
private int front;
private int rear; // 隊列尾
private int[] arr; // 該資料用于存放資料, 模拟隊列
public CircleArray(int maxSize) {
this.maxSize = maxSize;
front = 0;
rear = 0;
arr = new int[maxSize];
}
// 判斷隊列是否滿
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
// 判斷隊列是否為空
public boolean isEmpty() {
return front == rear;
}
// 添加資料到隊列
public void add(int n) {
// 判斷隊列是否滿
if (isFull()) {
System.out.println("隊列滿,不能加入資料~");
return;
}
arr[rear] = n;
rear = (rear + 1) % maxSize;
}
// 擷取隊列的資料, 出隊列
public int get() {
// 判斷隊列是否空
if (isEmpty()) {
// 通過抛出異常
throw new RuntimeException("隊列空,不能取資料");
}
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
// 顯示隊列的所有資料
public void show() {
// 周遊
if (isEmpty()) {
System.out.println("隊列空的,沒有資料~~");
return;
}
for (int i = front; i < front + (rear + maxSize - front) % maxSize; i++)//(rear+maxSize-front)%maxSize得到的是隊列的長度
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
}
// 顯示隊列的頭資料, 注意不是取出資料
public int head() {
// 判斷
if (isEmpty()) {
throw new RuntimeException("隊列空的,沒有資料~~");
}
return arr[front];
}
}
連結清單
連結清單是以節點的方式來存儲,是鍊式存儲。
每個節點包含 data 域, next 域:指向下一個節點。
連結清單的各個節點不一定是連續存儲。
連結清單分帶頭節點的連結清單和沒有頭節點的連結清單,根據實際的需求來确定。
單連結清單
結構如下
代碼實作案例
package datastructure.linkedlist;
import java.util.ArrayList;
import java.util.Stack;
public class SingleLinkedListDemo {
public static void main(String[] args) {
//進行測試
//先建立節點
HeroNode hero1 = new HeroNode(1, "宋江", "及時雨");
HeroNode hero2 = new HeroNode(2, "盧俊義", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吳用", "智多星");
HeroNode hero4 = new HeroNode(4, "林沖", "豹子頭");
//建立要給連結清單
SingleLinkedList singleLinkedList = new SingleLinkedList();
//加入
singleLinkedList.add(hero1);
singleLinkedList.add(hero2);
singleLinkedList.add(hero3);
singleLinkedList.add(hero4);
System.out.println("原來連結清單的情況~~");
singleLinkedList.list();
//反轉
// System.out.println("反轉後");
// reversetList2(singleLinkedList.getHead());
// singleLinkedList.list();
//檢視倒數元素
findLastIndexNode(singleLinkedList.getHead(), 2);
}
//将單連結清單反轉
public static void reversetList(HeroNode head) {
//如果目前連結清單為空,或者隻有一個節點,無需反轉,直接傳回
if (head.next == null || head.next.next == null) {
return;
}
HeroNode temp = head.next;
HeroNode newHead = new HeroNode(0, "", "");
HeroNode next = null;
while (temp != null) {
next = temp.next;
temp.next = newHead.next;
newHead.next = temp;
temp = next;
}
head.next = newHead.next;
}
//反轉方法2
//可以利用棧這個資料結構,将各個節點壓入到棧中,然後利用棧的先進後出的特點,就實作了逆序列印的效果
public static void reversetList2(HeroNode head) {
if (head.next == null) {
return;//空連結清單,不能列印
}
Stack<HeroNode> stack = new Stack<>();
HeroNode temp = head.next;
while (temp != null) {
stack.push(temp);
temp = temp.next;
}
while (stack.size() > 0) {
System.out.println(stack.pop());
}
}
//查找單連結清單中的倒數第k個結點 【新浪面試題】
//思路
//使用快慢指針
public static void findLastIndexNode(HeroNode head, int k) {
//判斷如果連結清單為空,傳回null
if (head.next == null) {
return;//沒有找到
}
HeroNode fast = head;
HeroNode slow = head;
int index = 0;
while (fast.next != null) {
index += 1;
fast = fast.next;
if (index >= k) {
slow = slow.next;
}
}
if (index<k) {
System.out.println("連結清單長度小于k,查詢不到");
} else {
System.out.println("倒數" + k + "元素為" + slow);
}
}
}
//定義SingleLinkedList 管理我們的英雄
class SingleLinkedList {
//先初始化一個頭節點, 頭節點不要動, 不存放具體的資料
private HeroNode head = new HeroNode(0, "", "");
//傳回頭節點
public HeroNode getHead() {
return head;
}
//添加節點到單向連結清單
//思路,當不考慮編号順序時
//1. 找到目前連結清單的最後節點
//2. 将最後這個節點的next 指向 新的節點
public void add(HeroNode heroNode) {
//因為head節點不能動,是以我們需要一個輔助周遊 temp
HeroNode temp = head;
//周遊連結清單,找到最後
while (temp.next != null) {
temp = temp.next;
}
temp.next = heroNode;
}
//第二種方式在添加英雄時,根據排名将英雄插入到指定位置
//(如果有這個排名,則添加失敗,并給出提示)
public void addByOrder(HeroNode heroNode) {
//因為頭節點不能動,是以我們仍然通過一個輔助指針(變量)來幫助找到添加的位置
//因為單連結清單,因為我們找的temp 是位于 添加位置的前一個節點,否則插入不了
HeroNode temp = head;
boolean flag = false; // flag标志添加的編号是否存在,預設為false
while (temp.next != null) {
if (temp.next.no > heroNode.no) {
break; //位置找到,就在temp的後面插入
} else if (temp.next.no == heroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
//不能添加,說明編号存在
System.out.printf("準備插入的英雄的編号 %d 已經存在了, 不能加入\n", heroNode.no);
} else {
heroNode.next = temp.next;
temp.next = heroNode;
temp.next = heroNode;
}
}
//修改節點的資訊, 根據no編号來修改,即no編号不能改.
//說明
//1. 根據 newHeroNode 的 no 來修改即可
public void update(HeroNode newHeroNode) {
//判斷是否空
if (head.next == null) {
System.out.println("連結清單為空~");
return;
}
//找到需要修改的節點, 根據no編号
//定義一個輔助變量
HeroNode temp = head;
boolean flag = false; //表示是否找到該節點
while (temp != null) {
if (temp.no == newHeroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else {
//沒有找到
System.out.printf("沒有找到 編号 %d 的節點,不能修改\n", newHeroNode.no);
}
}
//删除節點
//思路
//1. head 不能動,是以我們需要一個temp輔助節點找到待删除節點的前一個節點
//2. 說明我們在比較時,是temp.next.no 和 需要删除的節點的no比較
public void del(int no) {
HeroNode temp = head;
boolean flag = false; // 标志是否找到待删除節點的
while (temp.next != null) {
if (temp.next.no == no) {
//找到的待删除節點的前一個節點temp
flag = true;
break;
}
temp = temp.next; //temp後移,周遊
}
//判斷flag
if (flag) { //找到
//可以删除
temp.next = temp.next.next;
} else {
System.out.printf("要删除的 %d 節點不存在\n", no);
}
}
//顯示連結清單[周遊]
public void list() {
//判斷連結清單是否為空
if (head.next == null) {
System.out.println("連結清單為空");
return;
}
//因為頭節點,不能動,是以我們需要一個輔助變量來周遊
HeroNode temp = head.next;
while (temp != null) {
//輸出節點的資訊
System.out.println(temp);
//将temp後移, 一定小心
temp = temp.next;
}
}
}
//定義HeroNode , 每個HeroNode 對象就是一個節點
class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next; //指向下一個節點
//構造器
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}
雙向連結清單
單向連結清單,查找的方向隻能是一個方向,而雙向連結清單可以向前或者向後查找。
單向連結清單不能自我删除,需要靠輔助節點 ,而雙向連結清單,則可以自我删除,是以前面我們單連結清單删除節點,總是找到temp,temp是待删除節點的前一個節點。
代碼實作:
package datastructure.linkedlist;
public class DoubleLinkedListDemo {
}
class DoubleLinkedList {
private HeroNode2 head = new HeroNode2(0, "", "");
public HeroNode2 getHead() {
return head;
}
//添加節點到單向連結清單
public void add(HeroNode2 heroNode) {
//因為head節點不能動,是以我們需要一個輔助周遊 temp
HeroNode2 temp = head;
//周遊連結清單,找到最後
while (temp.next!= null) {
temp = temp.next;
}
temp.next = heroNode;
heroNode.pre =temp;
}
// 修改一個節點的内容, 可以看到雙向連結清單的節點内容修改和單向連結清單一樣
// 隻是 節點類型改成 HeroNode2
public void update(HeroNode2 newHeroNode) {
//判斷是否空
if (head.next == null) {
System.out.println("連結清單為空~");
return;
}
//找到需要修改的節點, 根據no編号
//定義一個輔助變量
HeroNode2 temp = head;
boolean flag = false; //表示是否找到該節點
while (temp != null) {
if (temp.no == newHeroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else {
//沒有找到
System.out.printf("沒有找到 編号 %d 的節點,不能修改\n", newHeroNode.no);
}
}
//删除
public void del(int no){
HeroNode2 temp = head;
boolean flag = false; // 标志是否找到待删除節點的
while (temp.next != null) {
if (temp.next.no == no) {
//找到的待删除節點的前一個節點temp
flag = true;
break;
}
temp = temp.next; //temp後移,周遊
}
//判斷flag
if (flag) { //找到
//可以删除
temp.pre.next = temp.next;
// 如果是最後一個節點,就不需要執行下面這句話,否則出現空指針
if (temp.next != null) {
temp.next.pre = temp.pre;
}
} else {
System.out.printf("要删除的 %d 節點不存在\n", no);
}
}
public void list()
{
//判斷連結清單是否為空
if (head.next == null) {
System.out.println("連結清單為空");
return;
}
//因為頭節點,不能動,是以我們需要一個輔助變量來周遊
HeroNode2 temp = head.next;
while (temp != null) {
//輸出節點的資訊
System.out.println(temp);
//将temp後移, 一定小心
temp = temp.next;
}
}
}
//定義HeroNode , 每個HeroNode 對象就是一個節點
class HeroNode2 {
public int no;
public String name;
public String nickname;
public HeroNode2 next; //指向下一個節點
public HeroNode2 pre;//指向上一個節點
//構造器
public HeroNode2(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}
單向環形連結清單(實作約瑟夫環)
結構如圖示
Josephu(約瑟夫環問題)
Josephu 問題為:設編号為1,2,… n的n個人圍坐一圈,約定編号為k(1<=k<=n)的人從1開始報數,數到m 的那個人出列,它的下一位又從1開始報數,數到m的那個人又出列,依次類推,直到所有人出列為止,由此産生一個出隊編号的序列。
代碼實作:
package datastructure.linkedlist;
public class Josephu {
public static void main(String[] args) {
// 測試一把看看建構環形連結清單
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5);// 加入5個小孩節點
circleSingleLinkedList.show();
//測試一把小孩出圈是否正确
circleSingleLinkedList.countBoy(1, 2, 5); // 2->4->1->5->3
}
}
class CircleSingleLinkedList {
// 建立一個first節點,目前沒有編号
private Boy first = null;
// 添加小孩節點,建構成一個環形的連結清單
public void addBoy(int nums) {
// nums 做一個資料校驗
if (nums < 1) {
System.out.println("nums的值不符合規則,請重新輸入");
return;
}
Boy temp = null;
for (int i = 1; i <= nums; i++) {
Boy boy = new Boy(i);
if (i == 1) {
first = boy;
first.next=first; // 構成環
temp = first; // 讓curBoy指向第一個小孩
} else {
temp.next=boy;
boy.next=first;
temp = boy;
}
}
}
//周遊
public void show(){
// 判斷連結清單是否為空
if (first == null) {
System.out.println("沒有任何小孩~~");
return;
}
Boy temp =first;
while(temp.next!=first){
System.out.print(temp.no+"\t");
temp=temp.next;
}
System.out.println(temp.no+"\t");
}
// 根據使用者的輸入,計算出小孩出圈的順序
/**
*
* @param startNo
* 表示從第幾個小孩開始數數
* @param countNum
* 表示數幾下
* @param nums
* 表示最初有多少小孩在圈中
*/
public void countBoy(int startNo, int countNum, int nums) {
// 先對資料進行校驗
if (first == null || startNo < 1 || startNo > nums) {
System.out.println("參數輸入有誤, 請重新輸入");
return;
}
// 建立要給輔助指針,始終指向目前位置的前一個元素
Boy pre =first;
while(pre.next!=first)
{
pre=pre.next;//初始化,指向first的前一個元素
}
//先移動到第K個元素
for(int j = 0; j < startNo - 1; j++) {
first = first.next;
pre=pre.next;
}
//當小孩報數時,讓first 和 helper 指針同時 的移動 m - 1 次, 然後出圈
//這裡是一個循環操作,知道圈中隻有一個節點
while(pre!=first){
for(int i =1;i<countNum;i++){
first = first.next;
pre=pre.next;
}
System.out.printf("小孩%d出圈\n", first.no);
first=first.next;
pre.next=first;
}
System.out.printf("小孩%d出圈\n", first.no);
}
}
class Boy{
public int no;// 編号
public Boy next; // 指向下一個節點,預設null
public Boy(int no){
this.no=no;
}
}