栈与队列
1 栈与队列基础
-
栈:先进后出
- 栈是以底层容器完成其所有的工作,对外提供统一的接口,底层容器是可插拔的(也就是说我们可以控制使用哪种容器来实现栈的功能)。
- 我们常用的SGI STL,如果没有指定底层实现的话,默认是以deque为缺省情况下栈的底层结构。
2 用栈实现队列
题目:
使用栈实现队列的下列操作:
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
思路:
两个栈 stkIn和stkOut
- push():stkIn.push()
- pop():stkIn中的元素push到stkOut中,stkOut.pop()
- peek():利用pop,弹出后再压回到stkOut中
- empty():stkIn和stkOut都为空则空
代码:
stack<int> stkIn;
stack<int> stkOut;
MyQueue() {
}
void push(int x) {
stkIn.push(x);
}
int pop() {
if(stkOut.empty()){
while(!stkIn.empty()){
stkOut.push(stkIn.top());
stkIn.pop();
}
}
int result = stkOut.top();
stkOut.pop();
return result;
}
int peek() {
int result = this->pop();
stkOut.push(result);
return result;
}
bool empty() {
return stkIn.empty()&&stkOut.empty();
}
3 队列实现栈
题目:
使用队列实现栈的下列操作:
push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空
思路:
一个队列即可实现模拟栈
代码:
queue<int>que;
MyStack() {
}
void push(int x) {
que.push(x);
}
int pop() {
int size = que.size();
while(size>1){
que.push(que.front());
que.pop();
size--;
}
int result = que.front();
que.pop();
return result;
}
int top() {
return que.back();
}
bool empty() {
return que.empty();
}
4 有效的括号
题目:
给定一个只包括 '(',')','{','}','[',']'
的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
思路:
定义一个栈,检测到括号就压入,遇到对应的消除,出现错误就返回无效,最后栈不为空也是无效
代码:
bool isValid(string s) {
if (s.size() % 2 != 0) return false;
stack<char> st;
for(int i=0;i<s.size();i++){
if(s[i]=='(' || s[i]=='{' || s[i]=='['){
st.push(s[i]);
}
else if(s[i]==')' && !st.empty() && st.top()=='(') st.pop();
else if(s[i]==']' && !st.empty() && st.top()=='[') st.pop();
else if(s[i]=='}' && !st.empty() && st.top()=='{') st.pop();
else return false;
}
if(!st.empty()) return false;
return true;
}
5 删除字符串中的所以后相邻重复项
题目:
给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
思路:
反复跟栈顶元素对比即可
这里可以把string当作栈,这样少一次颠倒的操作
代码:
string removeDuplicates(string s) {
string result;
for(int i=0;i<s.size();i++){
if(result.empty() || s[i]!=result.back()){
result.push_back(s[i]);
}
else{
result.pop_back();
}
}
return result;
}
6 逆波兰表达式求值
题目:
根据 逆波兰表示法,求表达式的值。
思路:
挨个入栈,遇到计算符,开始pop前两个元素进行计算,最后只剩一个元素就是结果
代码:
int evalRPN(vector<string>& tokens) {
stack<long long>pld;
for(int i=0;i<tokens.size();i++){
if(tokens[i]=="+" || tokens[i]=="-" || tokens[i]=="*" || tokens[i]=="/")
{
long long num1=pld.top();
pld.pop();
long long num2=pld.top();
pld.pop();
if(tokens[i] == "+") pld.push(num2 + num1);
if(tokens[i] == "-") pld.push(num2 - num1);
if(tokens[i] == "*") pld.push(num2 * num1);
if(tokens[i] == "/") pld.push(num2 / num1);
}
else {
pld.push(stoll(tokens[i]));
}
}
int result = pld.top();
pld.pop();
return result;
}
注意:
- longlong定义
- stoll:string to longlong
- 注意是num2与num1运算
7 滑动窗口最大值
题目:
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
思路:
定义一个class myQueue,维护单调队列,保存窗口内的单调性,front为最大值
代码:
class Solution {
private:
class myQueue{
public:
deque<int> que;
void pop(int num){
if(!que.empty() && num == que.front()){
que.pop_front();
}
}
void push(int num){
while(!que.empty() && num>que.back()){
que.pop_back();
}
que.push_back(num);
}
int front(){
return que.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
myQueue que;
vector<int>result;
for(int i=0 ; i < k ; i++){
que.push(nums[i]);
}
result.push_back(que.front());
for(int i=k;i<nums.size();i++){
que.pop(nums[i-k]);
que.push(nums[i]);
result.push_back(que.front());
}
return result;
}
};
难点在于时间复杂度为O(n),暴力算法复杂度为O(k * n),要不断在窗口内求最大值。
8 前k个高频元素
题目:
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
思路:
优先级队列priority_queue,
代码:
class Solution {
public:
// 小顶堆
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
// 要统计元素出现频率
unordered_map<int, int> map; // map<nums[i],对应出现的次数>
for (int i = 0; i < nums.size(); i++) {
map[nums[i]]++;
}
// 对频率排序
// 定义一个小顶堆,大小为k
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
// 用固定大小为k的小顶堆,扫面所有频率的数值
for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
pri_que.push(*it);
if (pri_que.size() > k) { // 如果堆的大小大于了K,则队列弹出,保证堆的大小一直为k
pri_que.pop();
}
}
// 找出前K个高频元素,因为小顶堆先弹出的是最小的,所以倒序来输出到数组
vector<int> result(k);
for (int i = k - 1; i >= 0; i--) {
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
};
标签:队列,pop,int,que,result,push
From: https://www.cnblogs.com/mobbu/p/17577474.html