leetcode简单题目中的栈的全部题目
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。 有效字符串需满足：
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。解题思路：按序读取字符串中的每一位，当读取到 ( , { , [ 三种左边的符号时，向栈中添加一个对应的右结束括号，当读取到 ) , } , ] 的时候，判断栈顶的元素是否与其相对应，如果相对应，弹出栈顶元素，继续读取字符串中的字符，直到结束，若在读取判断的过程中出现了不相等，则直接返回false；
public boolean isVaild(String s){ if (s.isEmpty()){ return true; } Stack<Character> stack = new Stack<Character>(); for(char c:s.toCharArray()){ if(c=='(') stack.push(')'); else if (c=='{') stack.push('}'); else if (c=='[') stack.push(']'); else if(stack.empty()||c!=stack.pop()) return false } if(stack.empty()) return true; return false; }设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。pop() —— 删除栈顶的元素。top() —— 获取栈顶元素。getMin() —— 检索栈中的最小元素。解题思路：设计两个栈，其中一个栈负责添加元素，另外一个栈的栈顶存放当前最小的元素即可。
class MinStack{ private Stack<Integer> stack; private Stack<Integer> minStack; public MinStack(){ stack = new Stack<>(); minStack = new Stack<>(); } public void push(int x){ stack.push(x); if(minStack.isEmpty()||x<=minStack.peek()) minStack.push(x); } public void pop(){ if(stack.pop().equals(minStack.peek())) minStack.pop(); } public int top(){ return stack.peek(); } public int getMin(){ return minStack.peek(); } }使用队列实现栈的下列操作：
push(x) – 元素 x 入栈pop() – 移除栈顶元素top() – 获取栈顶元素empty() – 返回栈是否为空解题思路：采用两个队列即可
class MyStack{ private Queue<Integer> queue1; private Queue<Integer> queue2; public MyStack(){ queue1 = new LinkedList<>(); queue2 = new LinkedList<>(); } public void push(int x){ queue1.add(x); } public int pop(){ while(queue1.size()>1) queue2.add(queue1.poll()); int ans = queue1.poll(); while(queue2.size()>0) queue1.add(queue2.poll()); return ans; } public int top(){ while(queue1.size()>1) queue2.add(queue1.poll()); int ans = queue1.peek(); queue2.add(queue1.poll()); while(queue2.size()>0) queue1.add(queue2.poll()); return ans; } public boolean empty(){ return queue1.isEmpty(); } }给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。 输入: nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出: [-1,3,-1]
解题思路：
class Solution{ public int[] nextGreaterElement(int[] nums1,int[] nums2){ Stack<Integer> stack = new Stack<>(); HashMap<Integer,Integer>map = new HashMap<>(); int[] res = new int[nums1.length]; for (int i=0;i<nums2.length;i++){ while(!stack.empty() && nums2[i]>stack.peek()) map.put(stack.pop(),nums2[i]) stack.push(nums[i]); } while(!stack.empty){ map.put(stack.pop(),-1); } for (int i =0;i<nums1.length;i++) res[i] = map.get(nums1[i]) return res } }你现在是棒球比赛记录员。 给定一个字符串列表，每个字符串可以是以下四种类型之一：
1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。 “+”（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。 “D”（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。 “C”（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。 你需要返回你在所有回合中得分的总和。
class Soultion{ public int calPoints(String[] ops){ int res = 0; Stack<Integer> stack = new Stack<>(); for(String str:ops){ switch (str){ case "C": stack.pop(); break; case "D": stack.push(stack.peek()*2); break; case "+": Integer tmpPeek = stack.pop(); Integer tmp = stack.peek()+tmpPeek; stcak.push(tmpPeek); stack.push(tmp); default: stack.push(Integer.valueOf(str)); break; } } while(!stack.empty) res+=stack.pop(); return res; } }给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
class Solution{ public boolean backsapceCompare(String S,String T){ return build(S).equals(build(T)); } public String build(String str){ Stack<Character> stack = new Stack<>(); for(Char c:str.toCharArray()){ if(c!='#') stack.push(c); else if(!stack.empty()) stack.pop(); return String.vauleOf(stack); } } }给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
class Solution { public String removeDuplicates(String S) { Stack<Character> stack = new Stack<>(); for(Character c : S.toCharArray()){ if(stack.isEmpty()) stack.push(c); else if(c==stack.peek()) stack.pop(); else stack.push(c); } StringBuilder sb = new StringBuilder(); while(!stack.isEmpty()) sb.append(stack.pop()); return sb.reverse().toString(); } }给你一个目标数组 target 和一个整数 n。每次迭代，需要从 list = {1,2,3…, n} 中依序读取一个数字。
请使用下述操作来构建目标数组 target ：
Push：从 list 中读取一个新元素， 并将其推入数组中。Pop：删除数组中的最后一个元素。 如果目标数组构建完成，就停止读取更多元素。 题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。请返回构建目标数组所用的操作序列。
题目数据保证答案是唯一的。
class Solution { public List<String> buildArray(int[] target, int n) { List<String> list = new ArrayList<>(); int flag = 1; for(int num:target){ if(num==flag) list.add("Push"); else{ while(num!=flag){ list.add("Push"); list.add("Pop"); flag++; } list.add("Push"); } flag++; } return list; } }