Java數(shù)據(jù)結(jié)構(gòu)之棧與隊(duì)列實(shí)例詳解
一，棧
1，概念
在我們軟件應(yīng)用 ，棧這種后進(jìn)先出數(shù)據(jù)結(jié)構(gòu)的應(yīng)用是非常普遍的。比如你用瀏 覽器上網(wǎng)時(shí)不管什么瀏覽器都有 個(gè)"后退"鍵，你點(diǎn)擊后可以接訪問(wèn)順序的逆序加載瀏覽過(guò)的網(wǎng)頁(yè)。
?
很多類似的軟件，比如 Word Photoshop 等文檔或圖像編 軟件中 都有撤銷 )的操作，也是用棧這種方式來(lái)實(shí)現(xiàn)的，當(dāng)然不同的軟件具體實(shí)現(xiàn)會(huì)有很大差異，不過(guò)原理其實(shí)都是一樣的。
棧( stack )是限定僅在表尾進(jìn)行插入和刪除的線性表
棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧 頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則。
2，棧的操作
壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)在棧頂。
3，棧的實(shí)現(xiàn)
①入棧
?
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
int ret = stack.push(4);
System.out.println(ret);
}
②出棧
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
int ret1 = stack.pop();
int ret2 = stack.pop();
System.out.println(ret1);
System.out.println(ret2);
}
③獲取棧頂元素
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
int ret1 = stack.pop();
int ret2 = stack.pop();
int ret3 = stack.peek();
System.out.println(ret1);
System.out.println(ret2);
System.out.println(ret3);
}
④判斷棧是否為空
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
int ret1 = stack.pop();
int ret2 = stack.pop();
int ret3 = stack.peek();
System.out.println(ret1);
System.out.println(ret2);
System.out.println(ret3);
stack.pop();
boolean flag = stack.empty();
System.out.println(flag);
}
?4，實(shí)現(xiàn)mystack
public class MyStack<T> {
private T[] elem;//數(shù)組
private int top;//當(dāng)前可以存放數(shù)據(jù)元素的下標(biāo)-》棧頂指針
public MyStack() {
this.elem = (T[])new Object[10];
}
/**
* 入棧操作
* @param item 入棧的元素
*/
public void push(T item) {
//1、判斷當(dāng)前棧是否是滿的
if(isFull()){
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
//2、elem[top] = item top++;
this.elem[this.top++] = item;
}
public boolean isFull(){
return this.elem.length == this.top;
}
/**
* 出棧
* @return 出棧的元素
*/
public T pop() {
if(empty()) {
throw new UnsupportedOperationException("棧為空！");
}
T ret = this.elem[this.top-1];
this.top--;//真正的改變了top的值
return ret;
}
/**
* 得到棧頂元素，但是不刪除
* @return
*/
public T peek() {
if(empty()) {
throw new UnsupportedOperationException("棧為空！");
}
//this.top--;//真正的改變了top的值
return this.elem[this.top-1];
}
public boolean empty(){
return this.top == 0;
}
}
public class MyStack<T> {
private T[] elem;//數(shù)組
private int top;//當(dāng)前可以存放數(shù)據(jù)元素的下標(biāo)-》棧頂指針
public MyStack() {
this.elem = (T[])new Object[10];
}
/**
* 入棧操作
* @param item 入棧的元素
*/
public void push(T item) {
//1、判斷當(dāng)前棧是否是滿的
if(isFull()){
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
//2、elem[top] = item top++;
this.elem[this.top++] = item;
}
public boolean isFull(){
return this.elem.length == this.top;
}
/**
* 出棧
* @return 出棧的元素
*/
public T pop() {
if(empty()) {
throw new UnsupportedOperationException("棧為空！");
}
T ret = this.elem[this.top-1];
this.top--;//真正的改變了top的值
return ret;
}
/**
* 得到棧頂元素，但是不刪除
* @return
*/
public T peek() {
if(empty()) {
throw new UnsupportedOperationException("棧為空！");
}
//this.top--;//真正的改變了top的值
return this.elem[this.top-1];
}
public boolean empty(){
return this.top == 0;
}
}
二，隊(duì)列
1，概念
像移動(dòng)、聯(lián)通、電信等客服電話，客服人員與客戶相比總是少數(shù)，在所有的客服人員都占線的情況下，客戶會(huì)被要求等待，直到有某個(gè)客服人員空下來(lái)，才能讓最先等待的客戶接通電話。這里也是將所有當(dāng)前撥打客服電話的客戶進(jìn)行了排隊(duì)處理。
操作系統(tǒng)和客服系統(tǒng)中，都是應(yīng)用了種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)剛才提到的先進(jìn)先出的排隊(duì)功能，這就是隊(duì)列。
隊(duì)列(queue) 是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表
隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出FIFO(First In First Out) 入隊(duì)列：進(jìn)行插入操作的一端稱為隊(duì)尾（Tail/Rear） 出隊(duì)列：進(jìn)行刪除操作的一端稱為隊(duì)頭 （Head/Front）
?2，隊(duì)列的實(shí)現(xiàn)
①入隊(duì)
public static void main(String[] args) {
Deque<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
}
②出隊(duì)
public static void main(String[] args) {
Deque<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
System.out.println(queue.poll());
System.out.println(queue.poll());
}
③獲取隊(duì)首元素
public static void main(String[] args) {
Deque<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println("-----------------");
System.out.println(queue.peek());
}
?3，實(shí)現(xiàn)myqueue
class Node {
private int val;
private Node next;
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Node(int val) {
this.val = val;
}
}
public class MyQueue {
private Node first;
private Node last;
//入隊(duì)
public void offer(int val) {
//尾插法 需要判斷是不是第一次插入
Node node = new Node(val);
if(this.first == null) {
this.first = node;
this.last = node;
}else {
this.last.setNext(node);//last.next = node;
this.last = node;
}
}
//出隊(duì)
public int poll() {
//1判斷是否為空的
if(isEmpty()) {
throw new UnsupportedOperationException("隊(duì)列為空！");
}
//this.first = this.first.next;
int ret = this.first.getVal();
this.first = this.first.getNext();
return ret;
}
//得到隊(duì)頭元素但是不刪除
public int peek() {
//不要移動(dòng)first
if(isEmpty()) {
throw new UnsupportedOperationException("隊(duì)列為空！");
}
return this.first.getVal();
}
//隊(duì)列是否為空
public boolean isEmpty() {
return this.first == null;
}
}
public static void main(String[] args) {
MyQueue myQueue = new MyQueue();
myQueue.offer(1);
myQueue.offer(2);
myQueue.offer(3);
System.out.println(myQueue.peek());
System.out.println(myQueue.poll());
System.out.println(myQueue.poll());
System.out.println(myQueue.poll());
System.out.println(myQueue.isEmpty());
}
棧、隊(duì)列與數(shù)組的區(qū)別？
A: 棧、隊(duì)列和優(yōu)先級(jí)隊(duì)列與數(shù)組主要有如下三個(gè)區(qū)別：
A: (一)程序員工具?
數(shù)組和其他的結(jié)構(gòu)（棧、隊(duì)列、鏈表、樹(shù)等等）都適用于數(shù)據(jù)庫(kù)應(yīng)用中作為數(shù)據(jù)記錄。它們常用于記錄那些對(duì)應(yīng)于現(xiàn)實(shí)世界的對(duì)象和活動(dòng)的數(shù)據(jù)，如職員檔案等，這些結(jié)構(gòu)便于數(shù)據(jù)的訪問(wèn)：它們易于進(jìn)行插入、刪除和查找特定數(shù)據(jù)項(xiàng)的操作。?
然而，本篇要講解的數(shù)據(jù)結(jié)構(gòu)和算法更多的是作為程序員的工具來(lái)運(yùn)用。它們主要作為構(gòu)思算法的輔助工具，而不是完全的數(shù)據(jù)存儲(chǔ)工具。這些數(shù)據(jù)結(jié)構(gòu)的生命周期比那些數(shù)據(jù)庫(kù)類型的結(jié)構(gòu)要短得多。在程序操作執(zhí)行期間它們才被創(chuàng)建，通常用它們?nèi)?zhí)行某項(xiàng)特殊的任務(wù)；當(dāng)完成任務(wù)之后，它們則被銷毀。
A: (二)受限訪問(wèn)?
在數(shù)組中，若知道數(shù)據(jù)項(xiàng)的下標(biāo)，便可以立即訪問(wèn)該數(shù)據(jù)項(xiàng)；而在本篇的數(shù)據(jù)結(jié)構(gòu)中，訪問(wèn)是受限制的，即在特定時(shí)刻只有一個(gè)數(shù)據(jù)項(xiàng)可以被讀取或者刪除。?
這些結(jié)構(gòu)接口的設(shè)計(jì)增強(qiáng)了這種受限訪問(wèn)，訪問(wèn)其他數(shù)據(jù)項(xiàng)理論上是不允許的。
A: (三)更加抽象?
棧、隊(duì)列和優(yōu)先隊(duì)列是比數(shù)組和其他數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)更為抽象的結(jié)構(gòu)。主要是通過(guò)接口對(duì)棧、隊(duì)列和優(yōu)先隊(duì)列進(jìn)行定義，接口表明了它們可以完成的操作，而主要實(shí)現(xiàn)機(jī)制對(duì)用戶來(lái)說(shuō)是不可見(jiàn)的。?
例如：棧的實(shí)現(xiàn)機(jī)制可以用數(shù)組實(shí)現(xiàn)，本篇的示例就是這樣處理的，但它也可以用鏈表來(lái)實(shí)現(xiàn)。優(yōu)先級(jí)隊(duì)列的內(nèi)部實(shí)現(xiàn)可以用數(shù)組或一種特別的樹(shù)-堆來(lái)實(shí)現(xiàn)。
總結(jié)
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之棧與隊(duì)列的文章就介紹到這了,更多相關(guān)Java數(shù)據(jù)結(jié)構(gòu)棧與隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- Java 棧與隊(duì)列超詳細(xì)分析講解
- Java?棧與隊(duì)列實(shí)戰(zhàn)真題訓(xùn)練
- 一起來(lái)學(xué)習(xí)Java的棧和隊(duì)列
- Java棧和基礎(chǔ)隊(duì)列的實(shí)現(xiàn)詳解
- Java 棧和隊(duì)列的相互轉(zhuǎn)換詳解
- Java深入了解數(shù)據(jù)結(jié)構(gòu)之棧與隊(duì)列的詳解
- Java數(shù)據(jù)結(jié)構(gòu)專題解析之棧和隊(duì)列的實(shí)現(xiàn)
- Java使用跳轉(zhuǎn)結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列和棧流程詳解
相關(guān)文章
喜歡玩游戲的有福啦,文中有非常詳細(xì)的開(kāi)發(fā)框架,按著框架來(lái)實(shí)現(xiàn)就好啦.而且24點(diǎn)游戲是經(jīng)典的紙牌益智游戲.,需要的朋友可以參考下2021-05-05
Java中對(duì)List去重 Stream去重的解決方法
這篇文章主要介紹了Java中對(duì)List去重, Stream去重的問(wèn)題解答，文中給大家介紹了Java中List集合去除重復(fù)數(shù)據(jù)的方法，需要的朋友可以參考下2018-04-04
設(shè)計(jì)模式（Design?pattern）代表了最佳的實(shí)踐，通常被有經(jīng)驗(yàn)的面向?qū)ο蟮能浖_(kāi)發(fā)人員所采用。設(shè)計(jì)模式是軟件開(kāi)發(fā)人員在軟件開(kāi)發(fā)過(guò)程中面臨的一般問(wèn)題的解決方案。本篇介紹設(shè)計(jì)模式七大原則之一的開(kāi)閉原則2022-02-02
這篇文章主要介紹了如何基于JAVA讀取yml配置文件指定key內(nèi)容,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-01-01
這篇文章主要介紹了RocketMQ事務(wù)消息機(jī)制詳解,RocketMQ服務(wù)端將消息持久化之后,向發(fā)送方返回Ack確認(rèn)消息已經(jīng)發(fā)送成功,由于消息為半事務(wù)消息,在未收到生產(chǎn)者對(duì)該消息的二次確認(rèn)前,此消息被標(biāo)記成"暫不能投遞"狀態(tài),需要的朋友可以參考下2024-01-01
idea推送項(xiàng)目到gitee中的創(chuàng)建方法
這篇文章主要介紹了idea推送項(xiàng)目到gitee中的創(chuàng)建方法,本文通過(guò)圖文實(shí)例相結(jié)合給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-08-08
struts+spring+hibernate三個(gè)框架的整合
這篇文章主要介紹了struts+spring+hibernate三個(gè)框架的整合,需要的朋友可以參考下2017-09-09
Java 網(wǎng)絡(luò)爬蟲(chóng)基礎(chǔ)知識(shí)入門解析
這篇文章主要介紹了Java 網(wǎng)絡(luò)爬蟲(chóng)基礎(chǔ)知識(shí)入門解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-10-10
這篇文章主要介紹了java右下角彈窗示例,需要的朋友可以參考下2014-04-04
本篇文章是對(duì)Java生成GUID的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05