155. Min Stack / 225. Implement Stack using Queues

2019-11-10 19:55:51

字体：大中小

来源：转载

供稿：网友

Min Stack题目描述代码实现Implement Stack using Queues题目描述代码实现

155. Min Stack

题目描述

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. getMin() – Retrieve the minimum element in the stack. Example:

MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin(); --> Returns -3.minStack.pop();minStack.top(); --> Returns 0.minStack.getMin(); --> Returns -2.

代码实现

使用vector来模拟：

class MinStack {public: vector<int> stk; /** initialize your data structure here. */ MinStack() { } void push(int x) { stk.push_back(x); } void pop() { stk.pop_back(); } int top() { return stk.back(); } int getMin() { int min_val = INT_MAX; int s_len = stk.size(); for(int i = 0; i < s_len; i++) { if(stk[i] < min_val) min_val = stk[i]; } return min_val; }};/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */

使用两个栈来模拟：

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(); }};

225. Implement Stack using Queues

题目描述

Implement the following Operations of a stack using queues.

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.

Notes:

You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid.Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

代码实现

实现方法一：

class MyStack {private: queue<int> q1;public: /** Initialize your data structure here. */ MyStack() { } /** Push element x onto stack. */ void push(int x) { q1.push(x); } /** Removes the element on top of the stack and returns that element. */ int pop() { int len = q1.size(); for(int i = 0; i < len - 1; i++) { int tmp = q1.front(); q1.pop(); q1.push(tmp); } int res = q1.front(); q1.pop(); return res; } /** Get the top element. */ int top() { return q1.back(); } /** Returns whether the stack is empty. */ bool empty() { return !q1.size()?true:false; }};/** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * bool param_4 = obj.empty(); */

当然还有另外一种思路，就是使用在push的时候进行排序：

class MyStack {public: queue<int> que; // Push element x onto stack. void push(int x) { que.push(x); for(int i=0;i<que.size()-1;++i){ que.push(que.front()); que.pop(); } } // Removes the element on top of the stack. int pop() { int res = que.front(); que.pop(); return res; } // Get the top element. int top() { return que.front(); } // Return whether the stack is empty. bool empty() { return que.empty(); }};

上一篇：MyBatis学习笔记（一）IntelliJ IDEA的第一个MyBatis Demo

下一篇：linux命令行