栈和队列（二）

栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。

public class SortedStack {

    
    private Stack A  , B;
    public SortedStack() {
        A = new Stack<>();
        B = new Stack<>();
    }

    public void push(int val) {
        //如果栈为空，直接入栈
        if(A.isEmpty()) A.push(val);
        else {
            //将A中小于val的值放入B,val入栈，再将B中元素依次入A
            while (val>A.peek()){
                B.push(A.pop());
            }
            A.push(val);
            if (!B.isEmpty()){
                A.push(B.pop());
            }
        }
    }
    public void pop() {
        if (A.isEmpty()){
            return;
        }
        A.pop();
    }
    public int peek() {
        if (A.isEmpty()){
            return -1;
        }
        return A.peek();
    }
    public boolean isEmpty() {
        return A.isEmpty();
    }
}

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。

public class SimplifyPath {
    public static String simplifyPath(String path) {
        //将path分割返回字符串数组
        String[] strs = path.split("/");
        Deque deque = new ArrayDeque<>();
        for (String str :strs){
            if ("..".equals(str)){
                deque.pollLast();
            }else if (str.length()>0 && !".".equals(str)){
                deque.offerLast(str);
            }
        }
        StringBuilder builder = new StringBuilder();
        if (deque.isEmpty()){
            builder.append("/");
        }else {
            while (!deque.isEmpty()){
                builder.append("/");
                builder.append(deque.pollFirst());
            }
        }
        return builder.toString();
    }
}

https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

public class evalRPN {

    public static int evalRPN(String[] tokens) {
        Stack stack = new Stack<>();
        for (int i=0;i
            if (isNumber(tokens[i])){
                stack.push(Integer.valueOf(tokens[i]));
            }else {
                Integer num1 = Integer.valueOf(stack.pop());
                Integer num2 = Integer.valueOf(stack.pop());
                if ("+".equals(tokens[i])){
                    stack.push(num2+num1);
                }else if ("*".equals(tokens[i])){
                    stack.push(num2*num1);
                }else if ("/".equals(tokens[i])){
                    stack.push(num2/num1);
                }else if ("-".equals(tokens[i])){
                    stack.push(num2-num1);
                }
            }
        }
        return stack.pop();
    }
    public static boolean isNumber(String numStr){
        return !("+".equals(numStr) || "-".equals(numStr) || "*".equals(numStr) || "/".equals(numStr));
    }

    public static void main(String[] args) {
        String[] tokens = {"4","3","-"};
        System.out.println(evalRPN(tokens));
    }
}

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

public class removeDuplicate {
    public static String removeDuplicates(String s) {
        Deque deque = new LinkedList(); //双边队列
        char[] charArray = s.toCharArray();
        for (int i=0;i
            if (!deque.isEmpty() && deque.getLast().equals(charArray[i])){
                deque.pollLast();
            }else if (deque.isEmpty() || !deque.getLast().equals(charArray[i])){
                deque.offer(charArray[i]);
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        while (!deque.isEmpty()){
            stringBuilder.append(deque.pollFirst());
        }
        return stringBuilder.toString();

    }

    public static void main(String[] args) {
        String s="abbbabaaa";
        System.out.println(removeDuplicates(s));
    }
}

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

   
   
public class calculate { 
	public int calculate(String s){
        int i = 0;
        int result = 0;
        Deque queue = new LinkedList<>();
        int symbol = 1;  //用来标记正负号
        queue.push(symbol);  //左括号进栈，右括号出栈
        while (i
            if (s.charAt(i)==' '){
                i++;
            }else if (s.charAt(i)=='+'){
                symbol = queue.peek();
                i++;
            }else if (s.charAt(i)=='-'){
                symbol = -queue.peek();
                i++;
            }else if (s.charAt(i)=='('){
                queue.push(symbol);
                i++;
            }else if (s.charAt(i)==')'){
                queue.pop();
                i++;
            }else {
                long count = 0l;
                while (i
                    count = count * 10 + s.charAt(i)-'0';
                    i++;
                }
                result += symbol*count;
            }
        }
        return result;
    }
}

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

**
 * @className MyStack
 * @Author sofia
 * @Date 2022/3/19
 * @Describe  https://leetcode-cn.com/problems/implement-stack-using-queues/
 **/
public class MyStack {
    Queue A;
    public MyStack() {
        A = new LinkedList<>();
    }
    //每次入队时把除当前队列的所有元素先出队再入队
    public void push(int x) {
        A.offer(x);
        for (int i=0;i
            A.offer(A.poll());
        }
    }
    public int pop() {
        return A.poll();
    }
    public int top() {
        return A.peek();
    }
    public boolean empty() {
        return A.isEmpty();
    }
}

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

https://leetcode-cn.com/problems/validate-stack-sequences/

  public boolean validateStackSequences(int[] pushed, int[] popped) {
		int N = pushed.length;
		Stack stack = new Stack();

		int j = 0;
		for (int x: pushed) {
			stack.push(x);
			while (!stack.isEmpty() && j < N && stack.peek() == popped[j]) {
				stack.pop();
				j++;
			}
		}

		return j == N;
	}