栈和队列数据结构的介绍，并以LeetCode习题为例刷题。
栈
在 计算机中， 栈是一种抽象的数据结构，后进先出是栈中元素的特点。在深度优先算法中需要栈的实现。支持两种基本的操作
- push，添加元素到容器（collection）中
- pop，去除最近添加进去的
无论是在C++ 还是在python 中，为了高效实现栈的操作，往往添加以下的判别函数：
- peek() ，获取栈顶元素，没有弹出
- isFull()， 判断栈是否满
- isEmpty() ，判断栈是否空
不同语言实现有所差异。
1). Score of Parentheses
C++ 实现，使用了 stack 数据结构，时间复杂度是 $O(n)$， $n$ 表示字符串的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
int scoreOfParentheses(string S) {
stack<int> st;
st.push(0);
for (auto & ch : S) //在遍历的时候为了节省内存，使用引用
{
if(ch =='(')
st.push(0);
else
{
int t =st.top();
st.pop();
if (t ==0)
st.top() ++;
else
st.top() += 2* t;
}
}
# 因为这个是 balanced parentheses 对称的，所以最后一定剩下了一个
return st.top();
}
};
|
python 中没有 栈这个数据结构，直接使用 list 实现就ok。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def scoreOfParentheses(self, S: str) -> int:
stack =[]
stack.append(0)
for ch in S:
if ch =='(':
stack.append(0)
else:
# 这个相当于遇到了右括号，那么肯定是要弹出的
t =stack[-1]
stack.pop()
if t ==0:
stack[-1] +=1
else:
stack[-1] += t* 2
return stack[-1]
|
2). Next Greater Element I
nums1 是子集，nums2 是总的数字。这个是可以暴力求解，然后时间复杂度是是$O(mn)$。但是可以使用 hash 表和栈进行优化，优化后的时间复杂度是$O(m)$，其中$m$ 是nums2 的长度，空间复杂度是$O(m)$。hash表中key 表示nums2 中的每个数字，value 表示第一个比起大的元素。使用的栈是一个单调栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
// 栈实际上是递减的（从栈底到栈顶）
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> hash;
stack<int> st;
vector<int> res;
for(auto num : nums2)
{
while( !st.empty() && st.top() < num)
{
hash[st.top()] = num;
st.pop();
}
st.push(num);
}
for(auto num : nums1)
{
res.emplace_back(hash.count(num) ? hash[num] : -1); // 这个三木判断还是有点意思的
}
return res;
}
};
|
使用python 实现。 其中的 while 重复体现了单调栈， 栈中的元素可以理解为未找到比其大的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
dic ={}
stack =[]
res =[]
for num in nums2:
while stack and stack[-1] < num:
dic[stack[-1]] =num
stack.pop()
stack.append(num)
print(dic)
for num in nums1:
res.append( dic[num] if num in dic else -1)
return res
|
3). Next Greater Element II
将原数组复制一份放在原数组之后，可以处理环形问题。和上一题的思路一样，还是 $O(n)$ 的时间复杂度。在实现上需要注意，这里的stack 存放的是 index 而不是上一题的数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n =nums.size();
vector<int> res(n, -1);
stack<int> st;
for(int i =0; i< 2*n ; i++)
{
int num =nums[i %n];
while ( ! st.empty() && nums[st.top() ]< num)
{
res[st.top()] = num;
st.pop();
}
if(i < n)
st.push(i);
}
return res;
}
};
|
4). Remove Outermost Parentheses
去除最外层的括号，对于嵌套的括号，最后保留一个括号进行。成对出现的括号问题,大多数都可以使用 stack 进行求解，并且当 ) 时是弹出队列，当( 的时候是弹入队列。这两个是不变的操作，其他的可以根据题目进行求解。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def removeOuterParentheses(self, S: str) -> str:
stack =[]
ans =""
for ch in S:
if ch ==')':
stack.pop()
if stack :
ans += ch
if ch =="(":
stack.append(ch)
return ans
|
Remove All Adjacent Duplicates In String
如果当前的元素和栈顶元素相同，那么弹出栈顶元素，否则入栈。最后将栈中所有元素输出，翻转。时间复杂度是$O(N)$
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def removeDuplicates(self, S: str) -> str:
stack =[]
for ch in S:
if stack and stack[-1] == ch:
stack.pop()
else: #当不满足条件之后添加 和 无论如何都要添加 还是两个不同的方式
stack.append(ch)
res =""
while stack:
res += stack[-1]
stack.pop()
return res[::-1]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public:
string removeDuplicates(string S) {
stack<char> st;
for(auto ch : S)
{
if(st.size() && st.top() ==ch) # 这种是常见的操作， st.size() 判断是否为空 && st.top() 是逻辑判断
st.pop();
else
st.push(ch);
}
string res ;
while (st.size())
{
auto t = st.top();
res += t;
st.pop();
}
reverse(res.begin(), res.end());
return res;
}
};
|
Backspace String Compare
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
class Solution {
public:
// 在想一个问题： 什么时候是用到栈的数据结构?
// 栈是有一定顺序的，如果有逆序访问的习惯，栈是一个很好的开始
vector<int> asteroidCollision(vector<int>& asteroids) {
int n =asteroids.size();
stack<int> st;
vector<int> res;
for(int aster : asteroids)
{
// 逆向 怼
if (aster < 0)
{
while(st.size() && st.top() < -aster)
{
st.pop();
}
if(st.empty())
res.emplace_back(aster);
else
{
if (st.top() == -aster)
st.pop();
}
}
else
st.push(aster);
}
// 现在st 中保存的是 幸存的结果
vector<int> t;
while(st.size())
{
t.emplace_back(st.top());
st.pop();
}
for(auto it =t.rbegin(); it != t.rend(); it ++)
res.emplace_back(*it);
return res;
}
};
|
Decoded String at Index
使用 cnt统计变形之后字符串的总长度，$K$ 是总的长度， $i$ 表示string 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public:
string decodeAtIndex(string S, int K) {
long i =0, cnt =0;
for(; cnt < K; i++)
{
cnt =isdigit(S[i]) ? cnt *(S[i] -'0') : (cnt +1);
}
while(i --)
{
if(isdigit(S[i]))
{
cnt /= (S[i] -'0');
K %= cnt;
}
else
{
if (K %cnt ==0) return string(1, S[i]);
cnt --;
}
}
return "";
}
};
|
Minimum Add to Make Parentheses Valid
括号匹配题一般想到用栈
该题目中 stack 中永远存放的是左括号，遇到右括号，如果栈中有左括号（只可能是左括号），那么就弹出；否则加上右括号的个数。最后加上左括号的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution(object):
def minAddToMakeValid(self, S):
"""
:type S: str
:rtype: int
"""
res =0
stack =[]
for ch in S:
if ch =='(':
stack.append('(')
else:
if stack:
stack.pop()
else:
res +=1
return res +len(stack)
|
Sum of Subarray Minimums
计算每一个数字的贡献值，当前数字是自己本身的最小值，然后是左边某个区间的最小值，是右边某个区间的最小值，这三部分相乘就是当前数字总的贡献值。具体参考讲解1 和讲解2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
class Solution {
public:
int sumSubarrayMins(vector<int>& A) {
int n =A.size();
stack<int> st;
vector<int> l(n), r(n);
long long ans =0;
const int mod =1e9+7;
for(int i =0; i< n; i++)
{
while (st.size() && A[i] < A[st.top()])
{
r[st.top()] =i; // r[] 中存储的是比其小的元素的index
st.pop();
}
st.push(i); // 如果是”一样“的数字，那么不会加上 else 语句，stack 中每个都会给其一次机会
}
// 如果找不到，那么就置为 n
while(st.size())
{
r[st.top()] =n;
st.pop();
}
// 栈就保持了一种可以往回退的结构
for(int i =n -1; i>=0 ; i--)
{
while(st.size() && A[i] <= A[st.top()])
{
l[st.top()] =i;
st.pop();
}
st.push(i);
}
while(st.size())
{
l[st.top()] =-1;
st.pop();
}
for(int i =0; i<n; i++)
{
ans =(ans + (long long)A[i] *(r[i] -i) *(i -l[i])) %mod;
}
return ans;
}
};
|
python 中双向队列使用这种方式进行实现；如果是栈的话，直接使用 stack实现就行。
1
|
stack = collections.deque([])
|
Validate Stack Sequences
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
// 使用一个stack 模拟过程, push进去 pushed 元素，然后和popped 中的元素做对比
// 如果是可以 pop，那么就一直pop
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
int n =pushed.size();
int i =0, j =0;
stack<int> st;
while (i < n && j < n)
{
st.push(pushed[i]);
while(st.size() && st.top() == popped[j])
{
st.pop();
j ++;
}
i ++;
}
return j ==n;
}
};
|
20. Valid Parentheses
注意 stk 的弹出条件。 len() ==0 or stk[-1] != ''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution(object):
# 关于 栈 stack 的使用
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stk =[]
for ch in s:
if ch in ['(', '[', '{']:
stk.append(ch)
elif ch ==')':
if len(stk) ==0 or stk[-1] !='(': return False # 注意这个是 or 的条件，反向的
stk.pop()
elif ch ==']':
if len(stk) ==0 or stk[-1] != '[': return False
stk.pop()
elif ch =='}':
if len(stk) ==0 or stk[-1] != '{': return False
stk.pop()
return len(stk) ==0
|
Minimum Remove to Make Valid Parentheses
stack更像是一种过滤机制， 最后的 v[i] 记录了默写去掉的字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class Solution {
public:
// 使用 stack 做了一个标记
string minRemoveToMakeValid(string s) {
int n =s.size();
stack<int> st;
vector<bool> v(n, true);
for(int i =0; i<n; i++)
{
if(s[i] ==')')
{
if ( !st.size() ) v[i] =false;
else st.pop();
}
else if(s[i] == '(')
st.push(i); // 存储的是index 下标，所以类型是int 而不是char
}
while(st.size())
{
v[st.top()] =false;
st.pop();
}
string ans ;
for(int i =0; i< n; i++)
if(v[i])
ans += s[i];
return ans;
}
};
|
Remove All Adjacent Duplicates in String II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution {
public:
string removeDuplicates(string s, int k) {
string res("#");
stack<int> cnt;
cnt.push(1);
int n =s.length();
for(int i =0; i<n ; i++ )
{
if(res.back() == s[i]) cnt.push(cnt.top() +1); // 这个是累加 push，后面也就是累加 pop的
else
cnt.push(1);
res += s[i];
if(cnt.top() >= k)
{
for(int j =0; j< k ; j++)
{
cnt.pop();
res.pop_back();
}
}
}
return stk.substr(1);
}
};
|
stack 数据结构 有点类似是来回访问, 但是能够保证只是访问一次，因为对于某个元素而言，只是经过一次的push 和pop
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def reverseParentheses(self, s: str) -> str:
stack =[]
for ch in s:
if ch ==")":
inner =[]
while True:
last =stack.pop()
if last =="(":
break
else:
inner.append(last)
stack.extend(inner)
else:
stack.append(ch)
return "".join(stack)
|
队列
队列刚好与之相反，是一个先进先出（FIFO，First In First Out）或者说后进后出（LILO，Last In Last Out）的数据结构。队列也是一种线性结构，只能一端（队尾）添加元素，另一端（队首）取出元素。
基本操作
- enqueue() 添加操作
- dequeue() 删除操作
为了使队列操作更加有效，可以有更多的操作
- peek() 访问队首元素而不删除
- isfull() 判断队列是否已满
- isempty() 判断队列是否为空
队列的存储可以分为链式存储和顺序存储。
队列的种类：
Python中关于队列的实现：
在python 中的使用 collections.deque() 实现队列。 deque是双向队列（double-ended queue），两段都是能够编辑，deque 既可以实现栈（stack） 又可以实现队列（queue）。相比于list 实现的队列，deque 具有更低的时间和空间复杂度。list 在出队（pop）和插入（insert）的时间复杂度是$O(n)$， deque在出队（pop）和入队（append）的时间复杂度是$O(1)$。
1
|
q =collections.deque([1, 2, 3, 4])
|
优先队列的实现。从源码中看，PriorityQueue 是使用heapq实现的，所以可以认为两者是等价的。当然 PriorityQueue 是考虑到了线程安全的问题。所以有两种方式实现优先队列（Priority Queue）。
C++ 中关于队列的实现：
普通队列的实现
1
2
3
|
queue<int> q;
q.push(4);
|
优先队列的最大特点是有序。
1
2
3
4
5
6
7
8
9
10
|
#include<queue>
# 下面两种形式是等价的，默认是大根堆
priority_queue<int> q;
priority_queue <int,vector<int>,less<int> >q;
priority_queue<node> q;
# 如果想要使用小根堆，使用greater 关键字输入到构造函数中
priority_queue<int,vector<int>,greater<int> >q;
|
1).
c++实现，队列简单的应用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class RecentCounter {
public:
queue<int> q;
RecentCounter() {
}
int ping(int t) {
q.push(t);
while(q.size())
{
if(t -3000 <=q.front())
break;
q.pop();
}
return q.size();
}
};
/**
* Your RecentCounter object will be instantiated and called as such:
* RecentCounter* obj = new RecentCounter();
* int param_1 = obj->ping(t);
*/
|
621. Task Scheduler
说实话，看不懂呀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
vector<int> cnt(26, 0);
for(char t : tasks)
cnt[t- 'A'] ++;
priority_queue<int> q;
for(int i =0; i<26; i++)
if(cnt[i] > 0)
q.push(cnt[i]);
int ans = 0;
while (true)
{
vector<int> tmp;
for(int i =1; i<=n +1; i++)
if(! q.empty())
{
tmp.push_back(q.top() -1);
q.pop();
}
for(int t : tmp)
if(t >0)
q.push(t);
if(q.empty())
{
ans += tmp.size() ;
break;
}
else
ans += n+1;
}
return ans;
}
};
|
Implement Stack using Queues
使用栈实现队列的功能， 栈是后进先出，队列是先进先出，主要考察的是队列和栈的操作。empty() 和push是在$O(1) $时间处理；pop() 和 top() 是在$O(n)$ 处理，其中top() 需要再次压栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
class MyStack {
public:
/** Initialize your data structure here. */
queue<int> q;
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
q.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
// 首先找到最后一个元素，然后是pop() 出去
int size =q.size();
// 不断将队列尾部的元素提前
while(size -- > 1)
{
/*
int t =q.front();
q.pop();
q.push(t);
*/
q.push(q.front());
q.pop();
}
int t =q.front();
q.pop();
return t;
}
/** Get the top element. */
int top() {
int size =q.size();
// 不断放到队尾
while(size -- > 1)
{
/*
int t =q.front();
q.pop();
q.push(t);
*/
q.push(q.front());
q.pop();
}
int t =q.front();
q.pop();
q.push(t);
return t;
}
/** Returns whether the stack is empty. */
bool empty() {
return q.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
|
Implement Queue using Stacks
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
class MyQueue {
public:
/** Initialize your data structure here. */
// 典型的做法是通过两个栈模拟队列，一个是主栈，一个是辅助栈
stack<int> sta, cache;
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
sta.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
// 队列是先进先出, 所以要找到栈的底
while( !sta.empty())
{
cache.push(sta.top());
sta.pop();
}
int val =cache.top();
cache.pop();
while(! cache.empty())
{
sta.push(cache.top());
cache.pop();
}
return val;
}
/** Get the front element. */
int peek() {
while( !sta.empty())
{
cache.push(sta.top());
sta.pop();
}
int val =cache.top();
//cache.pop();
while(! cache.empty())
{
sta.push(cache.top());
cache.pop();
}
return val;
}
/** Returns whether the queue is empty. */
bool empty() {
return sta.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
|
感觉是需要加上使用两个栈实现队列，使用两个队列实现栈的，解题思路
84. Largest Rectangle in Histogram
单调栈就是栈维持着某种单调性，比如递增，递减等，最后形成的数组，需要满足这样的单调性。如果不满足这样的性质怎么办？一般有两种思路：
- 当要压栈的数不满足规定的单调性，就不把这个数字压栈；
- 当压栈的数字破坏了单调性，那么就不停地弹出栈中的元素，知道新的数字压入之后不会破坏单调性。
时间复杂度$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
// 使用单调栈（递增）的思路解题
int n =heights.size() ;
heights.push_back(-1);
int res =0;
stack<int> st;
for(int i =0; i<=n ; i++)
{
while( !st.empty() && heights[i]< heights[st.top()])
{
// 进行弹出 操作 和计算可能的res
int t =st.top();
st.pop();
if(st.empty())
res =max(res, heights[t] *i);
else
res =max(res, heights[t] * (i- st.top() -1));
}
st.push(i);
}
return res;
}
};
|
85. Maximal Rectangle
可以将上一题目的解题思路拓展到二维空间。一行行考虑，一行内所有柱形条的高度 heights 就是当前 (i,j) 位置能够往上延伸的最大高度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
// 一行一行考虑，一行内所有柱形条的高度 heights 就是当前(i,j ) 位置能往上延伸的最大高度
int n =matrix.size() , m , ans =0;
if (n ==0) return 0;
m =matrix[0].size() ;
vector<int> heights(m +1, 0);
heights[m] =-1;
for(int i =0; i< n; i++)
{
// 一行一行处理
for(int j =0; j< m; j++)
{
if(matrix[i][j] =='0')
heights[j] =0;
else
heights[j] ++;
}
stack<int> st;
for(int j =0; j <=m; j++)
{
while( !st.empty() && heights[j] < heights[st.top()])
{
int cur =st.top();
st.pop();
if(st.empty())
ans =max(ans, heights[cur] *j);
else
ans =max(ans, heights[cur] * (j -st.top() -1));
}
st.push(j);
}
}
return ans;
}
};
|