一、前言
上一篇已經(jīng)講過了鏈表【Java實(shí)現(xiàn)單向鏈表】了蹬敲，它跟數(shù)組都是線性結(jié)構(gòu)的基礎(chǔ)榄笙，本文主要講解線性結(jié)構(gòu)的應(yīng)用：棧和隊(duì)列
如果寫錯(cuò)的地方希望大家能夠多多體諒并指正哦，如果有更好的理解的方式也希望能夠在評論下留言挖垛，讓大家學(xué)習(xí)學(xué)習(xí)～
二、數(shù)據(jù)結(jié)構(gòu)【棻牛】就是這么簡單
2.1數(shù)據(jù)結(jié)構(gòu)【椓《荆】介紹
數(shù)據(jù)結(jié)構(gòu)的棧長的是這個(gè)樣子：
其實(shí)非常好理解，我們將棽仙可以看成一個(gè)箱子
- 往箱子里面放東西叫做入棧
- 往箱子里面取東西叫做出棧
- 箱子的底部叫做棧底
- 箱子的頂部叫做棧頂
說到棧的特性哪替，肯定會(huì)有一句經(jīng)典的言語來概括：先進(jìn)后出(LIFO, Last In First Out)
- 往箱子里邊放蘋果，箱子底部的蘋果想要拿出來菇怀，得先把箱子頂部的蘋果取走才行
2.2數(shù)據(jù)結(jié)構(gòu)【椘静埃】 代碼實(shí)現(xiàn)
棧的分類有兩種：
- 靜態(tài)棧(數(shù)組實(shí)現(xiàn))
- 動(dòng)態(tài)棧(鏈表實(shí)現(xiàn))
從上一篇寫鏈表我就認(rèn)知到我的算法是有多渣了，普通的單鏈表操作也能把我繞得暈暈的爱沟。
由于我的鏈表還不是很熟库快，棧又不是很難，那么我就用鏈表來創(chuàng)建動(dòng)態(tài)棧了钥顽！
既然是用鏈表义屏，我們還是把上一篇節(jié)點(diǎn)的代碼拿過來吧：
public class Node {
//數(shù)據(jù)域
public int data;
//指針域，指向下一個(gè)節(jié)點(diǎn)
public Node next;
public Node() {
}
public Node(int data) {
this.data = data;
}
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
要鏈表用來表示棧蜂大，這次會(huì)有兩個(gè)指針：
- 棧頂
- 棧底
public class Stack {
public Node stackTop;
public Node stackBottom;
public Stack(Node stackTop, Node stackBottom) {
this.stackTop = stackTop;
this.stackBottom = stackBottom;
}
public Stack() {
}
}
2.2.1進(jìn)棧
將原本棧頂指向的節(jié)點(diǎn)交由新節(jié)點(diǎn)來指向闽铐，棧頂指向新加入的節(jié)點(diǎn)
/**
* 進(jìn)棧
*
* @param stack 棧
* @param value 要進(jìn)棧的元素
*/
public static void pushStack(Stack stack, int value) {
// 封裝數(shù)據(jù)成節(jié)點(diǎn)
Node newNode = new Node(value);
// 棧頂本來指向的節(jié)點(diǎn)交由新節(jié)點(diǎn)來指向
newNode.next = stack.stackTop;
// 棧頂指針指向新節(jié)點(diǎn)
stack.stackTop = newNode;
}
2.2.2遍歷棧
只要棧頂元素的指針不指向棧底，那么就一直輸出遍歷結(jié)果：
/**
* 遍歷棧(只要棧頂指針不指向棧底指針奶浦，就一直輸出)
*
* @param stack
*/
public static void traverse(Stack stack) {
Node stackTop = stack.stackTop;
while (stackTop != stack.stackBottom) {
System.out.println("關(guān)注公眾號(hào)：Java3y：" + stackTop.data);
stackTop = stackTop.next;
}
}
測試：
public static void main(String[] args) {
//初始化棧(無元素)
Stack stack = new Stack(new Node(), new Node());
//棧頂和棧尾是同一指向
stack.stackBottom = stack.stackTop;
//指向null
stack.stackTop.next = null;
//進(jìn)棧
pushStack(stack, 3);
pushStack(stack, 4);
pushStack(stack, 5);
traverse(stack);
}
結(jié)果：
這就符合了先進(jìn)后出的特性了～
2.2.3判斷該棧是否為空
很簡單兄墅，只要棧頂和棧底是同一指向，那么該棧就為空
/**
* 判斷該棧是否為空
*
* @param stack
*/
public static void isEmpty(Stack stack) {
if (stack.stackTop == stack.stackBottom) {
System.out.println("關(guān)注公眾號(hào)：Java3y---->該棧為空");
} else {
System.out.println("關(guān)注公眾號(hào)：Java3y---->該棧不為空");
}
}
2.2.4出棧
- 在出棧之前看看該棧是否為空澳叉，不為空才出棧...
- 將棧頂?shù)脑氐闹羔?指向下一個(gè)節(jié)點(diǎn))賦值給棧頂指針(完成出棧)
/**
* 出棧(將棧頂?shù)闹羔樦赶蛳乱粋€(gè)節(jié)點(diǎn))
* @param stack
*/
public static void popStack(Stack stack) {
// 棧不為空才能出棧
if (!isEmpty(stack)) {
//棧頂元素
Node top = stack.stackTop;
// 棧頂指針指向下一個(gè)節(jié)點(diǎn)
stack.stackTop = top.next;
System.out.println("關(guān)注公眾號(hào)：Java3y---->出棧的元素是：" + top.data);
}
}
測試出棧：
多次出棧：
2.2.5清空棧
當(dāng)時(shí)學(xué)C的時(shí)候需要釋放內(nèi)存資源隙咸，可是Java不用呀，所以棧頂指向棧底成洗，就清空棧了
/**
* 清空棧
* @param stack
*/
public static void clearStack(Stack stack) {
stack.stackTop = null;
stack.stackBottom = stack.stackTop;
}
三五督、數(shù)據(jù)結(jié)構(gòu)【隊(duì)列】就是這么簡單
數(shù)據(jù)結(jié)構(gòu)的隊(duì)列長的是這個(gè)樣子：
其實(shí)隊(duì)列非常好理解，我們將隊(duì)列可以看成小朋友排隊(duì)
- 隊(duì)尾的小朋友到指定的地點(diǎn)了-->出隊(duì)
- 有新的小朋友加入了-->入隊(duì)
相對于棧而言瓶殃，隊(duì)列的特性是：先進(jìn)先出
- 先排隊(duì)的小朋友肯定能先打到飯充包！
隊(duì)列也分成兩種：
- 靜態(tài)隊(duì)列(數(shù)組實(shí)現(xiàn))
- 動(dòng)態(tài)隊(duì)列(鏈表實(shí)現(xiàn))
這次我就使用數(shù)組來實(shí)現(xiàn)靜態(tài)隊(duì)列了。值得注意的是：往往實(shí)現(xiàn)靜態(tài)隊(duì)列遥椿，我們都是做成循環(huán)隊(duì)列
做成循環(huán)隊(duì)列的好處是不浪費(fèi)內(nèi)存資源基矮！
3.1數(shù)據(jù)結(jié)構(gòu)【隊(duì)列】 代碼實(shí)現(xiàn)
這次我們使用的是數(shù)組來實(shí)現(xiàn)靜態(tài)隊(duì)列淆储，因此我們可以這樣設(shè)計(jì)：
public class Queue {
//數(shù)組
public int [] arrays;
//指向第一個(gè)有效的元素
public int front;
//指向有效數(shù)據(jù)的下一個(gè)元素(即指向無效的數(shù)據(jù))
public int rear;
}
從上面的設(shè)計(jì)我們可以發(fā)現(xiàn)：rear并不指向最后一個(gè)有效的元素，在循環(huán)隊(duì)列中這樣設(shè)計(jì)是非常方便的家浇！因?yàn)檫@樣設(shè)計(jì)可以讓我們分得清隊(duì)頭和隊(duì)尾(不然循環(huán)隊(duì)列不斷入隊(duì)或出隊(duì)本砰，位置是變化很快的)
由于我們是循環(huán)隊(duì)列，所以front和rear值會(huì)經(jīng)常變動(dòng)钢悲，我們得把front和rear的值限定在一個(gè)范圍內(nèi)点额，不然會(huì)超出隊(duì)列的長度的。
有這么一個(gè)算法：rear=（rear+1)%數(shù)組長度
- 比如rear的下標(biāo)是2譬巫，數(shù)組的長度是6，往后面移一位是3督笆，那么
rear = （rear+1) % 6芦昔，結(jié)果還是3
3.1.2初始化隊(duì)列
此時(shí)隊(duì)列為空，分配了6個(gè)長度給數(shù)組(只能裝5個(gè)實(shí)際的數(shù)字娃肿，rear指向的是無效的位置的)
public static void main(String[] args) {
//初始化隊(duì)列
Queue queue = new Queue();
queue.front = 0;
queue.rear = 0;
queue.arrays = new int[6];
}
3.1.3判斷隊(duì)列是否滿了
如果rear指針和front指針緊挨著咕缎，那么說明隊(duì)列就滿了
/**
* 判斷隊(duì)列是否滿了，front和rear指針緊挨著料扰，就是滿了
* @param queue
* @return
*/
public static boolean isFull(Queue queue) {
if ((queue.rear + 1) % queue.arrays.length == queue.front) {
System.out.println("關(guān)注公眾號(hào)：Java3y--->此時(shí)隊(duì)列滿了凭豪！");
return true;
} else {
System.out.println("關(guān)注公眾號(hào)：Java3y--->此時(shí)隊(duì)列沒滿了！");
return false;
}
}
3.1.4入隊(duì)
- 判斷該隊(duì)列是否滿了
- 入隊(duì)的值插入到隊(duì)尾中(具體的位置就是rear指針的位置【再次聲明：rear指向的是無效元素的位置】
- rear指針移動(dòng)(再次指向無效的元素位置)
/**
* 入隊(duì)
*
* @param queue
*/
public static void enQueue(Queue queue,int value) {
// 不是滿的隊(duì)列才能入隊(duì)
if (!isFull(queue)) {
// 將新的元素插入到隊(duì)尾中
queue.arrays[queue.rear] = value;
// rear節(jié)點(diǎn)移動(dòng)到新的無效元素位置上
queue.rear = (queue.rear + 1) % queue.arrays.length;
}
}
3.1.5遍歷
只要front節(jié)點(diǎn)不指向rear節(jié)點(diǎn)晒杈，那么就可以一直輸出
/**
* 遍歷隊(duì)列
* @param queue
*
*/
public static void traverseQueue(Queue queue) {
// front的位置
int i = queue.front;
while (i != queue.rear) {
System.out.println("關(guān)注公眾號(hào)：Java3y--->" + queue.arrays[i]);
//移動(dòng)front
i = (i + 1) % queue.arrays.length;
}
}
隊(duì)列沒滿時(shí)：
隊(duì)列已滿了就插入不了了(驗(yàn)證上面的方法是否正確)：
3.1.6判斷該隊(duì)列是否為空
只要rear和front指針指向同一個(gè)位置嫂伞，那該隊(duì)列就是空的了
/**
* 判斷隊(duì)列是否空，front和rear指針相等拯钻，就是空了
* @param queue
* @return
*/
public static boolean isEmpty(Queue queue) {
if (queue.rear == queue.front) {
System.out.println("關(guān)注公眾號(hào)：Java3y--->此時(shí)隊(duì)列空的帖努！");
return true;
} else {
System.out.println("關(guān)注公眾號(hào)：Java3y--->此時(shí)隊(duì)列非空！");
return false;
}
}
3.1.7出隊(duì)
出隊(duì)的邏輯也非常簡單：
- 判斷該隊(duì)列是否為null
- 如果不為null粪般，則出隊(duì)拼余，只要front指針往后面移就是出隊(duì)了!
/**
* 出隊(duì)
*
* @param queue
*/
public static void outQueue(Queue queue) {
//判斷該隊(duì)列是否為null
if (!isEmpty(queue)) {
//不為空才出隊(duì)
int value = queue.arrays[queue.front];
System.out.println("關(guān)注公眾號(hào)：Java3y--->出隊(duì)的元素是：" + value);
// front指針往后面移
queue.front = (queue.front + 1) % queue.arrays.length;
}
}
結(jié)果：
四、總結(jié)
數(shù)據(jù)結(jié)構(gòu)的棧和隊(duì)列的應(yīng)用非常非常的多亩歹，這里也只是最簡單的入門匙监，理解起來也不困難。
- 棧：先進(jìn)后出
- 隊(duì)列：先進(jìn)先出
關(guān)于數(shù)據(jù)結(jié)構(gòu)這方面我就到暫時(shí)到這里為止了小作，都簡單的入個(gè)門亭姥，以后遇到更加復(fù)雜的再繼續(xù)開新的文章來寫～畢竟現(xiàn)在水平不夠，也無法理解更深層次的東西～數(shù)據(jù)結(jié)構(gòu)這東西是必備的顾稀，等到研究集合的時(shí)候還會(huì)來回顧它致份，或者遇到新的、復(fù)雜的也會(huì)繼續(xù)學(xué)習(xí)....
想要更加深入數(shù)據(jù)結(jié)構(gòu)的同學(xué)就得去翻閱相關(guān)的書籍咯～這僅僅是冰山一角
如果文章有錯(cuò)的地方歡迎指正础拨，大家互相交流氮块。習(xí)慣在微信看技術(shù)文章绍载，想要獲取更多的Java資源的同學(xué)，可以關(guān)注微信公眾號(hào):Java3y
