溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這期內容當中小編將會給大家帶來有關Java中棧和隊列有什么區別，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。
Java的特點有哪些 1.Java語言作為靜態面向對象編程語言的代表，實現了面向對象理論，允許程序員以優雅的思維方式進行復雜的編程。 2.Java具有簡單性、面向對象、分布式、安全性、平臺獨立與可移植性、動態性等特點。 3.使用Java可以編寫桌面應用程序、Web應用程序、分布式系統和嵌入式系統應用程序等。
Java為什么要有集合類: 臨時存儲數據。
鏈表的本質: 對象間通過持有和引用關系互相關聯起來。
線性表: 普通線性表, 操作受限線性表(某些操作受到限制 --> 某一個線性表它的增刪改操作受到限制) --> 棧 & 隊列
（1）線性表：n個數據元素的有序序列。
①首先，線性表中元素的個數是有限的。
②其次，線性表中元素是有序的。
（2）那這個”序”指的是什么呢？
①除表頭和表尾元素外，其它元素都有唯一前驅和唯一后繼，其唯一前驅或唯一后繼確定了該元素在線性表中的位置。
②因此，線性表中，每個數據元素都有一個確定的位序，這個確定的位序我們稱之為索引。 表頭元素有唯一后繼，無前驅，表尾元素有唯一前驅，無后繼。
棧是一種”操作受限”的線性表，體現在只能在一端插入和刪除數據，符合FILO的特性。
FILO: 先進后出,
LIFO: 后進先出
線性表和哈希表在以后工作中會最常用。
棧在實際工作中不常用
應用場景：
1.函數調用棧
2.反序字符串: 實現reNumber(str)方法,反轉字符串(附代碼) 。
public class DemoStack1 {
public static void main(String[] args) {
String str = "123456789";
String reStr = reStr(str);
System.out.println(reStr);
}
// 棧先進后出
public static String reStr(String str){
MyArrayStack<Character> stack = new MyArrayStack<>();
for (int i = 0; i < str.length(); i++) {
stack.push(str.charAt(i));
}
StringBuffer buffer = new StringBuffer();
// 1 2 3 4 5 6 7 8 9
while (!stack.isEmpty()){
Character pop = stack.pop();
buffer.append(pop);
}
return buffer.toString();
}
}3.括號匹配問題: 實現judgeBracket(str)方法來判斷括號匹配 （附代碼）。
public class DemoStack2 {
public static void main(String[] args) {
String str = "public class) DemoStack2 {public static void main(String[] args) {}}";
boolean bool = judgeBracket(str);
System.out.println(bool);
}
public static boolean judgeBracket(String str){
MyArrayStack<Character> stack = new MyArrayStack<>();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
// 判斷c 是left括號, 然后入棧
if (c == '{'){
stack.push('}');
} else if (c == '['){
stack.push(']');
}else if (c == '('){
stack.push(')');
} else if (c == '}' || c == ')' || c == ']'){
Character pop = stack.pop();
if (c != pop){// 不匹配
return false;
}
}
}
return stack.isEmpty();
}
}4.編譯器利用棧實現表達式求值
5.瀏覽器的前進后退功能
6.利用棧實現 DFS: depth-first-search 深度優先遍歷(樹 圖)
編譯器利用棧實現表達式求值
中綴表達式: 2 + 3 * 2 給人看的 , 運算符放到中間
前綴表達式: + 2 * 3 2 運算符放到之前
后綴表達式: 2 3 2 * + 運算符放到后面
// 中綴表達式轉化為后綴:
// 遍歷中綴表達式
// 遇到操作數輸出
// 遇到操作符, 出棧, 直到遇到更低優先級的操作符, 操作符入棧
// 遍歷完成, 全部彈棧
// 中綴表達式轉化為前綴:
// 遍歷中綴表達式: 逆序遍歷
// 遇到操作數輸出: 頭插法
// 遇到操作符, 出棧, 只彈出更高優先級的操作符, 操作符入棧
// 遍歷完成, 全部彈棧
隊列也是一種”操作受限”的線性表，體現在一端插入數據在另一端刪除數據，特性是FIFO。
實現一個集合類
集合類: 數據容器
底層: 數組 or 鏈表
數據結構表現: 隊列
(1)用數組實現一個隊列。
/**
* 用數組實現一個隊列
* 集合類角度: 數據容器
* 底層: 數組
* 表示: 隊列
*/
public class MyArrayQueue <T> {
private final int MAX_CAPACITY = Integer.MAX_VALUE - 8;
private final int INIT_CAPACITY = 16;
private Object[] objs;
private int size;
private int head;// 頭的下標
private int end;// 尾的下標
public MyArrayQueue(){
objs = new Object[INIT_CAPACITY];
}
public MyArrayQueue(int initCapcity){
if (initCapcity <= 0 || initCapcity > MAX_CAPACITY) throw new IllegalArgumentException("" + initCapcity);
objs = new Object[initCapcity];
}
public boolean offer(T t){
// 如果數組滿了
if (size == objs.length){
int newLen = getLen();
grow(newLen);
}
// 可以添加
if (isEmpty()){
// 沒有任何元素存儲: 新添加的元素就是唯一的元素
objs[head] = t;
end = head;
size++;
return true;
} else {
// 原本存儲就有內容
// 尾后移一位
end = (end + 1) % objs.length;
objs[end] = t;
size++;
return true;
}
}
private void grow(int newLen) {
Object[] newArr = new Object[newLen];
for (int i = 0; i < objs.length; i++) {
int index = (head + i) % objs.length;
newArr[i] = objs[index];
}
objs = newArr;
head = 0;
end = size - 1;
}
private int getLen() {
int oldLen = objs.length;
int newLen = oldLen << 1;
// 判斷新長度是否溢出
if (newLen <= 0 || newLen > MAX_CAPACITY){
newLen = MAX_CAPACITY;
}
// 如果新長度和舊長度一樣
if (newLen == oldLen)throw new RuntimeException("stack can not add");
return newLen;
}
public T poll(){
if (isEmpty()) throw new RuntimeException("queue is empty");
if (size == 1){
// 原隊列中只剩一個元素
T oldValue = (T)objs[head];
head = 0;
end = 0;
size--;
return oldValue;
} else {
// 隊列中超過一個元素
T oldValue = (T)objs[head];
head = (head + 1) % objs.length;
size--;
return oldValue;
}
}
public T peek(){
if (isEmpty()) throw new RuntimeException("queue is empty");
return (T)objs[head];
}
public int size() {
return size;
}
public boolean isEmpty(){
return size == 0;
}
}（2）用鏈表實現一個鏈表。
public class MyLinkedQueue <T> {
private Node head;// 隊頭
private Node end; // 隊尾
private int size;
// 添加 offer
// 刪除 poll
// 查看隊頭元素 peek
public boolean offer(T t){
// 如果原隊列為空
if (isEmpty()){// 原隊列空
// 讓頭尾都指向這個新加的結點
head = new Node(t, null);
end = head;
size++;
return true;
}
// 原隊列不空
// 把這個元素添加到隊尾
end.next = new Node(t, null);
end = end.next;// end后移
size++;
return true;
}
public T poll(){
if (isEmpty()) throw new RuntimeException("queue is empty");
if (size == 1){
// 代表著, 鏈表中只有一個元素
T oldVlaue = head.value;
head = null;
end = null;
size--;
return oldVlaue;
}else {
T oldVlaue = head.value;
head = head.next;
size--;
return oldVlaue;
}
}
public T peek(){
if (isEmpty()) throw new RuntimeException("queue is empty");
return head.value;
}
public boolean isEmpty(){
return size == 0;
}
public int size(){
return size;
}
class Node{
T value;
Node next;
public Node(T value, Node next) {
this.value = value;
this.next = next;
}
}
}（1）隊列更不常用(自己寫代碼使用不常用):
（2）常見, 很多jdk源碼, 中間件的源碼上 很多地方使用了隊列
Eg:
①生產者消費者問題
生產者 – 消費者
生產者: 廚師
消費者: 吃面包的人
桌子: 放面包的地方
②線程池
線程池: 任務
生產者: 產生任務
消費者: 線程
桌子: 隊列
③生態環境:
第三方輪子: 要看懂
Maven
④消息隊列和緩存。
（3）普通隊列的應用場景是很有限的，一般在工程中用到的是阻塞隊列。
①阻塞隊列(有一個隊列, 大小一定)：常用于生產者-消費者模型中。
當隊列滿的時候，入隊列就阻塞。
當隊列空的時候，出隊列就阻塞。
②利用隊列實現 BFS:breadth first search 廣度優先搜索/ 遍歷 ()
上述就是小編為大家分享的Java中棧和隊列有什么區別了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
