155-最小栈
- 解法一：此题最简单的做法就是实现两个栈，一个记录当前元素，一个记录当前序列的最小元素。
代码：
class MinStack {
public:
stack<int> s;
stack<int> m;
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
s.push(x);
if (m.empty())
m.push(x);
else{
int cur_min = m.top();
if (x < cur_min)
m.push(x);
else
m.push(cur_min);
}
}
void pop() {
s.pop();
m.pop();
}
int top() {
return s.top();
}
int getMin() {
return m.top();
}
};
- 解法二：更厉害一点的做法是，只用一个栈，当前最小值用一个int型记录。如果新压栈的数比当前最小值小，就要把当前最小值先压栈，然后更新当前最小值。
不过，当新压栈的数与当前最小值相等时，比较容易出错。需要注意：1）当新压栈的数与当前最小值最小时，也要将最小值先压栈，否则出栈时会出错；2）当栈为空时，第一个元素要压栈两次，否则出栈最后一个元素时，会报段错误。
代码：
class MinStack {
public:
stack<int> s;
int cur_min;
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
if (s.empty()){
s.push(x); //第一个元素要压栈两次
s.push(x);
cur_min = x;
}
else{
if (x <= cur_min){ //等号很重要
s.push(cur_min);
s.push(x);
cur_min = x;
}
else{
s.push(x);
}
}
}
void pop() {
if (s.top() == cur_min){
s.pop();
cur_min = s.top();
s.pop();
}
else{
s.pop();
}
}
int top() {
return s.top();
}
int getMin() {
return cur_min;
}
};
225-用队列实现栈
- 解法一：本题最直观的做法还是搞两个队列，一个平时存数据，一个pop的时候临时存放。
push：O(1)，pop：O(n)。 - 解法二：另一种做法是只使用一个队列，在push的时候就把数据的顺序调整成栈的存放顺序。
比如push a, b, c：
1）push a，队列中只有a
2）push b，此时队列为b a，右边为队头，左边为队尾。将a出队后再push，队列变为a b。
3）push c，此时队列为c a b，将a和b分别出队再入队，队列变为a b c.
push：O(n), pop: O(1)。
代码：
class MyStack {
public:
/** Initialize your data structure here. */
queue <int> q1;
int top_ele;
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
if (q1.empty())
q1.push(x);
else {
int q_len = q1.size();
q1.push(x);
while (q_len--) {
int tmp = q1.front();
q1.pop();
q1.push(tmp);
}
}
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int rm_ele = q1.front();
q1.pop();
return rm_ele;
}
/** Get the top element. */
int top() {
return q1.front();
}
/** Returns whether the stack is empty. */
bool empty() {
return q1.empty();
}
};
232-用栈实现队列
双栈法，一个主栈，一个辅助栈。push的时候只push到主栈中。
解法一：维护一个top值，pop的时候将主栈的元素都倒到辅助栈中，完成pop再倒回主栈中。
时间复杂度：push O(1), pop O(n), top O(1)
这种做法比较简单，就不放代码了。解法二：分别维护一个top_all和top_s1用来存放模拟队列的队头和主栈的栈底。pop的时候将主栈的元素都倒到辅助栈中，完成pop后也不倒回，之后每次pop都从辅助栈中取，直到辅助栈为空，再将主栈元素倒入辅助栈中。平均下来，每个元素pop的代价也是O(1)。
时间复杂度：push O(1), pop O(1), top O(1)。
代码：
class MyQueue {
public:
/** Initialize your data structure here. */
stack <int> s1; // store elements with stack order
stack <int> s2; // store elements with queue order
int top_all, top_s1;
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
if (s1.empty() && s2.empty()) {
top_all = x;
}
if (s1.empty() && !s2.empty()) {
top_s1 = x; // s1栈底元素，用于s2空时更新队头元素
}
s1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
int rm_ele;
if (!s2.empty()) {
// pop element from s2
rm_ele = s2.top();
s2.pop();
// update top_all
if (s2.empty())
top_all = top_s1;
else
top_all = s2.top();
return rm_ele;
}
// transmit all elements from s1 to s2
while (!s1.empty()) {
int tmp = s1.top();
s2.push(tmp);
s1.pop();
}
rm_ele = s2.top();
s2.pop();
if (!s2.empty())
// update top_all
top_all = s2.top();
return rm_ele;
}
/** Get the front element. */
int peek() {
return top_all;
}
/** Returns whether the queue is empty. */
bool empty() {
return s1.empty() && s2.empty();
}
};
不过，这两种解法提交后运行时间都是0ms，反而是如果不维护top元素，每次取队头元素都要倒一遍数据的做法用时比较多，可能测试样例中比较多peek操作。而维护top元素的代价很小，所以还是很值得的。
