隊列：先進先出 棧：后進先出
隊列：先進先出 棧：后進先出
有效的括號
https://leetcode.cn/problems/valid-parentheses/
做法：遍歷字符串
1.當(dāng)前字符是左括號：進棧
2.當(dāng)前字符是右括號：出棧頂元素和當(dāng)前字符比較是否匹配
- 特殊情況：如果此時棧為空，那么說明不匹配
3.最后如果棧為空，說明是匹配的，否則是不匹配的
class Solution {
public:
bool isValid(string s) {
stack<char> st;
//遍歷字符串,碰到左括號：進棧 碰到右括號：出棧頂元素判斷是否和該右括號匹配
for(auto& ch:s)
{
if(ch == '(' || ch == '[' || ch == '{')
{
st.push(ch);
}
else
{
//如果棧為空,說明括號是不匹配的
if(st.empty()) return false;
//出棧頂元素和當(dāng)前右括號匹配
char top = st.top();
st.pop();
if( ch ==')' && top != '(' || ch == ']' && top != '[' ||ch == '}' && top != '{')
return false;
}
}
return st.empty(); //如果最后棧為空,說明括號是匹配的
}
};
用隊列實現(xiàn)棧
https://leetcode-cn.com/problems/implement-stack-using-queues/
兩個隊列實現(xiàn)棧
隊列：先進先出 棧：后進先出
兩個隊列：
- NonEmptyQueue：表示存放數(shù)據(jù)的隊列，記為A
- EmptyQueue：表示空隊列，記為B
插入元素：直接往A隊列插入
彈出元素：將A隊列的元素都插入到B隊列當(dāng)中，直到A隊列只剩下一個元素，此時這個元素就相當(dāng)于是棧頂元素。然后A隊列和B隊列交換，保證B隊列是空的
例如：插入順序為1 2 3 4
A隊列：1 2 3 4
假設(shè)要棧頂元素：那么就算A隊列隊尾元素
假設(shè)要彈出棧頂元素：將A的元素放到B,直到A只有一個元素，然后彈出A隊列剩余的一個元素就是棧頂元素，然后交換兩個隊列
A:4 B:1 2 3 ==> A:1 2 3 B:空
獲取棧頂元素：本質(zhì)就是A隊列的隊尾元素
判空：A隊列和B隊列為空 就是空
class MyStack {
public:
MyStack() {
}
void push(int x) {
NonEmptyQueue.push(x);//往不為空的隊列插入數(shù)據(jù)
}
int pop() {
//將不空隊列的數(shù)據(jù)放到空隊列當(dāng)中,直到不空隊列只有一個元素
while(NonEmptyQueue.size() > 1)
{
EmptyQueue.push(NonEmptyQueue.front());
NonEmptyQueue.pop();
}
int front = NonEmptyQueue.front();
NonEmptyQueue.pop();
NonEmptyQueue.swap(EmptyQueue);//交換兩個隊列,保證EmptyQueue為空隊列
return front;
}
int top() {
return NonEmptyQueue.back();
}
bool empty() {
return EmptyQueue.empty() && NonEmptyQueue.empty();
}
private:
queue<int> NonEmptyQueue;//不為空的隊列
queue<int> EmptyQueue;//空隊列
};
一個隊列實現(xiàn)棧
將隊列類比為一個循環(huán)圈
插入元素：直接插入
彈出元素：將隊列的前size-1個元素重新插入到隊列當(dāng)中，然后此時隊頭元素就是要彈出的===>隊頭元素就相當(dāng)于是棧頂元素
獲取棧頂元素：相當(dāng)于是隊尾元素
class MyStack {
public:
MyStack() {
}
void push(int x) {
q.push(x);
}
int pop() {
int size = q.size();
//將前size-1個元素重新插入到隊列當(dāng)中
for(int i = 0;i<size-1;i++)
{
int front = q.front();
q.pop();
q.push(front);
}
//此時隊頭元素就相當(dāng)于是棧頂元素
int front = q.front();
q.pop();
return front;
}
int top() {
return q.back();
}
bool empty() {
return q.empty();
}
private:
queue<int> q;
};
用棧實現(xiàn)隊列
https://leetcode-cn.com/problems/implement-queue-using-stacks/
兩個棧：
- pushStack：存放插入數(shù)據(jù)的棧
- popStack：存放要彈出數(shù)據(jù)的棧
插入元素：直接往pushStack插入
子函數(shù)Check：檢查是否要將pushStack的內(nèi)容導(dǎo)入到popStack
- 將pushStack的所有元素插入到popStack ===>元素就變成逆序了
插入順序：1 2 3 4
pushStack: 1 2 3 4 導(dǎo)入到popStack后：4 3 2 1 符合先進先出
彈出隊頭元素：先進行檢查 =>彈出popStack棧頂元素
獲取隊頭元素：先進行檢查 =>返回popStack棧頂元素
class MyQueue {
public:
MyQueue() {
}
void push(int x) {
pushStack.push(x);
}
void Check() //檢查是否要將push棧的內(nèi)容導(dǎo)入到pop棧
{
if(popStack.empty())
{
while(!pushStack.empty())
{
popStack.push(pushStack.top());
pushStack.pop();
}
}
}
int pop() {
Check();
int top = popStack.top();
popStack.pop();
return top;
}
int peek() {
Check();
return popStack.top();
}
bool empty() {
return pushStack.empty() && popStack.empty();
}
private:
stack<int> pushStack;//存放數(shù)據(jù)的棧
stack<int> popStack;//用于彈出數(shù)據(jù)的棧
};
設(shè)計循環(huán)隊列
https://leetcode-cn.com/problems/design-circular-queue/
方式1：使用數(shù)組實現(xiàn)
分析：
1.存儲k個元素，需要開辟k+1個空間！否則不能準確的判空和判滿
2.需要使用兩個變量來標志隊頭和隊尾位置，記為front和tail，還需要一個變量size：記錄隊列當(dāng)中存儲的元素個數(shù)
enQueue： 向循環(huán)隊列插入一個元素
- 如果隊列為滿了，直接插入失敗
- 在tail位置插入元素，然后tail++往后走，注意：需要和size+1取模，防止tail越界
deQueue：從循環(huán)隊列刪除元素
- 如果隊列為空，刪除失敗
- 只需要front往后走，front++即可，注意：需要和size+1取模，防止越界
獲取隊頭元素：front指向的就是隊頭元素
獲取隊尾元素：注意：tail的前一個位置就是隊尾元素！但是不能直接返回:arr[tail-1]，因為有可能上一次放的位置是size位置，然后tail++取模后到了0位置，所以要判斷一下
- 如果tail不是0位置：返回arr[tail-1]
- 如果tail是0位置：返回arr[size]
判斷隊列是否為滿：(tail + 1) % (size+1) == front;
class MyCircularQueue {
public:
MyCircularQueue(int k) {
arr.resize(k+1);//開辟k+1個空間
front = tail = 0;
size = k;
}
bool enQueue(int value) { //向循環(huán)隊列插入一個元素。如果成功插入則返回真
if(isFull()) return false;
arr[tail] = value;
tail ++;
tail %= size+1; //tail = tail % (size+1)
return true;
}
bool deQueue() { //從循環(huán)隊列中刪除一個元素。如果成功刪除則返回真。
if(isEmpty()) return false;
front++;
front %= size+1;
return true;
}
int Front() {
if(isEmpty()) return -1;
return arr[front];
}
int Rear() {
if(isEmpty()) return -1;
//由于插入元素之后,tail往后走,所以tail的前一個元素才是隊尾元素
if(tail == 0) return arr[size];
else return arr[tail-1];
}
bool isEmpty() {
return front == tail;
}
bool isFull() {
return (tail + 1) % (size+1) == front;
}
private:
vector<int> arr;
int front;//標志隊頭
int tail;//標志隊尾
int size;//實際存儲的元素個數(shù)
};
方法2：鏈表實現(xiàn)
存儲k個元素，需要構(gòu)建k+1個節(jié)點的循環(huán)鏈表，還需要定義兩個指針front和tail標志隊頭和隊尾，最初鏈表為空二者都指向鏈表的頭
向循環(huán)隊列插入一個元素：隊列為滿，插入失敗。否則插入到tail節(jié)點位置，然后tail節(jié)點往后走
從循環(huán)隊列刪除一個元素：隊列為空，刪除失敗。否則front節(jié)點往后走
獲取隊頭元素：返回front指針指向的節(jié)點的存放的值
獲取隊尾元素：注意：tail節(jié)點的前一個節(jié)點才是隊尾節(jié)點，所以需要從front位置開始往后遍歷找到tail的前一個節(jié)點，然后返回對應(yīng)的值
判空：front == tail
判滿：tail->next == front
class MyCircularQueue {
public:
MyCircularQueue(int k) {
//構(gòu)建k+1個節(jié)點的循環(huán)鏈表
tail = head = new ListNode;
for(int i = 0;i<k;i++)
{
ListNode* newnode = new ListNode;
tail->next = newnode;
tail = tail->next;
}
//tail指向尾節(jié)點,讓首尾相連
tail->next = head;
//注意:要讓tail回到起始位置?。。。。∫驗橐婚_始鏈表沒有有效元素
head = tail;
}
bool enQueue(int value) { //向循環(huán)隊列插入一個元素。如果成功插入則返回真。
if(isFull()) return false;
tail->val = value;
tail = tail->next;
return true;
}
bool deQueue() {
if(isEmpty()) return false;
head = head->next;
return true;
}
int Front() {
if(isEmpty()) return -1;
return head->val;
}
int Rear() {
if(isEmpty()) return -1;
//從head位置遍歷查找,tail的前一個節(jié)點放的就算隊尾元素
ListNode* cur = head;
while(cur->next != tail)
cur = cur->next;
return cur->val;
}
bool isEmpty() {
return head == tail;
}
bool isFull() {
return tail->next == head;
}
private:
ListNode* head;
ListNode* tail;
};s
最小棧
https://leetcode.cn/problems/min-stack/
方法1：使用兩個棧,一個數(shù)據(jù)棧,一個輔助棧
- 1.如果最小棧為空,就存放當(dāng)前入棧數(shù)據(jù)
- 2.如果最小棧不為空,
case1:如果此時最小棧的棧頂元素>此時入數(shù)據(jù)棧的當(dāng)前數(shù) -> 最小棧中壓入當(dāng)前數(shù)
case2:如果此時最小棧的棧頂元素<=此時入數(shù)據(jù)棧的當(dāng)前數(shù) -> 最小棧中重復(fù)壓入此時最小棧的棧頂元素
最小棧和輔助棧,同步壓入元素,同步彈出元素，每時每刻得到當(dāng)前數(shù)據(jù)棧中數(shù)據(jù)的最小值 ，二者一一對應(yīng)
class MinStack {
public:
MinStack() {
}
void push(int val) {
dataStack.push(val);
//判斷要往輔助棧放重復(fù)元素還是更小的元素
if( minStack.empty() || minStack.top() >= val)
minStack.push(val);
else
minStack.push(minStack.top());//重復(fù)壓入當(dāng)前最小棧棧頂元素
}
void pop() {
int top = dataStack.top();
dataStack.pop();
minStack.pop(); //坑點！！此時minStack也要同步pop數(shù)據(jù)
}
int top() {
return dataStack.top();
}
int getMin() {
return minStack.top();
}
private:
stack<int> minStack;//輔助棧->存放當(dāng)前棧中對應(yīng)的最小值
stack<int> dataStack;
};
優(yōu)化：
- 1.如果最小棧為空,就存放當(dāng)前入棧數(shù)據(jù)
- 2.如果最小棧不為空
case1:如果此時最小棧的棧頂元素**>=**此時入數(shù)據(jù)棧的當(dāng)前數(shù) -> 最小棧中壓入當(dāng)前數(shù) ，等于的時候也要插入?。?！
case2:如果此時最小棧的棧頂元素<此時入數(shù)據(jù)棧的當(dāng)前數(shù) -> 不壓入數(shù)據(jù)
pop數(shù)據(jù)時:如果此時數(shù)據(jù)棧的數(shù)據(jù)和最小棧的棧頂數(shù)據(jù)一樣->最小棧出棧頂元素 否則最小棧不出數(shù)據(jù)
class MinStack {
public:
MinStack() {
}
void push(int val) {
dataStack.push(val);
if( minStack.empty() || minStack.top() >= val)
minStack.push(val);
}
void pop() {
int top = dataStack.top();
dataStack.pop();
if(top == minStack.top())
minStack.pop();
}
int top() {
return dataStack.top();
}
int getMin() {
return minStack.top();
}
private:
stack<int> minStack;//輔助棧->存放當(dāng)前棧中對應(yīng)的最小值
stack<int> dataStack;
};
棧的壓入&彈出序列
https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
思想就是：使用棧的入棧順序，模擬這個出棧順序,如果能模擬出來,就說明是合法的,否則就是非法的!
做法：
使用一個棧，然后遍歷pushV數(shù)組，模擬入棧順序，還需要定義一個變量popIndex表示出棧數(shù)組遍歷到了哪個位置，對于每一次遍歷：
- 先將當(dāng)前pushV數(shù)組的元素進棧
- 如果棧不為空,并且當(dāng)前出棧元素 = 棧頂元素,那么就彈出棧頂元素 ==> while循環(huán)操作
最后：如果popIndex遍歷完了popV數(shù)組,說明是可以按這個順序彈出的，返回true
class Solution {
public:
//pushV:元素的入棧順序 popV:判斷該序列是否可能為該棧的彈出順序
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
if(pushV.size() != popV.size()) return false;
stack<int> st;//模擬進棧順序
int popIndex = 0;//當(dāng)前出棧元素位置
for(int i = 0;i<pushV.size();i++)
{
//當(dāng)前元素進棧
st.push(pushV[i]);
//如果棧不為空,并且當(dāng)前出棧元素 = 棧頂元素,那么就彈出
while(!st.empty() && st.top() == popV[popIndex])
{
popIndex++;
st.pop();
}
}
//最后:如果popIndex遍歷完了popV數(shù)組,說明是可以按這個順序彈出的
return popIndex == popV.size();
}
};
逆波蘭表達式（后綴表達式）
https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
思路：遍歷字符串
- 如果是操作數(shù)：進棧
- 如果是操作符：取棧頂?shù)膬蓚€元素出來進行運算，然后再把運算結(jié)果放到棧中
- 最后遍歷完成后，棧頂元素就是計算結(jié)果
注意：棧是后進先出的，所以先拿到的是右操作數(shù)，然后才是左操作數(shù)
最好是使用switch-case語句，因為有+-*/四種情況，后續(xù)如果還有其它情況，也比較容易增加。如果使用if-else，看起來不美觀文章來源：http://www.zghlxwxcb.cn/news/detail-656192.html
- 使用第一個字符判斷是操作符還是操作數(shù)的時候，要特別小心
-，因為操作數(shù)可能為負數(shù)，所以要特判：如果字符串長度為1：說明就是操作符，否則就是操作數(shù) - 或者說：取字符串的最后一個字符判斷是操作數(shù)還是操作符
switch(str.back())
stoi函數(shù)：用于將string字符串轉(zhuǎn)為整數(shù)文章來源地址http://www.zghlxwxcb.cn/news/detail-656192.html
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
//遍歷容器,如果是操作數(shù)就進棧
int left = 0,right = 0;
auto GetNum = [&]() //獲取兩個操作數(shù)
{
right = st.top(); //注意:先拿到的是右操作數(shù)
st.pop();
left = st.top();
st.pop();
};
for(auto& str:tokens) //str是string
{
//如果是操作數(shù)就進棧,如果是操作符就把當(dāng)前棧中兩個元素拿出來進行運算,然后把運算結(jié)果進棧
switch(str[0])
{
case '+':
GetNum();
st.push(left + right);
break;
case '-': //坑點:有可能不是操作符,而是操作數(shù)->負數(shù)
if(str.size() == 1) //操作符
{
GetNum();
st.push(left - right);
}
else //操作數(shù)
{
st.push(stoi(str));
}
break;
case '*':
GetNum();
st.push(left * right);
break;
case '/':
GetNum();
st.push(left / right);
break;
default: //操作數(shù)
st.push(stoi(str));
break;
}
}
return st.top();
}
};
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】棧和隊列常見題目的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
