- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- empty() -- Return whether the stack is empty.
之前做过implement queue using stacks,这个题目咋一看觉得解是一样的,但是发现queue不管怎么倒来倒去元素的顺序是不会改变的,像stack那样倒是没用的,但是queue的话,如果把front的元素pop 出来,然后又push到queue的后面,这样,后面的元素就到queue的前面去了。
这个题目直接用一个queue就可以解决, time complexity: push(O(1)), pop (O(n)), top (O(n))
class Stack {
private:
queue<int> q1;
public:
// Push element x onto stack.
void push(int x) {
q1.push(x);
}
// Removes the element on top of the stack.
void pop() {
int size1 = q1.size();
for (int i = 0; i < size1 -1; i++) {
q1.push(q1.front());
q1.pop();
}
q1.pop();
}
// Get the top element.
int top() {
int size1 = q1.size();
for (int i = 0; i < size1 -1; i++) {
q1.push(q1.front());
q1.pop();
}
int tmp = q1.front();
q1.push(q1.front());
q1.pop();
return tmp;
}
// Return whether the stack is empty.
bool empty() {
return q1.empty();
}
};
No comments:
Post a Comment