232. 用栈实现队列
用一个输入栈,和一个输出栈,数据从输入栈输入,输出时,先判断输出栈是否为空,若为空,则将输入栈的数据转移到输出栈,若不为空则输出输出栈的首个元素,即为队列队首元素。
Java
class MyQueue {
private Stack<Integer> in;
private Stack<Integer> out;
/** Initialize your data structure here. */
public MyQueue() {
in = new Stack<>();
out = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
in.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if(out.empty()){
while(!in.empty()){
out.push(in.pop());
}
}
return out.pop();
}
/** Get the front element. */
public int peek() {
if(out.empty()){
while(!in.empty()){
out.push(in.pop());
}
}
return out.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return in.empty()&&out.empty();
}
}
225. 用队列实现栈
本题的重点在于用两个队列实现插入序列的逆序,方法是,使用一个空队列,每插入一个数,先放入空序列,然后再将另一个数列中数依次插入到后面,即可得到逆序的队列
Java
class MyStack {
private Queue<Integer> in;
private Queue<Integer> out;
/** Initialize your data structure here. */
public MyStack() {
in = new LinkedList<>();
out = new LinkedList<>();
}
/** Push element x onto stack. */
public void push(int x) {
in.offer(x);
while(!out.isEmpty()){
in.offer(out.poll());
}
Queue temp = in;
in = out;
out = temp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return out.poll();
}
/** Get the top element. */
public int top() {
return out.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return out.isEmpty();
}
}
155. 最小栈
每向数据栈中插入一个数x,则往相应的最小栈中插入此时栈中的最小元素值,即为min(min,x),出栈时,数据栈中数和其在最小栈中的对应数一起出栈,min的值则置为最小栈的栈顶值,注意:如果最小栈空了,则应将min置为MAX_VALUE!!
Java
class MinStack {
private Stack<Integer> dataStack;
private Stack<Integer> minStack;
private int min;
/** initialize your data structure here. */
public MinStack() {
dataStack = new Stack<>();
minStack = new Stack<>();
min = Integer.MAX_VALUE;
}
public void push(int x) {
dataStack.push(x);
min = Math.min(min,x);
minStack.push(min);
}
public void pop() {
dataStack.pop();
minStack.pop();
min = minStack.isEmpty()?Integer.MAX_VALUE:minStack.peek();//注意!
}
public int top() {
return dataStack.peek();
}
public int getMin() {
return minStack.peek();
}
}