20. 有效的括号
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for(int i=0;i<s.length();i++){
char ch=s.charAt(i);
// 如果是左括号就入栈
if(ch=='(' || ch=='[' || ch=='{'){
stack.push(ch);
}else{
// 如果是右括号就进行匹配
// 如果是右括号栈为空了则不是有效的括号
if(stack.empty()){
return false;
}else{
// 是右括号且匹配成功了就弹出
char ch2=stack.peek();
if(ch2=='('&&ch==')' || ch2=='['&&ch==']' || ch2=='{'&&ch=='}' ){
stack.pop();
}else{
return false;
}
}
}
}
// 字符串遍历完成但是栈不为空则不是有效括号
if(!stack.empty()){
return false;
}
return true;
}
}
150. 逆波兰表达式求值
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(String x:tokens){
if(x.equals("+") || x.equals("-") ||x.equals("*") ||x.equals("/")){
int num1 = stack.pop();
int num2 = stack.pop();
switch(x){
case "+":
stack.push(num2 + num1);
break;
case "-":
stack.push(num2 - num1);
break;
case "*":
stack.push(num2 * num1);
break;
case "/":
stack.push(num2 / num1);
break;
}
} else{
stack.push(Integer.parseInt(x));
}
}
return stack.pop();
}
}
JZ31 栈的压入、弹出序列
JZ31 栈的压入、弹出序列
思路:
pushV中的元素依次入栈,和popV中的元素比较,如果相同就出栈,遍历结束后,如果栈为空,那么就说明是正确的弹出顺序.
代码:
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pushV int整型一维数组
* @param popV int整型一维数组
* @return bool布尔型
*/
public boolean IsPopOrder (int[] pushV, int[] popV) {
Stack<Integer> stack = new Stack<>();
int j=0;
for(int i=0;i<pushV.length;i++){
stack.push(pushV[i]);
while(j<popV.length && !stack.empty() && stack.peek()==popV[j]){
stack.pop();
j++;
}
}
if(stack.isEmpty()){
return true;
}
return false;
}
}
622. 设计循环队列
class MyCircularQueue {
public int[] elem;
public int front;
public int rear;
public MyCircularQueue(int k) {
elem = new int[k+1];
}
public boolean enQueue(int value) {
if(isFull()){
return false;
}
elem[rear] = value;
rear = (rear+1) % elem.length;
return true;
}
public boolean deQueue() {
if(isEmpty()){
return false;
}
front = (front+1) % elem.length;
return true;
}
public int Front() {
if(isEmpty()){
return -1;
}
return elem[front];
}
public int Rear() {
if(isEmpty()){
return -1;
}
int index = (rear==0?elem.length-1:rear-1);
return elem[index];
}
public boolean isEmpty() {
if(front==rear){
return true;
}
return false;
}
public boolean isFull() {
if((rear+1) % elem.length == front){
return true;
}
return false;
}
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue obj = new MyCircularQueue(k);
* boolean param_1 = obj.enQueue(value);
* boolean param_2 = obj.deQueue();
* int param_3 = obj.Front();
* int param_4 = obj.Rear();
* boolean param_5 = obj.isEmpty();
* boolean param_6 = obj.isFull();
*/
225. 用队列实现栈
class MyStack {
private Queue<Integer> q1;
private Queue<Integer> q2;
public MyStack() {
q1 = new LinkedList<Integer>();
q2 = new LinkedList<Integer>();
}
public void push(int x) {
if(!q1.isEmpty()){
q1.offer(x);
}else if(!q2.isEmpty()){
q2.offer(x);
}else{
q1.offer(x);
}
}
public int pop() {
if(empty()){
return -1;
}
if(!q1.isEmpty()){
int size=q1.size();
for(int i=0;i<size-1;i++){
q2.offer(q1.poll());
}
return q1.poll();
}else{
int size = q2.size();
for(int i=0;i<size-1;i++){
q1.offer(q2.poll());
}
return q2.poll();
}
}
public int top() {
if(empty()){
return -1;
}
if(!q1.isEmpty()){
int size=q1.size();
int ret=-1;
for(int i=0;i<size;i++){
ret = q1.poll();
q2.offer(ret);
}
return ret;
}else{
int size = q2.size();
int ret=-1;
for(int i=0;i<size;i++){
ret = q2.poll();
q1.offer(ret);
}
return ret;
}
}
public boolean empty() {
return q1.isEmpty() && q2.isEmpty();
}
}
/**
* 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();
* boolean param_4 = obj.empty();
*/
232. 用栈实现队列
class MyQueue {
Stack<Integer> stackA;
Stack<Integer> stackB;
public MyQueue() {
stackA = new Stack<>();
stackB = new Stack<>();
}
public void push(int x) {
stackA.push(x);
}
public int pop() {
if(empty()){
return -1;
}
if(stackB.empty()){
while(!stackA.empty()){
stackB.push(stackA.pop());
}
}
return stackB.pop();
}
public int peek() {
if(empty()){
return -1;
}
if(stackB.empty()){
while(!stackA.empty()){
stackB.push(stackA.pop());
}
}
return stackB.peek();
}
public boolean empty() {
return stackA.isEmpty() && stackB.isEmpty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
