Day1 2022.11.8
09.用两个栈实现队列
自己实现
直接通过一个vector容器粗暴实现，时间复杂度相对较高，虽然空间复杂度较低
代码如下：
class CQueue {
vector<int> vec1;
public:
CQueue() {
}
void appendTail(int value) {
vec1.push_back(value);
}
int deleteHead() {
if(!vec1.size()) return -1;
else
{
int val=vec1[0];
vec1.erase(vec1.begin());
return val;
}
}
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/
代码表现
题解
两个栈：栈A（作为入队） 栈B（作为出队）
- 入队时不断一个个push进栈A
- 出队时
- 若B不为空，则pop B的栈顶
- 若B中为空，则将A中所有元素一个个pop并push进B中（即颠倒顺序，使A底变到B顶）
class CQueue {
vector<int> A;
vector<int> B;
public:
CQueue() {
}
void appendTail(int value) {
A.push_back(value);
}
int deleteHead() {
if(!B.empty())
{
int val=B.back();
B.pop_back();
return val;
}
else
{
while(!A.empty())
{
int val=A.back();
A.pop_back();
B.push_back(val);
}
if(B.empty())return -1;
else
{
int val=B.back();
B.pop_back();
return val;
}
}
}
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/
代码表现
hint：
-
vector的erase方法的参数采用迭代器更好，例如vec.erase(vec.begin()+j)
-
vector的pop_back()方法只负责删除末尾元素，但是不返回，返回值为void类型
30.包含min函数的栈
自己实现
主要是通过一个正常的栈和一个不断push每个新的最小值的栈来做到具有min功能的栈数据结构
代码如下：
class MinStack {
public:
vector<int> vec;
vector<int> vec_min;
public:
/** initialize your data structure here. */
MinStack() {
vec_min.push_back(INT_MAX);
}
void push(int x) {
vec.push_back(x);
if(x<=vec_min[vec_min.size()-1])vec_min.push_back(x);
}
void pop() {
if(vec[vec.size()-1]==vec_min[vec_min.size()-1]) vec_min.pop_back();
vec.pop_back();
}
int top() {
return vec[vec.size()-1];
}
int min() {
return vec_min[vec_min.size()-1];
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->min();
*/
代码表现
hint：
- 整数可表示的最大值：INT_MAX