目录
int main() {
stack<int> myStack; // 创建一个存储int类型的栈对象
// 检测栈是否为空
cout << "Is stack empty? " << (myStack.empty() ? "Yes" : "No") << endl;
myStack.push(10); // 压入元素10
myStack.push(20); // 压入元素20
myStack.push(30); // 压入元素30
// 输出栈中元素的个数
cout << "Stack size: " << myStack.size() << endl;
// 输出栈顶元素的值
cout << "Top element: " << myStack.top() << endl;
// 弹出栈顶元素
myStack.pop();
// 输出弹出后的栈顶元素的值
cout << "Top element after pop: " << myStack.top() << endl;
return 0;
}
?
template<class T, class Container = vector<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
const T& top()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
这段代码实现了一个栈(stack)类模板,使用适配器模式(Adapter Pattern)来适配不同类型的容器(Container)作为底层实现。
适配器模式是一种结构型设计模式,用于将一个类的接口转换成客户端所期望的另一个接口。在这个例子中,stack类的接口被适配成了与Container类型兼容的接口。
这个问题的关键在于如何在常数时间内检索到最小元素。为了实现这个目标,我们可以使用两个栈:一个栈?
_st
?用于正常的 push 和 pop 操作,另一个栈?_minst
?用于存储当前栈中的最小元素。
class MinStack {
public:
MinStack() {}
void push(int val) {
_st.push(val);
if (_minst.empty() || val <= _minst.top())
{
_minst.push(val);
}
}
void pop() {
if (_minst.top() == _st.top()) {
_minst.pop();
}
_st.pop();
}
int top() {
return _st.top();
}
int getMin() {
return _minst.top();
}
private:
stack<int> _st;
stack<int> _minst;
};
详细步骤:
初始化:我们初始化两个空栈?_st
?和?_minst
。
push 操作:当我们将一个元素?val
?推入栈?_st
?时,我们也需要检查它是否应该被推入栈?_minst
。如果?_minst
?为空,或者?val
?小于等于?_minst
?的栈顶元素,那么我们就将?val
?推入?_minst
。这样,_minst
?的栈顶元素就始终是?_st
?中的最小元素。
pop 操作:当我们从?_st
?中弹出一个元素时,我们需要检查它是否是?_minst
?的栈顶元素。如果是,那么我们也需要从?_minst
?中弹出它,因为这个元素已经不再?_st
?中了,所以?_minst
?的栈顶元素需要更新。
top 操作:这个操作只需要返回?_st
?的栈顶元素。
getMin 操作:这个操作只需要返回?_minst
?的栈顶元素,因为我们已经确保了?_minst
?的栈顶元素始终是?_st
?中的最小元素。
这个算法的关键在于,我们使用了一个额外的栈?_minst
?来存储当前栈中的最小元素,这样我们就可以在常数时间内检索到最小元素。
这个问题的关键在于理解栈的特性,即后进先出(LIFO)。我们可以通过一个辅助栈来模拟压入和弹出的过程,以此来判断给定的弹出序列是否可能。
class Solution {
public:
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
stack<int> st;
int pushi = 0, popi = 0;
while (pushi < pushV.size()) {
st.push(pushV[pushi++]);
while (!st.empty() && st.top() == popV[popi]) {
st.pop();
popi++;
}
}
return popi==popV.size();
}
};
初始化一个空栈,用于模拟压入和弹出的过程。同时,初始化两个指针,pushi
?和?popi
,分别指向?pushV
?和?popV
?的开始位置。
当?pushi
?小于?pushV
?的大小时,执行以下操作:
pushV[pushi]
?压入栈中,并将?pushi
?加一。popV[popi]
。如果相等,说明当前栈顶元素是下一个要弹出的元素,因此我们将其从栈中弹出,并将?popi
?加一。我们需要不断进行这个检查,直到栈为空或者栈顶元素不等于?popV[popi]
。最后,如果?popi
?等于?popV
?的大小,说明?popV
?中的所有元素都正确地被弹出了栈,因此返回?true
。否则,返回?false
。
这个算法的关键在于,它利用了栈的特性来模拟了压入和弹出的过程。当栈顶元素等于 popV[popi] 时,我们知道这个元素应该被弹出,因为在给定的弹出序列中,它是下一个要弹出的元素。
思路:
- 遇到操作数入栈。
- 遇到操作符,取栈顶的两个操作数进行运算,运算结果重新入栈。
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(auto& str:tokens){
if(str=="+"||str=="-"||str=="*"||str=="/"){
int right=st.top();
st.pop();
int left=st.top();
st.pop();
switch(str[0]){
case '+':
st.push(left+right);
break;
case '-':
st.push(left-right);
break;
case '*':
st.push(left*right);
break;
case '/':
st.push(left/right);
break;
}
}
else{
st.push(stoi(str));
}
}
return st.top();
}
};
1、操作数输出
2、操作符
? ? ? ? (1)栈为空进栈
? ? ? ? (2)栈不为空,跟栈顶的操作符比较。
? ? ? ? ? ? ? ? a、比栈顶操作符优先级高,进栈。
? ? ? ? ? ? ? ? b、比栈顶优先级低或相等,出栈顶操作符输出。
带括号的中缀转后缀?
1 + 2*(4 - 5) + 6 /7? >>? 1245-*+67/+?
?
?
class MyQueue {
public:
MyQueue() {}
void push_to_pop(){
if(stpop.empty()){
while (!stpush.empty()) {
stpop.push(stpush.top());
stpush.pop();
}
}
}
void push(int x) { stpush.push(x); }
int pop() {
push_to_pop();
int x=stpop.top();
stpop.pop();
return x;
}
int peek() {
push_to_pop();
return stpop.top();
}
bool empty() { return stpush.empty() && stpop.empty(); }
private:
stack<int> stpush;
stack<int> stpop;
};
/**
* 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();
*/
MyQueue
的类,表示队列。stpush
和stpop
,它们分别表示用于入队和出队操作的两个栈。MyQueue
类中定义了一个默认构造函数MyQueue()
,用于创建一个空的队列。push_to_pop()
函数用于将stpush
栈中的元素转移到stpop
栈中。如果stpop
栈为空,则将stpush
栈中的元素逐个弹出并压入stpop
栈中,以实现队列的先进先出顺序。push(int x)
函数用于将元素x
入队,即将元素压入stpush
栈中。pop()
函数用于出队操作,即从队列中移除并返回队头元素。在执行出队操作之前,首先调用push_to_pop()
函数,确保stpop
栈中有元素。然后从stpop
栈中弹出栈顶元素,并返回该元素。peek()
函数用于获取队头元素,但不对队列进行修改。同样,在执行获取队头元素操作之前,先调用push_to_pop()
函数,确保stpop
栈中有元素。然后返回stpop
栈的栈顶元素。empty()
函数用于判断队列是否为空。当stpush
和stpop
两个栈都为空时,队列为空,返回true
;否则返回false
。这样,通过使用两个栈,我们可以实现队列的基本功能,包括入队、出队、获取队头元素和判断队列是否为空。
在代码的最后,给出了使用MyQueue
类的示例代码。首先创建一个MyQueue
对象obj
,然后可以通过调用obj
的成员函数来进行入队、出队、获取队头元素和判断队列是否为空的操作。