棧（Stack）
又名堆棧，它是一種重要的數(shù)據(jù)結(jié)構(gòu)。從數(shù)據(jù)結(jié)構(gòu)角度看，棧也是線性表，其特殊性在于棧的基本操作是線性表操作的子集，它是操作受限的線性表，因此，可稱為限定性的數(shù)據(jù)結(jié)構(gòu)。限定它僅在表尾進(jìn)行插入或刪除操作。表尾稱為棧頂，相應(yīng)地，表頭稱為棧底。棧的基本操作除了在棧頂進(jìn)行插入和刪除外，還有棧的初始化，判空以及取棧頂元素等。
隊(duì)列（Queue）
是一種先進(jìn)先出（FIFO，F(xiàn)irst-In-First-Out）的線性表。
在具體應(yīng)用中通常用鏈表或者數(shù)組來實(shí)現(xiàn)。隊(duì)列只允許在后端（稱為 rear）進(jìn)行插入操作，在前端（稱為 front）進(jìn)行刪除操作。
隊(duì)列的操作方式和堆棧類似，唯一的區(qū)別在于隊(duì)列只允許新數(shù)據(jù)在后端進(jìn)行添加。
Queue接口與List、Set同一級(jí)別，都是繼承了Collection接口。LinkedList實(shí)現(xiàn)了Queue接 口。
隊(duì)列常用的方法有：add、remove、element、offer、poll、peek、put、take，方法解釋：
- add
增加一個(gè)元索 如果隊(duì)列已滿，則拋出一個(gè)IIIegaISlabEepeplian異常 - remove
移除并返回隊(duì)列頭部的元素 如果隊(duì)列為空，則拋出一個(gè)NoSuchElementException異常 - element
返回隊(duì)列頭部的元素 如果隊(duì)列為空，則拋出一NoSuchElementException異常 - offer 添加一個(gè)元素并返回true 如果隊(duì)列已滿，則返回false
- poll 移除并返問隊(duì)列頭部的元素 如果隊(duì)列為空，則返回null
- peek 返回隊(duì)列頭部的元素 如果隊(duì)列為空，則返回null
- put 添加一個(gè)元素 如果隊(duì)列滿，則阻塞
- take 移除并返回隊(duì)列頭部的元素
面試題 03.04. 化棧為隊(duì)
實(shí)現(xiàn)一個(gè)MyQueue類，該類用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列。
示例：
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
題解：
/**
* 實(shí)現(xiàn)思路：
* 創(chuàng)建2個(gè)棧，棧1只負(fù)責(zé)入棧，棧2只負(fù)責(zé)出棧
* 存入幾個(gè)元素到棧1后，如果此時(shí)棧2為空，則將棧1中的元素轉(zhuǎn)移到棧2，從棧2出棧
* 如果此時(shí)棧2中不為空，則直接從棧2出棧
*/
class MyQueue {
Stack<Integer> stack1; //stack1只負(fù)責(zé)入棧
Stack<Integer> stack2; //stack2只負(fù)責(zé)出棧
/** Initialize your data structure here. */
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
stack1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (!stack2.isEmpty()) {
return stack2.pop();
} else {
//將stack1中所有元素轉(zhuǎn)移到stack2
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
/** Get the front element. */
public int peek() {
if (!stack2.isEmpty()) {
return stack2.peek();
} else {
//將stack1中所有元素轉(zhuǎn)移到stack2
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.peek();
}
}
/** Returns whether the queue is empty. */
public boolean empty() {
if (stack1.isEmpty() && stack2.isEmpty()) {
return true;
} else {
return false;
}
}
}
1047. 刪除字符串中的所有相鄰重復(fù)項(xiàng)
給出由小寫字母組成的字符串 S，重復(fù)項(xiàng)刪除操作會(huì)選擇兩個(gè)相鄰且相同的字母，并刪除它們。
在 S 上反復(fù)執(zhí)行重復(fù)項(xiàng)刪除操作，直到無法繼續(xù)刪除。
在完成所有重復(fù)項(xiàng)刪除操作后返回最終的字符串。答案保證唯一。
示例：
輸入："abbaca"
輸出："ca"
解釋：
例如，在 "abbaca" 中，我們可以刪除 "bb" 由于兩字母相鄰且相同，這是此時(shí)唯一可以執(zhí)行刪除操作的重復(fù)項(xiàng)。之后我們得到字符串 "aaca"，其中又只有 "aa" 可以執(zhí)行重復(fù)項(xiàng)刪除操作，所以最后的字符串為 "ca"。
題解：
/**
* 用棧的結(jié)構(gòu)來維護(hù)沒有重復(fù)項(xiàng)的字母序列:
* 循環(huán)從字符串中取出一個(gè)字符，與棧頂字符對(duì)比，如果不同，則放入棧；如果相同，則兩個(gè)字符消掉，
* 即刪除字符串中該字符，同時(shí)刪除棧中該字符，最終棧中剩下來的字符數(shù)組為最終字符串
*
*/
class Solution {
public String removeDuplicates(String S) {
Stack<Character> stack = new Stack();
char[] chars = S.toCharArray();
for (char ch : chars) {
if (stack.isEmpty()) { //如果棧為空，則直接入棧
stack.push(ch);
} else { //如果棧不為空，則判斷當(dāng)前字符與棧頂字符是否相同，相同就從棧中彈出棧
if (ch != stack.peek()) {
stack.push(ch);
} else {
stack.pop();
}
}
}
StringBuilder stringBuilder = new StringBuilder();
for (Character ch : stack) {
stringBuilder.append(ch);
}
return stringBuilder.toString();
}
}
682. 棒球比賽
你現(xiàn)在是棒球比賽記錄員。
給定一個(gè)字符串列表，每個(gè)字符串可以是以下四種類型之一：
1.整數(shù)（一輪的得分）：直接表示您在本輪中獲得的積分?jǐn)?shù)。
- "+"（一輪的得分）：表示本輪獲得的得分是前兩輪有效 回合得分的總和。
- "D"（一輪的得分）：表示本輪獲得的得分是前一輪有效 回合得分的兩倍。
- "C"（一個(gè)操作，這不是一個(gè)回合的分?jǐn)?shù)）：表示您獲得的最后一個(gè)有效 回合的分?jǐn)?shù)是無效的，應(yīng)該被移除。
每一輪的操作都是永久性的，可能會(huì)對(duì)前一輪和后一輪產(chǎn)生影響。
你需要返回你在所有回合中得分的總和。
示例 1:
輸入: ["5","2","C","D","+"]
輸出: 30
解釋:
第1輪：你可以得到5分。總和是：5。
第2輪：你可以得到2分?？偤褪牵?。
操作1：第2輪的數(shù)據(jù)無效。總和是：5。
第3輪：你可以得到10分（第2輪的數(shù)據(jù)已被刪除）?？倲?shù)是：15。
第4輪：你可以得到5 + 10 = 15分?？倲?shù)是：30。
題解：
/**
* 思路：
* 用Stack來存儲(chǔ)每一個(gè)輪的得分，最后累加得分。
* 根據(jù)每種字符規(guī)則，處理當(dāng)前輪的得分
*/
class Solution {
public int calPoints(String[] ops) {
//stack為Integer類型，只存儲(chǔ)每輪分?jǐn)?shù)數(shù)值
Stack<Integer> stack = new Stack();
for (String op : ops) {
if (op.equals("+")) {
int last = stack.pop(); //上一輪分?jǐn)?shù)
int cur = stack.peek() + last; //當(dāng)前輪分?jǐn)?shù)
stack.push(last);
stack.push(cur);
} else if (op.equals("C")) {
//移除上一輪得分
stack.pop();
} else if (op.equals("D")) {
//當(dāng)前分?jǐn)?shù)為上一輪的2倍
int score = stack.peek()*2;
stack.push(score);
} else {
//當(dāng)前為數(shù)字，直接加入
stack.push(Integer.valueOf(op));
}
}
int totalScore = 0;
for (Integer score : stack) {
totalScore += score;
}
return totalScore;
}
}
933. 最近的請(qǐng)求次數(shù)
寫一個(gè) RecentCounter 類來計(jì)算最近的請(qǐng)求。
它只有一個(gè)方法：ping(int t)，其中 t 代表以毫秒為單位的某個(gè)時(shí)間。
返回從 3000 毫秒前到現(xiàn)在的 ping 數(shù)。
任何處于 [t - 3000, t] 時(shí)間范圍之內(nèi)的 ping 都將會(huì)被計(jì)算在內(nèi)，包括當(dāng)前（指 t 時(shí)刻）的 ping。
保證每次對(duì) ping 的調(diào)用都使用比之前更大的 t 值。
示例：
輸入：inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
輸出：[null,1,2,3,3]
題解：
class RecentCounter {
Queue<Integer> queue;
public RecentCounter() {
queue = new LinkedList<>();
}
public int ping(int t) {
queue.add(t); //將當(dāng)前時(shí)間入列
//遍歷隊(duì)列，判斷當(dāng)前元素是否是當(dāng)前時(shí)間前3000的值，如果是，則從隊(duì)列中移除
while (queue.peek() < t - 3000) {
queue.poll();
}
return queue.size();
}
}
劍指 Offer 59 - I. 滑動(dòng)窗口的最大值
給定一個(gè)數(shù)組 nums 和滑動(dòng)窗口的大小 k，請(qǐng)找出所有滑動(dòng)窗口里的最大值。
示例:
輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7]
解釋:
滑動(dòng)窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
題解：
class Solution {
/**
* 思路：
* 從nums數(shù)組中取出前k個(gè)數(shù)，存入隊(duì)列中
* 獲取隊(duì)列的最大值存儲(chǔ)到集合中
* 然后隊(duì)列移除頭部，在尾部添加第k+1個(gè)數(shù)，獲取隊(duì)列中最大值存儲(chǔ)到集合中
*
* @param nums
* @param k
* @return
*/
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0) {
//如果數(shù)組為空，則返回空數(shù)組
return new int[0];
}
int[] result = new int[nums.length-k+1]; //總共需要輸出的數(shù)組
Queue<Integer> queue = new LinkedList<>();
//首次添加前k個(gè)數(shù)到隊(duì)列中作為初始隊(duì)列
for (int j=0;j<k;j++) {
queue.add(nums[j]);
}
//遍歷隊(duì)列獲取最大值
int maxNum = queue.peek();
for (Integer num : queue) {
if (num > maxNum) {
maxNum = num;
}
}
result[0] = maxNum;
for (int i=0;i<nums.length-k;i++) {
queue.poll(); //移除隊(duì)列頭部
queue.add(nums[i+k]); //添加數(shù)組下一個(gè)值到隊(duì)列尾部
//遍歷隊(duì)列獲取最大值
int max = queue.peek();
for (Integer num : queue) {
if (num > max) {
max = num;
}
}
result[i+1] = max;
}
return result;
}
}
有效的括號(hào)
給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：
左括號(hào)必須用相同類型的右括號(hào)閉合。
左括號(hào)必須以正確的順序閉合。
每個(gè)右括號(hào)都有一個(gè)對(duì)應(yīng)的相同類型的左括號(hào)。
題解：
class Solution {
public static boolean isValid(String s) {
//思路：1.在hashmap中存入左右括號(hào)對(duì)應(yīng)分別作為鍵值對(duì)
//遍歷字符，如果為左括號(hào)，就在棧中存入右括號(hào)，看后面的字符是否有該右括號(hào)來消掉
//3.用stack來存，先存就后取，后存就要先取
Stack<Character> stack = new Stack();
HashMap<Character,Character> map = new HashMap();
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
for(Character ch : s.toCharArray()) {
if(map.containsKey(ch)) { //當(dāng)前字符為左括號(hào)
stack.push(map.get(ch));
} else { //當(dāng)前字符為右括號(hào)，那棧中最頂部必然要與之相同才行
if(stack.isEmpty() || stack.pop() != ch) {
return false;
}
}
}
//最后看stack還有沒有沒有正確關(guān)閉括號(hào)
return stack.isEmpty();
}
}
用隊(duì)列實(shí)現(xiàn)棧
請(qǐng)你僅使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。
實(shí)現(xiàn) MyStack 類：
void push(int x) 將元素 x 壓入棧頂。
int pop() 移除并返回棧頂元素。
int top() 返回棧頂元素。
boolean empty() 如果棧是空的，返回 true ；否則，返回 false 。
題解：
/**
* 用兩個(gè)隊(duì)列實(shí)現(xiàn)棧
* 這里需要實(shí)現(xiàn)一個(gè)隊(duì)列元素的倒序，每次從queue2入列，從queue1中取出
*/
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
/** Initialize your data structure here. */
public MyStack() {
queue1 = new LinkedList(); //入隊(duì)列
queue2 = new LinkedList(); //出隊(duì)列
}
/** Push element x onto stack. */
public void push(int x) {
queue2.offer(x);
while(!queue1.isEmpty()) { //將queue1中的元素移入queue2中，實(shí)現(xiàn)現(xiàn)有元素的倒序
queue2.offer(queue1.poll());
}
//交換數(shù)據(jù)，所以每次添加完數(shù)據(jù)都在queue1隊(duì)列中
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue1.poll();
}
/** Get the top element. */
public int top() {
return queue1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty();
}
}
用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列。隊(duì)列的聲明如下，請(qǐng)實(shí)現(xiàn)它的兩個(gè)函數(shù) appendTail 和 deleteHead ，分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能。(若隊(duì)列中沒有元素，deleteHead 操作返回 -1 )
題解：
/**
* 實(shí)現(xiàn)思路：
* 創(chuàng)建2個(gè)棧，棧1只負(fù)責(zé)入棧，棧2只負(fù)責(zé)出棧
* 存入幾個(gè)元素到棧1后，如果此時(shí)棧2為空，則將棧1中的元素轉(zhuǎn)移到棧2，從棧2出棧
* 如果此時(shí)棧2中不為空，則直接從棧2出棧
*/
class CQueue {
Stack<Integer> stack1; //stack1只負(fù)責(zé)入棧
Stack<Integer> stack2; //stack2只負(fù)責(zé)出棧
public CQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
/**
* 入列
* @param value
*/
public void appendTail(int value) {
stack1.push(value);
}
/**
* 出列并返回當(dāng)前出列元素
* @return
*/
public int deleteHead() {
if (!stack2.isEmpty()) {
return stack2.pop();
} else {
//將stack1中所有元素轉(zhuǎn)移到stack2
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
//若隊(duì)列中沒有元素，deleteHead 操作返回 -1
return stack2.isEmpty() ? -1 : stack2.pop();
}
}
}
最小棧
設(shè)計(jì)一個(gè)支持 push ，pop ，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。
實(shí)現(xiàn) MinStack 類:
MinStack() 初始化堆棧對(duì)象。
void push(int val) 將元素val推入堆棧。
void pop() 刪除堆棧頂部的元素。
int top() 獲取堆棧頂部的元素。
int getMin() 獲取堆棧中的最小元素。
題解：
/**
* 思路：用一個(gè)棧和一個(gè)最小棧來做，棧保存存入的數(shù)，最小棧的數(shù)目與存數(shù)棧一樣，只是棧頂始終保存的是當(dāng)前棧中最小的數(shù)
*/
class MinStack {
Stack<Integer> stack;
Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty()) {
minStack.push(val);
} else {
minStack.push(Math.min(minStack.peek(), val));
}
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
去除重復(fù)字母
給你一個(gè)字符串 s ，請(qǐng)你去除字符串中重復(fù)的字母，使得每個(gè)字母只出現(xiàn)一次。需保證 返回結(jié)果的字典序最小（要求不能打亂其他字符的相對(duì)位置）。
題解：
class Solution {
/**
* 解題思路：
* 1.第一個(gè)條件：去重字母
* 2.第二個(gè)條件：保證字典序從小到大
* 3.第三個(gè)條件：保證字母存在至少一個(gè)
* @param s
* @return
*/
public String removeDuplicateLetters(String s) {
//第三個(gè)條件：保證字母存在至少一個(gè)
//做法：給每一種字母維護(hù)一個(gè)計(jì)數(shù)器，先遍歷獲取其數(shù)量，如果數(shù)量為1，則在第二個(gè)條件中不要彈出棧，否則可以彈出棧
int[] charCount = new int[256];
for (int i=0;i<s.length();i++) {
charCount[s.charAt(i)]++;
}
Stack<Character> stk = new Stack<>();
boolean[] inStack = new boolean[256]; //用于存儲(chǔ)這個(gè)字符是否已經(jīng)記錄過
// 第一個(gè)條件：去重字母
for(char c : s.toCharArray()) {
// 每遍歷過一個(gè)字符，都將對(duì)應(yīng)的計(jì)數(shù)減一
charCount[c]--;
if (inStack[c]) {
continue;
}
//第二個(gè)條件：保證字典序從小到大，在插入字母之前，判斷與前一個(gè)字母的字典序，
// 如果比前一個(gè)小，則循環(huán)將字符彈出棧頂，清除在棧中的記錄
while(!stk.empty() && stk.peek() > c) {
if (charCount[stk.peek()] == 0) {
break;
}
inStack[stk.pop()] = false;
}
stk.push(c);
inStack[c] = true;
}
StringBuilder sb = new StringBuilder();
while (!stk.empty()) {
sb.append(stk.pop());
}
return sb.reverse().toString();
}
}
劍指 Offer 59 - I. 滑動(dòng)窗口的最大值
給定一個(gè)數(shù)組 nums 和滑動(dòng)窗口的大小 k，請(qǐng)找出所有滑動(dòng)窗口里的最大值。
題解：
class Solution {
/**
* 思路：
* 從nums數(shù)組中取出前k個(gè)數(shù)，存入隊(duì)列中
* 獲取隊(duì)列的最大值存儲(chǔ)到集合中
* 然后隊(duì)列移除頭部，在尾部添加第k+1個(gè)數(shù)，獲取隊(duì)列中最大值存儲(chǔ)到集合中
*
* @param nums
* @param k
* @return
*/
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0) {
//如果數(shù)組為空，則返回空數(shù)組
return new int[0];
}
int[] result = new int[nums.length-k+1]; //總共需要輸出的數(shù)組
Queue<Integer> queue = new LinkedList<>();
//首次添加前k個(gè)數(shù)到隊(duì)列中作為初始隊(duì)列
for (int j=0;j<k;j++) {
queue.add(nums[j]);
}
//遍歷隊(duì)列獲取最大值
int maxNum = queue.peek();
for (Integer num : queue) {
if (num > maxNum) {
maxNum = num;
}
}
result[0] = maxNum;
for (int i=0;i<nums.length-k;i++) {
queue.poll(); //移除隊(duì)列頭部
queue.add(nums[i+k]); //添加數(shù)組下一個(gè)值到隊(duì)列尾部
//遍歷隊(duì)列獲取最大值
int max = queue.peek();
for (Integer num : queue) {
if (num > max) {
max = num;
}
}
result[i+1] = max;
}
return result;
}
}
