摘要:一前言上一篇已經(jīng)講過了鏈表實(shí)現(xiàn)單向鏈表了,它跟數(shù)組都是線性結(jié)構(gòu)的基礎(chǔ),本文主要講解線性結(jié)構(gòu)的應(yīng)用棧和隊(duì)列如果寫錯(cuò)的地方希望大家能夠多多體諒并指正哦,如果有更好的理解的方式也希望能夠在評(píng)論下留言,讓大家學(xué)習(xí)學(xué)習(xí)二數(shù)據(jù)結(jié)構(gòu)棧就是這么簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)
一、前言
上一篇已經(jīng)講過了鏈表【Java實(shí)現(xiàn)單向鏈表】了,它跟數(shù)組都是線性結(jié)構(gòu)的基礎(chǔ),本文主要講解線性結(jié)構(gòu)的應(yīng)用:棧和隊(duì)列
如果寫錯(cuò)的地方希望大家能夠多多體諒并指正哦,如果有更好的理解的方式也希望能夠在評(píng)論下留言,讓大家學(xué)習(xí)學(xué)習(xí)~
二、數(shù)據(jù)結(jié)構(gòu)【?!烤褪沁@么簡(jiǎn)單 2.1數(shù)據(jù)結(jié)構(gòu)【棧】介紹數(shù)據(jù)結(jié)構(gòu)的棧長(zhǎng)的是這個(gè)樣子:
其實(shí)非常好理解,我們將??梢?strong>看成一個(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; } }
測(cè)試:
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判斷該棧是否為空很簡(jiǎn)單,只要棧頂和棧底是同一指向,那么該棧就為空
/** * 判斷該棧是否為空 * * @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); } }
測(cè)試出棧:
多次出棧:
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ì)列】就是這么簡(jiǎn)單
數(shù)據(jù)結(jié)構(gòu)的隊(duì)列長(zhǎng)的是這個(gè)樣子:
其實(shí)隊(duì)列非常好理解,我們將隊(duì)列可以看成小朋友排隊(duì)
隊(duì)尾的小朋友到指定的地點(diǎn)了-->出隊(duì)
有新的小朋友加入了-->入隊(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ì)列的長(zhǎng)度的。
有這么一個(gè)算法:rear=(rear+1)%數(shù)組長(zhǎng)度
比如rear的下標(biāo)是2,數(shù)組的長(zhǎng)度是6,往后面移一位是3,那么rear = (rear+1) % 6,結(jié)果還是3
3.1.2初始化隊(duì)列此時(shí)隊(duì)列為空,分配了6個(gè)長(zhǎng)度給數(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ì)的邏輯也非常簡(jiǎn)單:
判斷該隊(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)用非常非常的多,這里也只是最簡(jiǎn)單的入門,理解起來也不困難。
棧:先進(jìn)后出
隊(duì)列:先進(jìn)先出
關(guān)于數(shù)據(jù)結(jié)構(gòu)這方面我就到暫時(shí)到這里為止了,都簡(jiǎn)單的入個(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
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/71049.html
摘要:在改進(jìn)前使用數(shù)組的一個(gè)缺點(diǎn)是必須聲明數(shù)組的大小,所以棧有確定的容量。待解決的問題建立一個(gè)能夠增長(zhǎng)或者縮短到任意大小的棧。下邊的圖是觀察時(shí)間開銷的另一種方式,表示了入棧操作需要訪問數(shù)組的次數(shù)。 前言 上一篇:算法分析下一篇:基本排序 本篇內(nèi)容主要是棧,隊(duì)列 (和包)的基本數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)文章里頭所有的對(duì)數(shù)函數(shù)都是以 2 為底關(guān)于性能分析,可能還是需要一些數(shù)學(xué)知識(shí),有時(shí)間可以回一下在很多...
摘要:的前部分內(nèi)容講的是棧和隊(duì)列的實(shí)現(xiàn)。學(xué)習(xí)環(huán)境在學(xué)習(xí)這門課之前,先引入的概念,即抽象數(shù)據(jù)類型。鏈表實(shí)現(xiàn)學(xué)習(xí),鏈表實(shí)現(xiàn)簡(jiǎn)單的數(shù)組實(shí)現(xiàn)鏈表實(shí)現(xiàn)簡(jiǎn)單的數(shù)組實(shí)現(xiàn)解決使用棧或者隊(duì)列時(shí),的數(shù)據(jù)類型指定問題。 Week2 的前部分內(nèi)容講的是棧和隊(duì)列的Java實(shí)現(xiàn)。學(xué)習(xí)環(huán)境:mac, inteliJ, java version 1.8.0_77 在學(xué)習(xí)這門課之前,先引入Abstract Data Type...
摘要:在這種情況下,是以其為根的樹的最后一個(gè)結(jié)點(diǎn)。來源二總結(jié)底層是紅黑樹,能夠?qū)崿F(xiàn)該集合有序如果在構(gòu)造方法中傳遞了對(duì)象,那么就會(huì)以對(duì)象的方法進(jìn)行比較。 前言 聲明,本文用得是jdk1.8 前面章節(jié)回顧: Collection總覽 List集合就這么簡(jiǎn)單【源碼剖析】 Map集合、散列表、紅黑樹介紹 HashMap就是這么簡(jiǎn)單【源碼剖析】 LinkedHashMap就這么簡(jiǎn)單【源碼剖析】 本...
摘要:棧隊(duì)列雙端隊(duì)列都是非常經(jīng)典的數(shù)據(jù)結(jié)構(gòu)。結(jié)合了棧和隊(duì)列的特點(diǎn)。因此,在中,有棧的使用需求時(shí),使用代替。迭代器之前源碼源碼之與字段中分析過,容器的實(shí)現(xiàn)中,所有修改過容器結(jié)構(gòu)的操作都需要修改字段。 棧、隊(duì)列、雙端隊(duì)列都是非常經(jīng)典的數(shù)據(jù)結(jié)構(gòu)。和鏈表、數(shù)組不同,這三種數(shù)據(jù)結(jié)構(gòu)的抽象層次更高。它只描述了數(shù)據(jù)結(jié)構(gòu)有哪些行為,而并不關(guān)心數(shù)據(jù)結(jié)構(gòu)內(nèi)部用何種思路、方式去組織。本篇博文重點(diǎn)關(guān)注這三種數(shù)據(jù)結(jié)構(gòu)...
摘要:下面總結(jié)一下集合常用的三個(gè)子類吧無序,允許為,底層是散列表紅黑樹,非線程同步有序,不允許為,底層是紅黑樹非線程同步迭代有序,允許為,底層是雙向鏈表,非線程同步從結(jié)論而言我們就可以根據(jù)自己的實(shí)際情況來使用了。 前言 聲明,本文用的是jdk1.8 前面章節(jié)回顧: Collection總覽 List集合就這么簡(jiǎn)單【源碼剖析】 Map集合、散列表、紅黑樹介紹 HashMap就是這么簡(jiǎn)單【源碼...
閱讀 2249·2021-11-22 09:34
閱讀 2012·2021-09-22 15:22
閱讀 2015·2019-08-29 15:05
閱讀 2105·2019-08-26 10:43
閱讀 3406·2019-08-26 10:26
閱讀 876·2019-08-23 18:29
閱讀 3518·2019-08-23 16:42
閱讀 1994·2019-08-23 14:46