155.Min Stack
https://leetcode.com/problems/min-stack/
s2存儲(chǔ)最小值脑沿，s1存儲(chǔ)棧本身叉信。
class MinStack {
private:
stack<int> s1;
stack<int> s2;
public:
void push(int x) {
s1.push(x);
if (s2.empty() || x <= getMin()) s2.push(x);
}
void pop() {
if (s1.top() == getMin()) s2.pop();
s1.pop();
}
int top() {
return s1.top();
}
int getMin() {
return s2.top();
}
};
FB面經(jīng)：Min Queue
minque存儲(chǔ)最小值，
class MinQueue{
queue<int> que;
deque<int> minque;
public:
void push(int x) {
if(que.size() == 0) {
que.push(x);
minque.push_back(x);
} else {
que.push(x);
while(!minque.empty() && minque.back() > x) {
minque.pop_back();
}
minque.push_back(x);
}
}
void pop() {
if(que.size() == 0) return;
if(que.front() == minque.front())
minque.pop_front();
que.pop();
}
int front() {
return que.front();
}
int getMin(){
return minque.front();
}
};
232.Implement Queue using Stacks
class Queue {
stack<int> input, output;
public:
void push(int x) {
input.push(x);
}
void pop(void) {
peek();
output.pop();
}
int peek(void) {
if (output.empty())
while (input.size())
output.push(input.top()), input.pop();
return output.top();
}
bool empty(void) {
return input.empty() && output.empty();
}
};
225.implement Stack using Queues
class Stack {
queue<int> que;
public:
// Push element x onto stack.
void push(int x) {
que.push(x);
int n = que.size() - 1;
for(int i = 0; i < n; i++) {
que.push(que.front());
que.pop();
}
}
// Removes the element on top of the stack.
void pop() {
que.pop();
}
// Get the top element.
int top() {
return que.front();
}
// Return whether the stack is empty.
bool empty() {
return que.empty();
}
};
