目录
①括号匹配
给定一个只包括?
'('，')'，'{'，'}'，'['，']'?的字符串?s?，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭
输入：s = "()" 输出：true
输入：s = "(]" 输出：false
class Solution{
public boolean isValid(String s){
if(s == null && s.length() ==0){
return false;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++){
char ch = s.charAt(i);
if(ch =='(' || ch == '[' || ch == '{') {
stack.push(ch);
}else {
if (stack.empty()){
System.out.println("左括号多");
return false;
}
char tmp = stack.peek();
if(tmp == '{' && ch == '}' || tmp == '[' && ch == ']' || tmp == '(' && ch == ')' ){
System.out.println("括号匹配成功");
stack.pop();
}else {
System.out.println("括号匹配不成功");
return false;
}
}
}
if (!stack.empty()){
System.out.println("左括号多");
return false;
}else {
System.out.println("括号匹配成功");
return true;
}
}
}②最小栈
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]输出：
[null,null,null,null,-3,null,0,-2]解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); ? --> 返回 -3.
minStack.pop();
minStack.top(); ? ? ?--> 返回 0.
minStack.getMin(); ? --> 返回 -2.
?
class MinStack{
private Stack<Integer> stack1;
private Stack<Integer> minStack;
public MinStack(){
stack1 = new Stack<>();
minStack = new Stack<>();
}
public void push(int val){
stack1.push(val);
if(minStack.empty()){
minStack.push(val);
}else{
int top = minStack.peek();
if(val <= top){
minStack.push(val);
}
}
}
public void pop(){
int val = stack1.pop();
if(!minStack.empty()){
int top = minStack.peek();
if (val == top){
minStack.pop();
}
}
}
public int top(){
if (stack1.empty()){
return -1;
}else {
return stack1.peek();
}
}
public int getMin(){
if (minStack.empty()){
return -1;
}else{
return minStack.peek();
}
}
}
③队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
一个队列是实现不了栈的，必须是两个队列，因为栈是先进后出，队列是先进先出
class MyStack{
private Queue<Integer> qu1;
private Queue<Integer> qu2;
public MyStack(){
qu1 = new LinkedList<>();
qu2 = new LinkedList<>();
}
public void push(int x){
if(!qu1.isEmpty()){
qu1.offer(x);
}else if(!qu2.isEmpty()){
qu2.offer(x);
}else {
//指定一个入队
qu1.offer(x);
}
}
public boolean empty(){
return qu1.isEmpty() && qu2.isEmpty();
}
public int pop(){
if (empty()) return -1;
if(!qu1.isEmpty()){
int size = qu1.size();
for (int i = 0; i < size - 1; i++){
int x = qu1.poll();
qu2.offer(x);
}
return qu1.poll();
}else {
int size = qu2.size();
for (int i = 0; i < size - 1; i++){
int x = qu2.poll();
qu1.offer(x);
}
return qu2.poll();
}
}
public int top(){
if (empty()) return -1;
if(!qu1.isEmpty()){
int size = qu1.size();
int x = -1;
for (int i = 0; i < size; i++){
x = qu1.poll();
qu2.offer(x);
}
//最后一次入队正好是栈顶元素
return x;
}else {
int size = qu2.size();
int x = -1;
for (int i = 0; i < size; i++){
x = qu2.poll();
qu1.offer(x);
}
//最后一次入队正好是栈顶元素
return x;
}
}
}
④栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
一个栈是实现不了栈的，必须是两个栈，因为栈是先进后出，队列是先进先出
?
class MyQueue{
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public MyQueue(){
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public boolean empyt(){
return stack1.empty() && stack2.empty();
}
public void push(int x){
stack1.push(x);
}
public int pop(){
if (empyt()) return -1;
if (stack2.empty()){
while (!stack1.empty()){
int x = stack1.pop();
stack2.push(x);
}
}
return stack2.pop();
}
public int peek(){
if (empyt()) return -1;
if (stack2.empty()){
while (!stack1.empty()){
int x = stack1.pop();
stack2.push(x);
}
}
return stack2.peek();
}
}