class MyQueue {
Stack<Integer> stackOne = new Stack<>();
Stack<Integer> stacktwo = new Stack<>();
int front;
/** Initialize your data structure here. */
public MyQueue() {
}
/** Push element x to the back of queue. */
public void push(int x) {
if (stackOne.isEmpty()) {
front = x;
}
stackOne.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (!empty()) {
if (stacktwo.isEmpty()) {
while(!stackOne.isEmpty()) {
stacktwo.push(stackOne.pop());
}
}
return stacktwo.pop();
}
else
return -1;
}
/** Get the front element. */
public int peek() {
if (!empty()) {
if (!stacktwo.isEmpty()) {
return stacktwo.peek();
}
return front;
}
else return -1;
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stackOne.isEmpty() && stacktwo.isEmpty();
}
}
2.用隊列實作棧
225. 用隊列實作棧
LeetCode--棧和隊列篇
思路：
class MyStack {
Queue<Integer> queueOne = new LinkedList<>();
Queue<Integer> queueTwo = new LinkedList<>();
/** Initialize your data structure here. */
public MyStack() {
}
/** Push element x onto stack. */
public void push(int x) {
queueTwo.offer(x);
while (!queueOne.isEmpty()) {
queueTwo.offer(queueOne.poll());
}
Queue<Integer> temp = new LinkedList<>();
temp = queueOne;
queueOne = queueTwo;
queueTwo = temp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
if (!empty()) {
if (!queueOne.isEmpty()) {
return queueOne.poll();
}
return -1;
}
else {
return -1;
}
}
/** Get the top element. */
public int top() {
if (!empty()) {
return queueOne.peek();
}
else
return -1;
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queueOne.isEmpty() && queueTwo.isEmpty();
}
}
class MinStack {
Stack<Node> stack = new Stack<>();
class Node {
int min;
int value;
public Node(int min,int value) {
this.min = min;
this.value = value;
}
}
/** initialize your data structure here. */
public MinStack() {
}
public void push(int val) {
if (stack.isEmpty()) {
stack.push(new Node(val,val));
}else {
stack.push(new Node(Math.min(stack.peek().min,val),val));
}
}
public void pop() {
if (!stack.isEmpty()) {
stack.pop();
}
}
public int top() {
if (!stack.isEmpty()) {
return stack.peek().value;
}
else
return -1;
}
public int getMin() {
if (!stack.isEmpty()) {
return stack.peek().min;
}
else
return -1;
}
}
4.有效的括号
20. 有效的括号
LeetCode--棧和隊列篇
思路：如果是左括号，則存入對應的右括号，如果遇到右括号則
1.先看棧是否有元素，沒有則說明隻有半個括号，直接return false；
2.不空則和棧頂比較是否相同，不相同return false；
3.循環走完，看棧是否空，空則比對成功
class Solution {
Stack<Character> stack = new Stack<>();
public boolean isValid(String s) {
char[] chs = s.toCharArray();
for (int i = 0; i < chs.length; i++) {
if (chs[i] == '{')
stack.push('}');
else if (chs[i] == '[') {
stack.push(']');
}
else if (chs[i] == '(') {
stack.push(')');
}
else {
if (!stack.isEmpty()) {
if (chs[i] == stack.peek())
stack.pop();
else
return false;
}else {
return false;
}
}
}
return stack.size() == 0;
}
}
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
//維持一個單調棧
int[] result = new int[temperatures.length];
Deque<Integer> stack= new LinkedList<>();
for (int i = 0; i < temperatures.length; i++) {
int temp = temperatures[i];
while (!stack.isEmpty() && temp > temperatures[stack.peek()]) {
int number = stack.pop();
result[number] = i - number;
}
stack.push(i);
}
//後面的預設就是零,不用管了
// while (!stack.isEmpty()) {
// int number = stack.pop();
// result[number] = 0;
// }
return result;
}
}
6.下一個更大元素II
503. 下一個更大元素 II
LeetCode--棧和隊列篇
思路: 因為是循環數組的原因,到末尾又從頭開始,是以可以周遊兩遍,使用 i % len 來定位數組元素, 維持單調棧
class Solution {
public int[] nextGreaterElements(int[] nums) {
int len = nums.length;
int[] result = new int[len];
Arrays.fill(result,-1);
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < 2 * len - 1; i++) {
int num = nums[i % len];
while (!stack.isEmpty() && nums[stack.peek()] < num) {
int temp = stack.pop();
result[temp] = num;
}
if (i < len) stack.push(i);
}
return result;
}
}
