Java深入了解數據結構之棧與隊列的詳解
更新時間：2022年01月27日 16:49:16 作者：/少司命
這篇文章主要介紹了Java數據結構中的棧與隊列,在Java的時候，對于棧與隊列的應用需要熟練的掌握，這樣才能夠確保Java學習時候能夠有扎實的基礎能力。本文小編就來詳細說說Java中的棧與隊列,需要的朋友可以參考一下
一，棧
1，概念
在我們軟件應用 ，棧這種后進先出數據結構的應用是非常普遍的。比如你用瀏 覽器上網時不管什么瀏覽器都有 個"后退"鍵，你點擊后可以接訪問順序的逆序加載瀏覽過的網頁。
很多類似的軟件，比如 Word Photoshop 等文檔或圖像編 軟件中 都有撤銷 )的操作，也是用棧這種方式來實現(xiàn)的，當然不同的軟件具體實現(xiàn)會有很大差異，不過原理其實都是一樣的。
棧( stack )是限定僅在表尾進行插入和刪除的線性表
棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧 頂，另一端稱為棧底。棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。
2，棧的操作
壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據在棧頂。
3，棧的實現(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，實現(xiàn)mystack
public class MyStack<T> {
private T[] elem;//數組
private int top;//當前可以存放數據元素的下標-》棧頂指針
public MyStack() {
this.elem = (T[])new Object[10];
}
/**
* 入棧操作
* @param item 入棧的元素
*/
public void push(T item) {
//1、判斷當前棧是否是滿的
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 static void main(String[] args) {
MyStack<Integer> myStack = new MyStack<>();
myStack.push(1);
myStack.push(2);
myStack.push(3);
System.out.println(myStack.peek());
System.out.println(myStack.pop());
System.out.println(myStack.pop());
System.out.println(myStack.pop());
System.out.println(myStack.empty());
System.out.println("============================");
MyStack<String> myStack2 = new MyStack<>();
myStack2.push("hello");
myStack2.push("word");
myStack2.push("thank");
System.out.println(myStack2.peek());
System.out.println(myStack2.pop());
System.out.println(myStack2.pop());
System.out.println(myStack2.pop());
System.out.println(myStack2.empty());
}
二，隊列
1，概念
像移動、聯(lián)通、電信等客服電話，客服人員與客戶相比總是少數，在所有的客服人員都占線的情況下，客戶會被要求等待，直到有某個客服人員空下來，才能讓最先等待的客戶接通電話。這里也是將所有當前撥打客服電話的客戶進行了排隊處理。
操作系統(tǒng)和客服系統(tǒng)中，都是應用了種數據結構來實現(xiàn)剛才提到的先進先出的排隊功能，這就是隊列。
隊列(queue) 是只允許在一端進行插入操作，而在另一端進行刪除操作的線性表
隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列具有先進先出FIFO(First In First Out) 入隊列：進行插入操作的一端稱為隊尾（Tail/Rear） 出隊列：進行刪除操作的一端稱為隊頭 （Head/Front）
2，隊列的實現(xiàn)
①入隊
public static void main(String[] args) {
Deque<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
}②出隊
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());
}
③獲取隊首元素
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，實現(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;
//入隊
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;
}
}
//出隊
public int poll() {
//1判斷是否為空的
if(isEmpty()) {
throw new UnsupportedOperationException("隊列為空！");
}
//this.first = this.first.next;
int ret = this.first.getVal();
this.first = this.first.getNext();
return ret;
}
//得到隊頭元素但是不刪除
public int peek() {
//不要移動first
if(isEmpty()) {
throw new UnsupportedOperationException("隊列為空！");
}
return this.first.getVal();
}
//隊列是否為空
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());
}
到此這篇關于Java深入了解數據結構之棧與隊列的詳解的文章就介紹到這了,更多相關Java 棧與隊列 內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了解析idea內嵌瀏覽器翻譯的相關知識，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-10-10
這篇文章主要介紹了超個性修改SpringBoot項目的啟動banner的方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-07-07
這篇文章主要介紹了Spring為IOC容器注入Bean的五種方式詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-10-10
Python實現(xiàn)filter函數實現(xiàn)字符串切分
這篇文章主要介紹了Python實現(xiàn)filter函數實現(xiàn)字符串切分,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-03-03
mybatis3中@SelectProvider傳遞參數方式
這篇文章主要介紹了mybatis3中@SelectProvider傳遞參數方式。具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
SpringBoot中快速實現(xiàn)郵箱發(fā)送代碼解析
這篇文章主要介紹了SpringBoot中快速實現(xiàn)郵箱發(fā)送代碼解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-08-08
java 反射getClass .class 的使用方法示例
這篇文章主要介紹了java 反射getClass .class 的使用方法,結合實例形式分析了java類反射機制的相關操作技巧,需要的朋友可以參考下2019-11-11
java實現(xiàn)Spring在XML配置java類的方法
下面小編就為大家?guī)硪黄猨ava實現(xiàn)Spring在XML配置java類的方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-11-11
這篇文章主要介紹了Java 圖片復制功能實現(xiàn)過程解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-10-10
用intellij Idea加載eclipse的maven項目全流程(圖文)
這篇文章主要介紹了用intellij Idea加載eclipse的maven項目全流程(圖文)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-12-12