棧：后進(jìn)先出
隊(duì)列：先進(jìn)先出
1. 棧(Stack)
1.1 概念
棧：是一種特殊的線性表，只允許在固定的一端插入或者刪除元素，一個(gè)棧包含了棧頂和棧底。只能在棧頂插入或者刪除元素。棧的底層是由數(shù)組實(shí)現(xiàn)的。
棧遵循先入后出原則，也就是先插入的元素得到后面才能刪除，后面插入的元素比先插入的元素要更早的刪除?？梢岳斫獬桑汉筮M(jìn)先出
入棧：在棧頂插入元素。
出棧：在棧頂刪除元素。
1.2 棧的使用
如下圖，棧的常用方法有：
檢查棧是否為空的意思是，看看棧里面是不是一個(gè)元素都沒有。
?棧的方法都挺簡(jiǎn)單，我就不一個(gè)個(gè)演示了，刷題的時(shí)候直接用即可
import java.util.Stack;
public class Main {
public static void main(String[] args) {
//創(chuàng)建一個(gè)棧
Stack<Integer> stack = new Stack<>();
//入棧
stack.push(1);
//看看棧頂元素但不刪除
int top = stack.peek();
System.out.println(top);
//刪除棧頂元素
stack.pop();
//如果棧不為空，就看看棧里有幾個(gè)元素
if (!stack.empty()) {
int size = stack.size();
System.out.println(size);
}
}
}
1.3 棧的模擬實(shí)現(xiàn)
既然要實(shí)現(xiàn)一個(gè)棧，那我們可以先定義一個(gè) MyStack 類，接下來只需要思考怎么完成 MyStack 類即可。
之前也說過，棧的底層是由一個(gè)數(shù)組實(shí)現(xiàn)的，所以我們可以定義一個(gè)數(shù)組，對(duì)棧進(jìn)行操作就是對(duì)數(shù)組進(jìn)行操作。
為了以后方便操作數(shù)組，我們還可以再定義一個(gè) usedSize ，用來表示數(shù)組當(dāng)前存放的元素個(gè)數(shù)。
因?yàn)槲覀兇龝?huì)還要提供 MyStack 的構(gòu)造方法，就相當(dāng)于給數(shù)組分配內(nèi)存，所以我們可以定義一個(gè)默認(rèn)容量，用來表示數(shù)組一開始的容量大小。
有了默認(rèn)容量，我們就可以把 MyStack 的構(gòu)造方法給寫出來了。
棧要實(shí)現(xiàn)以下方法：
//入棧
public void push(int val) {
}
//出棧
public int pop() {
return -1;
}
//返回棧頂元素
public int peek() {
return -1;
}
//判空
public boolean empty() {
return false;
}
//返回棧的元素個(gè)數(shù)
public int size() {
return 0;
}我們可以先挑最簡(jiǎn)單的實(shí)現(xiàn)，比如 empty 和 size。
我們先實(shí)現(xiàn) empty 方法，很簡(jiǎn)單，就是看數(shù)組有沒有元素咯，元素個(gè)數(shù)不為 0 ，說明棧不空。
再來實(shí)現(xiàn) size 方法，這個(gè)也簡(jiǎn)單，直接返回?cái)?shù)組元素個(gè)數(shù)就好啦。
再來實(shí)現(xiàn) pop 方法，出棧，就是出棧頂元素，也就是把數(shù)組的最后一個(gè)元素給刪掉，那就得先判斷數(shù)組里有沒有元素，根據(jù)這個(gè)再來進(jìn)行刪除。
usedSize-- ，之后入棧的時(shí)候會(huì)把原來的元素給覆蓋掉，相當(dāng)于是變相刪除了這個(gè)元素
再來實(shí)現(xiàn) peek 方法，這個(gè)和 pop 方法同理，只是瞄一眼棧頂元素，但是不用刪除棧頂元素。
最后再來實(shí)現(xiàn) push 方法，首先，你得看看數(shù)組滿沒滿，滿了就要擴(kuò)容，然后再來放元素。
import java.util.Arrays;
public class MyStack {
private int[] elem;
private int usedSize;//表示當(dāng)前數(shù)組存放元素個(gè)數(shù)
private static final int DEFAULT_CAPACITY = 10;//數(shù)組的默認(rèn)容量
public MyStack() {
this.elem = new int[DEFAULT_CAPACITY];
}
//判空
public boolean empty() {
return this.usedSize == 0;
}
//返回棧的元素個(gè)數(shù)
public int size() {
return this.usedSize;
}
//出棧
public int pop() {
//棧為空，刪不了
if (empty()) {
return -1;
}
//棧不為空，刪除
int top = this.elem[this.usedSize - 1];
usedSize--;
return top;
}
//返回棧頂元素
public int peek() {
//棧為空
if (empty()) {
return -1;
}
return elem[usedSize - 1];
}
//入棧
public void push(int val) {
//數(shù)組滿了，得擴(kuò)容
if (this.usedSize == this.elem.length) {
//擴(kuò)容
this.elem = Arrays.copyOf(this.elem, this.elem.length * 2);
}
this.elem[usedSize] = val;
usedSize++;
}
}1.4 棧的應(yīng)用場(chǎng)景
1. 改變?cè)氐男蛄?
1. 若進(jìn)棧序列為 1,2,3,4 ，進(jìn)棧過程中可以出棧，則下列不可能的一個(gè)出棧序列是（）
? ? ? ? ? ? ?A: 1,4,3,2? ? ? ? ? ?B: 2,3,4,1? ? ? ? ? ?C: 3,1,4,2? ? ? ? ? ? ?D: 3,4,2,1
選C
?
?
?
?
2.一個(gè)棧的初始狀態(tài)為空。現(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是（ ）。
A: 12345ABCDE? ? ? ? ?B: EDCBA54321? ? ? ? ? C: ABCDE12345? ? ? ? ? D: 54321EDCBA
選B。
20.?有效的括號(hào)
思路：直接遍歷 s ，因?yàn)槭强纯蠢ㄌ?hào)是否匹配，可以利用棧來完成，所以直接讓右括號(hào)來跟左括號(hào)匹配即可
分兩種情況，如果是左括號(hào)，那就直接入棧
如果是右括號(hào)，那就匹配，匹配之前得看看棧是不是為空，如果為空，說明就不匹配
如果匹配了，那就出棧。
最后遍歷完 s ，如果棧為空，說明全部匹配成功，返回 true。
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
//左括號(hào)
if (ch == '(' || ch == '[' || ch == '{') {
stack.push(ch);
} else {
//右括號(hào)
if (!stack.empty()) {
char top = stack.peek();
if (top == '(' && ch == ')'
|| top == '{' && ch == '}'
|| top == '[' && ch == ']') {
stack.pop();
} else {
return false;
}
} else {
//棧為空，沒有左括號(hào)
return false;
}
}
}
if (!stack.empty()) {
return false;
}
return true;
}
}150.?逆波蘭表達(dá)式求值
思路：利用棧來完成，遍歷數(shù)組，如果遇到數(shù)字，那就放進(jìn)棧里，如果遇到運(yùn)算符，就彈出棧的兩個(gè)元素，
第一個(gè)彈出的元素作為運(yùn)算符的右操作數(shù)，第二個(gè)作為左操作數(shù)，將計(jì)算完的值放入棧中
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
//運(yùn)算符
if (tokens[i].equals("+")
|| tokens[i].equals("-")
|| tokens[i].equals("*")
|| tokens[i].equals("/")) {
int b = stack.pop();
int a = stack.pop();
switch (tokens[i]) {
case "+":
stack.push(a + b);
break;
case "-":
stack.push(a - b);
break;
case "*":
stack.push(a * b);
break;
case "/":
stack.push(a / b);
break;
}
} else {
//數(shù)字
int tmp = Integer.parseInt(tokens[i]);
stack.push(tmp);
}
}
return stack.pop();
}
}JZ31 棧的壓入、彈出序列
你平常怎么判斷出棧順序的，現(xiàn)在就怎么寫這個(gè)方法，思路是差不多的。
思路：這題利用棧來完成，遍歷 push 數(shù)組，用 j 遍歷 pop 數(shù)組，先把元素放入棧里，然后如果棧不為空并且棧頂元素和 pop[ j ] 相同的話，那就出棧，然后 j 往后走。
最后看看棧是否為空，如果為空，說明全都匹配成功，就返回 true ，否則返回 false
import java.util.*;
public class Solution {
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可
*
*
* @param pushV int整型一維數(shù)組
* @param popV int整型一維數(shù)組
* @return bool布爾型
*/
public boolean IsPopOrder(int[] push, int[] pop) {
int j = 0;
Stack<Integer> stack = new Stack<>();
//用i遍歷push數(shù)組，j遍歷pop數(shù)組，
//將push數(shù)組的所有數(shù)字都放入棧中，然后再peek棧
//如果peek棧的元素和pop數(shù)組的j下標(biāo)元素相同
//就將該元素出棧
//遍歷完i后，如果棧不是空的就返回false
for (int i = 0; i < push.length; i++) {
//入棧
stack.push(push[i]);
//匹配
while (!stack.empty() && j < pop.length && stack.peek() == pop[j]) {
stack.pop();
j++;
}
}
if (stack.empty()) {
return true;
}
return false;
}
}155.?最小棧
思路：定義兩個(gè)棧，一個(gè)就是普通的棧，一個(gè)用來存放有可能是最小值的元素的棧(簡(jiǎn)稱最小棧)
構(gòu)造方法就是初始化這兩個(gè)棧，
push 方法，那就得判斷是不是第一次入棧，如果是第一次入棧，那就兩個(gè)棧都要入，如果不是第一次，那就普通棧正常入棧，而最小棧就需要判斷一下，如果要入的 val 小于等于 最小棧的棧頂元素，那就入棧。
pop 方法，得看看是不是空棧，空棧出不了。如果棧不為空，那普通棧就正常出棧，但是得看看普通棧出的元素在最小棧中是否存在，如果存在，那最小棧也得出。
top 方法，看看是不是空棧，不是就正常返回棧頂元素
getMin 方法也同理。
class MinStack {
private Stack<Integer> stack;//一個(gè)是普通棧
private Stack<Integer> minStack;//一個(gè)存有可能是最小值的棧
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if (minStack.empty()) {
//如果是第一次入棧，那么兩個(gè)棧都得入
minStack.push(val);
} else {
int tmp = minStack.peek();
//如果val小于等于minStack棧頂元素，那就入棧
if (val <= tmp) {
minStack.push(val);
}
}
}
public void pop() {
if (stack.empty()) {
return;
}
int top = stack.pop();
int tmp = minStack.peek();
if (tmp == top) {
//如果普通棧和最小棧元素相等，那就都得出棧
//不是的話就普通棧出棧
minStack.pop();
}
}
//獲取普通棧的棧頂元素
public int top() {
if (stack.empty()) {
return -1;
}
return stack.peek();
}
//獲取普通棧的棧頂元素
public int getMin() {
if (minStack.empty()) {
return -1;
}
return minStack.peek();
}
}1.5 概念區(qū)分
2. 隊(duì)列(Queue)
2.1 概念
隊(duì)列：如上圖，只能在隊(duì)尾插入元素，隊(duì)頭刪除元素，是一種特殊的線性表，遵循先進(jìn)先出原則。
2.2 隊(duì)列的使用
在Java中，Queue是個(gè)接口，底層是通過鏈表實(shí)現(xiàn)的，所以在創(chuàng)建對(duì)象的時(shí)候，必須實(shí)例化 LinkedList 對(duì)象。
Queue 的常見方法有：?
跟棧的使用方式差不多，我就不演示啦
2.3 隊(duì)列模擬實(shí)現(xiàn)
隊(duì)列可以使用順序結(jié)構(gòu)或者鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)，更推薦使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)，因?yàn)楹?jiǎn)單
和棧同理，既然要實(shí)現(xiàn)隊(duì)列，那就先定義一個(gè) MyQueue 類。
同時(shí)，既然是使用鏈表實(shí)現(xiàn)，那肯定得定義一個(gè)靜態(tài)內(nèi)部類 ListNode。
而一個(gè)隊(duì)列還有隊(duì)頭和隊(duì)尾，所以也要定義隊(duì)頭和隊(duì)尾。
因?yàn)橐獙?shí)現(xiàn)的方法里包含 isEmpty 方法，所以可以額外定義一個(gè) usedSize 來記錄隊(duì)列的元素個(gè)數(shù)
隊(duì)列要實(shí)現(xiàn)的方法有這些：
public void offer(int val) {
}
//出隊(duì)列 相當(dāng)于刪除隊(duì)尾結(jié)點(diǎn)
public int poll() {
return -1;
}
//獲取隊(duì)頭
public int peek() {
return -1;
}
public int getUsedSize() {
return 0;
}
public boolean isEmpty() {
return false;
}同樣的，我們先選擇簡(jiǎn)單的方法來實(shí)現(xiàn)，比如 getUsedSize 方法和 isEmpty 方法。
我們先實(shí)現(xiàn)?getUsedSize 方法，這個(gè)簡(jiǎn)單，直接返回 usedSize 就行。
再來實(shí)現(xiàn) isEmpty 方法，判斷隊(duì)列是否為空，就是判斷隊(duì)列里usedSize是否為零。
再來實(shí)現(xiàn) offer 方法，分兩種情況，
一種是隊(duì)列為空，說明鏈表里面還沒有元素，也就是說新增的元素是第一個(gè)元素，所以就讓 front 和 rear 都指向新增的元素即可。
第二種是隊(duì)列不為空，相當(dāng)于鏈表的頭插法。
再來實(shí)現(xiàn) poll 方法，
分兩種情況，第一種，如果隊(duì)列為空，刪不了
第二種，隊(duì)列不為空，就得判斷，隊(duì)列里面是否只有一個(gè)節(jié)點(diǎn)，如果只有一個(gè)節(jié)點(diǎn)，那刪了隊(duì)列就空了，如果不是只有一個(gè)節(jié)點(diǎn)，那就相當(dāng)于刪除尾巴節(jié)點(diǎn)。
最后實(shí)現(xiàn) peek 方法，與 poll 方法類似，先看看空不空，不為空，就直接返回 top，為空，就返回 -1。
public class MyQueue {
static class ListNode {
private int val;
private ListNode prev;
private ListNode next;
public ListNode(int val) {
this.val = val;
}
}
private ListNode front;//隊(duì)頭
private ListNode rear;//隊(duì)尾
private int usedSize;
public void offer(int val) {
ListNode node = new ListNode(val);
if (front == null) {
front = node;
rear = node;
} else {
//采用頭插法
front.prev = node;
node.next = front;
front = node;
}
usedSize++;
}
//出隊(duì)列 相當(dāng)于刪除隊(duì)尾結(jié)點(diǎn)
public int poll() {
//頭插尾刪
if (rear == null) {
return -1;
} else if (front == rear) {
//只有一個(gè)結(jié)點(diǎn)
int ret = rear.val;
front = null;
rear = null;
usedSize--;
return ret;
} else {
int ret = rear.val;
rear = rear.prev;
rear.next = null;
usedSize--;
return ret;
}
}
//獲取隊(duì)頭
public int peek() {
if (rear == null) {
return -1;
}
//因?yàn)槭穷^插尾刪，所以返回的是隊(duì)尾元素
return rear.val;
}
public int getUsedSize() {
return usedSize;
}
public boolean isEmpty() {
if (usedSize == 0) {
return true;
}
return false;
}
}2.4 循環(huán)隊(duì)列
如下圖，就是一個(gè)循環(huán)隊(duì)列。環(huán)形隊(duì)列通常使用數(shù)組實(shí)現(xiàn)。
該怎么區(qū)分循環(huán)隊(duì)列到底滿沒滿？
1. 可以定義一個(gè) usedSize，如果 usedSize == elem.length，說明滿了
2. 可以定義一個(gè) flag ，如果滿了，就標(biāo)記為 true
3. 可以浪費(fèi)一個(gè)空間，來區(qū)分
一般用第三種方法，因?yàn)楸容^簡(jiǎn)單。
那么該怎么讓數(shù)組變成一個(gè)循環(huán)數(shù)組呢？
622.?設(shè)計(jì)循環(huán)隊(duì)列
首先，循環(huán)隊(duì)列的底層是一個(gè)數(shù)組，所以我們要定義一個(gè)數(shù)組，并且把 front，rear 也一起定義上。
然后實(shí)現(xiàn)構(gòu)造方法，因?yàn)槲覀冞x擇浪費(fèi)一個(gè)空間來區(qū)分循環(huán)隊(duì)列滿沒滿，所以我們要多初始化一個(gè)空間給數(shù)組，不然數(shù)組就放不下那么多元素了。
再來實(shí)現(xiàn) isEmpty 方法?，如下圖，很明顯，當(dāng) front == rear 的時(shí)候，隊(duì)列為空。
再來實(shí)現(xiàn) isFull 方法 ，因?yàn)槔速M(fèi)了一個(gè)空間來區(qū)分滿沒滿，根據(jù)前面講過的，如下圖：
?
再來實(shí)現(xiàn) front 和 rear 方法
先判斷空不空，不為空就返回，為空就返回 -1，返回隊(duì)尾元素的時(shí)候得注意 rear 下標(biāo)，假如 rear 剛好為 0 ，index = rear - 1；這顯然是不對(duì)的，他的上一個(gè)應(yīng)該是 len - 1下標(biāo)才對(duì)，所以得做判斷。
?
再來實(shí)現(xiàn)?enQueue 方法 ，首先判斷滿沒滿，沒滿就插入，滿了就返回 false
再來實(shí)現(xiàn)?deQueue 方法，先判斷 空不空，不空就出隊(duì)頭，空就返回.
class MyCircularQueue {
public int elem[];
public int front;
public int rear;//隊(duì)尾進(jìn)元素，所以增加元素的時(shí)候，就放到 rear 下標(biāo)即可
public MyCircularQueue(int k) {
//因?yàn)槲覀兝速M(fèi)了一個(gè)空間來區(qū)別隊(duì)列滿沒滿
//所以要多初始化一個(gè)空間
this.elem = new int[k + 1];
}
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
elem[rear] = value;
rear = (rear + 1) % elem.length;
return true;
}
public boolean deQueue() {
//為空
if (isEmpty()) {
return false;
}
//出隊(duì)頭
front = (front + 1) % elem.length;
return true;
}
public int Front() {
if (isEmpty()) {
return -1;
}
return elem[front];
}
public int Rear() {
if (isEmpty()) {
return -1;
}
int index = (rear == 0) ? (elem.length - 1) : (rear - 1);
return elem[index];
}
public boolean isEmpty() {
if (front == rear) {
return true;
}
return false;
}
public boolean isFull() {
if (((rear + 1) % elem.length) == front) {
return true;
}
return false;
}
}3. 雙端隊(duì)列 (Deque)
雙端隊(duì)列，就是兩邊都能進(jìn)行出隊(duì)入隊(duì)操作的隊(duì)列。元素可以從隊(duì)頭出隊(duì)和入隊(duì)，也可以從隊(duì)尾出隊(duì)和入隊(duì)。
Deque 也是一個(gè)接口，實(shí)例化的時(shí)候也要?jiǎng)?chuàng)建LinkedList的對(duì)象。
4. 練習(xí)題
225.?用隊(duì)列實(shí)現(xiàn)棧
思路：可以使用兩個(gè)隊(duì)列實(shí)現(xiàn)，只有當(dāng)兩個(gè)隊(duì)列都為空的時(shí)候，棧才為空，因?yàn)殛?duì)列是先進(jìn)先出的結(jié)構(gòu)，而棧是先進(jìn)后出的結(jié)構(gòu)，所以出棧的時(shí)候，就得出不為空的隊(duì)列，將不為空的隊(duì)列的所有元素出隊(duì)放到另一個(gè)隊(duì)列里，最后再出一次隊(duì)即可，而入棧的時(shí)候也同理，就把元素放到不為空的隊(duì)列里。
class MyStack {
private Queue<Integer> qu1;
private Queue<Integer> qu2;
public MyStack() {
qu1 = new LinkedList<>();
qu2 = new LinkedList<>();
}
public void push(int x) {
//入棧的時(shí)候入到不為空的隊(duì)列里
if (empty()) {
qu1.offer(x);
} else {
if (!qu1.isEmpty()) {
qu1.offer(x);
}
if (!qu2.isEmpty()) {
qu2.offer(x);
}
}
}
public int pop() {
if (empty()) {
return -1;//棧為空
}
if (!qu1.isEmpty()) {
int cnt = qu1.size() - 1;
while (cnt != 0) {
int tmp = qu1.poll();
qu2.offer(tmp);
cnt--;
}
return qu1.poll();
}
int cnt = qu2.size() - 1;
while (cnt != 0) {
int tmp = qu2.poll();
qu1.offer(tmp);
cnt--;
}
return qu2.poll();
}
public int top() {
if (empty()) {
return -1;
}
int tmp = 0;
if (!qu1.isEmpty()) {
int cnt = qu1.size();
while (cnt != 0) {
tmp = qu1.poll();
qu2.offer(tmp);
cnt--;
}
return tmp;
}
int cnt = qu2.size();
while (cnt != 0) {
tmp = qu2.poll();
qu1.offer(tmp);
cnt--;
}
return tmp;
}
public boolean empty() {
//兩個(gè)隊(duì)列都為空表示棧為空
if (qu1.isEmpty() && qu2.isEmpty()) {
return true;
}
return false;
}
}??????232.?用棧實(shí)現(xiàn)隊(duì)列
思路：利用兩個(gè)棧來實(shí)現(xiàn)，假設(shè)一個(gè)叫 stack1，一個(gè)叫 stack2，簡(jiǎn)稱 s1 和 s2。文章來源：http://www.zghlxwxcb.cn/news/detail-733040.html
固定 入隊(duì)就入 s1 ，出隊(duì)首先判斷隊(duì)列是不是空，如果不是空，就出 s2，如果 s2 沒元素，那就將 s1 的元素全部出到 s2 里，然后 s2 再來出棧。peek 也同理，只有當(dāng)兩個(gè)棧為空的時(shí)候，隊(duì)列才為空。文章來源地址http://www.zghlxwxcb.cn/news/detail-733040.html
class MyQueue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public MyQueue() {
stack1 = new Stack<>();//s1用來做輸入棧
stack2 = new Stack<>();//s2用來做輸出棧
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if (empty()) {
return -1;
}
if (stack2.empty()) {
int size = stack1.size();
while (size != 0) {
int tmp = stack1.pop();
stack2.push(tmp);
size--;
}
return stack2.pop();//是top元素
}
return stack2.pop();//如果s2不為空，說明之前已經(jīng)按順序彈出元素了
}
public int peek() {
if (empty()) {
return -1;
}
if (stack2.empty()) {
int size = stack1.size();
while (size != 0) {
int tmp = stack1.pop();
stack2.push(tmp);
size--;
}
return stack2.peek();//是top元素
}
return stack2.peek();
}
public boolean empty() {
if (stack1.empty() && stack2.empty()) {
return true;
}
return false;
}
}到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列 - 超詳細(xì)的教程，手把手教你認(rèn)識(shí)并運(yùn)用棧和隊(duì)列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
