栈是后入先出(LIFO)的数据结构,首先处理添加到队列的最新元素。
插入操作称作入栈push,在堆栈的末尾添加一个新元素。删除操作称作pop,删除最后一个元素。
动态数组即可实现堆栈。
#include <iostream>
class MyStack {
private:
vector<int> data; // store elements
public:
/** Insert an element into the stack. */
void push(int x) {
data.push_back(x);
}
/** Checks whether the queue is empty or not. */
bool isEmpty() {
return data.empty();
}
/** Get the top item from the queue. */
int top() {
return data.back();
}
/** Delete an element from the queue. Return true if the operation is successful. */
bool pop() {
if (isEmpty()) {
return false;
}
data.pop_back();
return true;
}
};
int main() {
MyStack s;
s.push(1);
s.push(2);
s.push(3);
for (int i = 0; i < 4; ++i) {
if (!s.isEmpty()) {
cout << s.top() << endl;
}
cout << (s.pop() ? "true" : "false") << endl;
}
}
一些基本操作的代码示例:
#include <iostream>
int main() {
// 1. Initialize a stack.
stack<int> s;
// 2. Push new element.
s.push(5);
s.push(13);
s.push(8);
s.push(6);
// 3. Check if stack is empty.
if (s.empty()) {
cout << "Stack is empty!" << endl;
return 0;
}
// 4. Pop an element.
s.pop();
// 5. Get the top element.
cout << "The top element is: " << s.top() << endl;
// 6. Get the size of the stack.
cout << "The size is: " << s.size() << endl;
}
最小栈:检索到最小元素的栈
设计支持push,pop,top操作,在常数时间内检索到最小元素的栈。实现MinStack类。
class MinStack {
private:
stack<long> st;
long min;
public:
//初始化堆栈对象
MinStack() {
}
/*将元素val推入堆栈。
如推入元素依次为1,2,6,4 -> 0,1,5,3. 3,2,4,1 -> 0,-1,2,-1.
*/
void push(int val) {
if(!st.empty()){
long long diff=val-min;
min=diff>0 ? min:val; //栈非空时存储与当前min的差值
st.push(diff);
}
else{
min=val; //栈为空时将val赋值给min
st.push(0); //栈的第一个元素为0
}
}
void pop() {
if(!st.empty()){
long long diff=st.top();
st.pop();
if(diff<0) min-=diff; //diff为负时说明top()比当前min小,所以要更新min
}
}
int top() {
return st.top()<0? min:(min+st.top());
}
int getMin() {
return min;
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
顺利运行通过,但是我没有懂得为什么这里需要定义long类型。将long和long long都改为int类型后发现示例运行结果正确,但是提交后报错:
Line11: int diff=val-min;Line 11: Char 25: runtime error: signed integer overflow: -2147483648 - 2147483647 cannot be represented in type 'int' (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:16:25
标签:val,min,int,最小,long,pop,push From: https://www.cnblogs.com/chordxx/p/17378486.html