Basic knowledge
Stack
- The stack provides interfaces such as push and pop, and all elements must comply with the first in and last out rule. Therefore, the stack does not provide access function or iterator. Stacks in STL are often not classified as containers, but as container adapter s.
- The bottom implementation of stack can be vector, deque and list, mainly the bottom implementation of array and linked list.
std::stack<int, std::vector<int> > third; // Stack using vector as the underlying container
queue
Queue is a first in first out data structure. Similarly, traversal behavior is not allowed, and iterators are not provided. You can also specify list as the bottom layer implementation
std::queue<int, std::list<int>> third; // Define a queue with list as the underlying container
Queues are also not classified as containers, but as container adapter s.
Examples
232. Implement queue with stack
Use two stacks, one input stack and one output stack. Press the input stack when entering the queue. If the output stack is not empty when leaving the queue, the top element of the output stack will pop up; If the output stack is empty, press all the input stacks into the output stack, and then pop up the top element of the output stack.
If the input stack and output stack are empty, the queue is empty
class MyQueue {
public:
stack<int> stin;
stack<int> stout;
MyQueue() {
}
void push(int x) {
stin.push(x);
}
int pop() {
int re;
if(stout.empty()){
while(!stin.empty()){
re=stin.top();
stin.pop();
stout.push(re);
}
}
re=stout.top();
stout.pop();
return re;
}
int peek() {
int re;
if(stout.empty()){
while(!stin.empty()){
re=stin.top();
stin.pop();
stout.push(re);
}
}
re=stout.top();
return re;
}
bool empty() {
if(stin.empty() && stout.empty()){
return true;
}
return false;
}
};
/**
* 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();
*/
225. Implement stack with queue
Solution 1 uses two queues. When entering the stack, it only enters the queue for q1. When leaving the stack, the other elements except the tail element will enter another queue in turn. At this time, the tail element will be at the head of the queue, and then the elements of another queue will enter the queue in turn.
Return the top element of the stack and directly return the tail element of q1.
class MyStack {
public:
queue<int> q1;
queue<int> q2;
MyStack() {
}
void push(int x) {
q1.push(x);
}
int pop() {
int size=q1.size();
for(int i=0;i<size-1;i++){//Pop up q1
q2.push(q1.front());
q1.pop();
}
for(int i=0;i<size-1;i++){
q1.push(q2.front());
q2.pop();
}
int x=q1.front();
q1.pop();
return x;
}
int top() {
int x=q1.back();
return x;
}
bool empty() {
if(q1.empty()){
return true;
}
else{
return false;
}
}
};
/**
* 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();
*/
Solution 2: when a queue is used to get out of the stack, the other elements except the tail element will be re queued in turn. At this time, the tail element is the top element of the stack.
class MyStack {
public:
queue<int> q;
MyStack() {
}
void push(int x) {
q.push(x);
}
int pop() {
int size=q.size();
int x;
for(int i=0;i<size-1;i++){
x=q.front();
q.pop();
q.push(x);
}
x=q.front();//At this time, the first element of the team is the top element of the stack
q.pop();
return x;
}
int top() {
int x=q.back();
return x;
}
bool empty() {
if(q.empty()){
return true;
}
return false;
}
};
/**
* 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();
*/
The brackets that appear first are paired last, which can be realized by stack
When encountering the left side of the bracket, it will be put into the stack, and when encountering the right side of the bracket, it will be put out of the stack. If the stack is not empty and the element at the top of the stack is paired with this element, it will continue to compare, otherwise it will return false.
If the element of the last stack is 0, it indicates that all parentheses have been paired and returns true.
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(int i=0;i<s.size();i++){
if(s[i]=='(' || s[i]=='[' || s[i]=='{'){
st.push(s[i]);
}
else{
if(!st.empty() && s[i]==')' && st.top()=='('){//! st.empty() is to avoid the situation of ")"
st.pop();
}
else if(!st.empty() && s[i]==']' && st.top()=='['){
st.pop();
}
else if(!st.empty() && s[i]=='}' && st.top()=='{'){
st.pop();
}
else{
return false;
}
}
}
if(st.size()==0){
return true;
}
return false;
}
};
1047. Delete all adjacent duplicates in the string
Solution 1 adjacent duplicates can think of the characteristics of the stack
If the stack is empty or the element at the top of the stack is different from the current element, it will be put into the stack, otherwise it will be out of the stack, and the last is the reverse order of the target string.
class Solution {
public:
string removeDuplicates(string s) {
stack<int> q;
string re;
for(int i=0;i<s.size();i++){
if(q.empty()){
q.push(s[i]);
}
else if(!q.empty() && s[i]==q.top()){
q.pop();
}
else {
q.push(s[i]);
}
}
while(!q.empty()){
re+=q.top();
q.pop();
}
reverse(re.begin(),re.end());
return re;
}
};
The solution 2 string itself is a stack, pop_back() is equivalent to pushing out of the stack_ Back () is equivalent to putting on the stack, and back () returns the top element of the stack.
class Solution {
public:
string removeDuplicates(string s) {
string re;
for(char a:s){
if(re.empty() || re.back()!=a){
re.push_back(a);
}
else{
re.pop_back();
}
}
return re;
}
};
Solution 3 delete operation naturally also wants to think of double pointers
Operate directly on the original string, so it saves space
If s[l]==s[l-1],l --, otherwise L++
class Solution {
public:
string removeDuplicates(string s) {
int l=0;
int r=0;
for(;r<s.size();r++){
s[l]=s[r];
if(l>0 && s[l]==s[l-1]){
l--;
}
else{
l++;
}
}
s.resize(l);
return s;
}
};
150. Evaluation of inverse Polish expression
Inverse Polish
Analysis: the inverse Polish expression is created according to the stack, so it is directly solved with a stack
If the current stack is empty or the current string is not an operator, press the stack (for the convenience of operation, an int stack is built here, so type conversion is required, stoi(): sring to int). If the current string is an operator, it will be out of the stack twice in a row as the right operand and the left operand to press the operation result into the stack. The final result is the element at the top of the stack.
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(int i=0;i<tokens.size();i++){
if(st.empty() || (tokens[i]!="+" && tokens[i]!="-" && tokens[i]!="*" && tokens[i]!="/")){//The current string is a number
st.push(stoi(tokens[i]));
}
else{
int r=st.top();
st.pop();
int l=st.top();
st.pop();
int re;
if(tokens[i]=="+"){
re=l+r;
}
else if(tokens[i]=="-"){
re=l-r;
}
else if(tokens[i]=="*"){
re=l*r;
}
else{
re=l/r;
}
st.push(re);
}
}
return st.top();
}
};
239. Maximum value of sliding window
The idea of this problem is very clear. It is to find the maximum value of the window. The key is how to find this maximum value. If you hard solve it, it will timeout. Therefore, you have to think of a wonderful way to maintain the maximum value of the window, and the maximum value can be updated when the window moves.
Monotone queue is introduced here: the elements of the queue are monotone
This problem needs to realize the monotonous queue by itself, and deque is needed, because it involves the deletion of the head and tail of the team
The queue should contain push(int v): the tail of the queue enters the queue. If v > the tail element of the queue, the tail element leaves the queue until the queue is empty or v < = the tail element of the queue, and then the tail of the queue enters the queue; Otherwise, v directly join the team at the end of the line, and the queue will be monotonous
pop(int v): first out of the queue. If the element to be deleted in the window v = = the first element of the queue, the first element of the queue will be out of the queue (to avoid that the element not in the window is still in the queue); Otherwise, do nothing. In this way, the maximum value can be updated in real time when the window moves.
int front(int v): returns the first element of the queue
- Set the left and right ends of the window. First queue the elements in the first window
- The maximum value of the record window is the first element of the queue. When the window moves, the right endpoint enters the queue, and judge whether the left endpoint is the first element of the queue. If so, pop.
class Solution {
public:
class Myqueue{
public:
deque<int> q;
void push(int v){//Maintain large to small queues
while(!q.empty() && v>q.back()){
q.pop_back();//Out of the team at the end of the team
}
q.push_back(v);//Join the team at the end of the team
}
void pop(int v){
if(!q.empty() && v==q.front()){
q.pop_front();//Team first team
}
}
int front(){
return q.front();
}
};
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
Myqueue q;
vector<int> result;
int l=0;
int r=k;
for(int i=0;i<r;i++){//Join the first k numbers first
q.push(nums[i]);
}
result.push_back(q.front());//Maximum value of the first window
if(nums[l]==q.front()){//When the first window moves forward, judge whether to delete the team head element
q.pop(nums[l]);
}
for(l=1;r<nums.size();r++, l++){
q.push(nums[r]);//Join the team at the right end of the window
result.push_back(q.front());//Record the maximum value of the current window
if(nums[l]==q.front()){//To delete an element equal to the first element of the team, the first element of the team is out of the team
q.pop(nums[l]);
}
}
return result;
}
};
347. Top K high frequency elements
Supplement:
Generally speaking, the top K problem can be realized with a large top heap or a small top heap,
The largest K: small top pile
The smallest K: large top pile
Heap is a complete binary tree. The value of each node in the tree is not less than (or greater than) the value of its left and right children. If the father node is greater than or equal to the left and right, the child is the big top pile, and the child less than or equal to the left and right is the small top pile. From small to large row is small top pile, and from large to small row is large top pile.
The root node of the large top heap is the maximum and the root node of the small top heap is the minimum.
For large top heap: when the maximum value is found, the last element of the binary tree is exchanged at the root node to reconstruct the heap. The final root node is the next largest value.
For this problem, it is more convenient to find the elements with frequency > = k, because the largest elements are replaced every time, and the elements with frequency > = k are left in the end.
- Count the frequency of elements
- Sort according to the frequency of elements. Since you want to find the elements with the highest k, the minimum heap is used
- Since the current stack is arranged from small to large, the results are stored from the back to the front.
class Solution {
public:
class myComparison{
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs){
return lhs.second>rhs.second;//Small top pile
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int ,int>umap;
for(int i=0;i<nums.size();i++){
umap[nums[i]]++;
}
priority_queue<pair<int,int>,vector<pair<int,int> >,myComparison >pri_que;
for(unordered_map<int,int>::iterator it=umap.begin();it!=umap.end();it++){
pri_que.push(*it);
if(pri_que.size()>k){
pri_que.pop();
}
}
vector<int> result(k);
for(int i=k-1;i>=0;i--){
result[i]=pri_que.top().first;
pri_que.pop();
}
return result;
}
};
summary
- Due to the particularity of stack structure, it is very suitable for symmetric matching.
- To find the maximum value of the window, consider the monotonic queue.
- Generally speaking, the top K problem or partial sorting can be realized with large top heap or small top heap. The largest K: small top heap. The smallest K: large top pile