LeetCode-Solutions/C++/implement-stack-using-queues.cpp at master · pythonpeixun/LeetCode-Solutions · GitHub

History

66 lines (55 loc) · 1.24 KB

Raw

// Time: push: O(n), pop: O(1), top: O(1)

// Space: O(n)

class Stack {

public:

queue<int> q_;

// Push element x onto stack.

void push(int x) { // O(n)

q_.emplace(x);

for (int i = 0; i < q_.size() - 1; ++i) {

q_.emplace(q_.front());

q_.pop();

}

// Remove the element on top of the stack.

void pop() { // O(1)

q_.pop();

}

// Get the top element.

int top() { // O(1)

return q_.front();

}

// Return whether the stack is empty.

bool empty() { // O(1)

return q_.empty();

}

};

// Time: push: O(1), pop: O(n), top: O(1)

// Space: O(n)

class Stack2 {

public:

queue<int> q_;

int top_;

// Push element x onto stack.

void push(int x) { // O(1)

q_.emplace(x);

top_ = x;

}

// Remove the element on top of the stack.

void pop() { // O(n)

for (int i = 0; i < q_.size() - 1; ++i) {

top_ = q_.front();

q_.emplace(top_);

q_.pop();

}

q_.pop();

}

// Get the top element.

int top() { // O(1)

return top_;

}

// Return whether the stack is empty.

bool empty() { // O(1)

return q_.empty();

}

};

LeetCode-Solutions/C++/implement-stack-using-queues.cpp at master · pythonpeixun/LeetCode-Solutions · GitHub

Expand file tree

Breadcrumbs

implement-stack-using-queues.cpp

Latest commit

History

Breadcrumbs

implement-stack-using-queues.cpp

File metadata and controls