文章目录

• 中缀表达式转后缀表达式
• 栈实现后缀表达式
• 十进制转十六进制
• 十六进制转十进制
• 回文字符判断
• 括号匹配问题
• 双端栈
• 队列
• • queue接口定义
  • 结构实现
• 数据结构文件遍历
• 栈实现队列
• 队列实现栈
• 循环队列
• 双端栈
• • 接口
  • 结构

中缀表达式转后缀表达式

public class InfixToSuffix {
    public static void main(String[] args) {
        String str = "80+65";
        str = infixToSuffix(str);
        System.out.println(str);
    }
    public static String infixToSuffix(String str){
        ArrayStack<String> opStack = new ArrayStack<>();
        ArrayList<String> suffixList = new ArrayList<>();
        str = insertBlanks(str);
        String[] tokens = str.split(" ");
        for (String token:tokens){
            if(token.length() == 0) continue;
            if(isOperator(token)){
                while (true){
                    if(opStack.isEmpty()|| opStack.peek().equals("(")||priority(opStack.peek())<priority(token)){
                        opStack.push(token);
                        break;
                    }
                    suffixList.add(opStack.pop());
                }
            }else if(token.equals("(")){
                opStack.push((token));
            }else  if(token.equals(")")){
                while (!opStack.peek().equals("(")){
                    suffixList.add(opStack.pop());
                }
                opStack.pop();
            }else if(isNumber(token)){
                suffixList.add(token);
            }else {
                throw new IllegalArgumentException(""+str);
            }
        }
        while (!opStack.isEmpty()){
            suffixList.add(opStack.pop());
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < suffixList.size(); i++) {
            sb.append(suffixList.get(i));
            sb.append(' ');
        }
        return  sb.toString();
    }

    private static int priority(String token){
        if(token.equals("+") || token.equals("-")){
            return 0;
        }
        if(token.equals("*") || token.equals("/")){
            return 1;
        }
        return -1;
    }

    private  static  boolean isNumber(String token){
        return token.matches("\\d+");
    }
    private static boolean isOperator(String token){
        return token.equals("+")||token.equals("-")||token.equals("*")||token.equals("/");
    }
    public static String insertBlanks(String str){
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if(c == '(' || c == ')'|| c == '+' || c == '-' || c == '*' || c == '/'
            ){
                stringBuilder.append(" ");
                stringBuilder.append(c);
                stringBuilder.append(" ");
            }
            else stringBuilder.append(c);
        }
        return stringBuilder.toString();
    }
}

栈实现后缀表达式

public class SuffixCalculator {
    public static void main(String[] args) {
        String infixExpression = "(10+20/2*3)/2+8";
        String suffixxpression = InfixToSuffix.infixToSuffix(infixExpression);
        int result = evaluateSuffix(suffixxpression);
        System.out.println(result);

    }
    private static int evaluateSuffix(String str){
        ArrayStack<Integer> stack = new ArrayStack<>();
        String [] tokens  = str.split(" ");
        for(String token:tokens){
            if(token.length() == 0){
                continue;
            }
            if(isNumber(token)){
                stack.push(new Integer(token));
            }
            else {
                processAnOperator(stack,token);
            }
        }
        return  stack.pop();
    }
    private  static  void  processAnOperator(ArrayStack<Integer> stack,String token){
        int num_1 = stack.pop();
        int num_2 = stack.pop();
        if(token.equals("+")){
            stack.push(num_2 + num_1);
        }
        else if(token.equals("-")){
            stack.push((num_2-num_1));
        }
        else if(token.equals("*")){
            stack.push(num_2*num_1);
        }
        else if(token.equals("/")){
            stack.push(num_2/num_1);
        }
    }
    private static boolean isNumber(String token){
        return token.matches("\\d+");
    }
}

十进制转十六进制

public class DecToHex {
    public static void main(String[] args) {
        int num = 654321;
        ArrayStack<String> numStack = new ArrayStack<>();
        while (num != 0){
            int a = num % 16;
            if(a < 10){
                numStack.push(a+" ");
            }
            else {
                numStack.push((char)(a+55) + " ");
            }
            num /= 16;
        }
        StringBuilder sb = new StringBuilder();
        while (!numStack.isEmpty()){
            sb.append(numStack.pop());
        }
        System.out.println(sb.toString());
    }
}

十六进制转十进制

public class HexToDec {
    public static void main(String[] args) {
        String hex = "9FBF1";
        ArrayStack<Character> stack = new ArrayStack<>();
        for (int i = 0; i < hex.length(); i++) {
            stack.push(hex.charAt(i));
        }
        int sum = 0;
        int mi = 0;
        while (!stack.isEmpty()){
            char c = stack.pop();
            sum = (int) (sum + getNumber(c)*Math.pow(16,mi));
            mi ++;
        }
        System.out.println(sum);
    }
    private static int getNumber(char c){
        if(!(c >='0' && c <='9' || c>= 'A' && c<='F')){
            throw new IllegalArgumentException("wrong char!");
        }
        if(c >= '0' && c <= '9' ) return c-'0';
        else return c-'A'+10;
    }
}

回文字符判断

public class JudgingPalindrome {
    public static void main(String[] args) {
        solution_1();
        solution_2();
    }

    private static boolean solution_2() {
        String text = "上海自来水来自海上";
        int i = 0;
        int j =text.length()-1;
        while (true){
            if(text.charAt(i) == text.charAt(j)){
                i++;j--;
            }
            else  return false;
            if(j<=i) return  true;
        }
    }

    private static void solution_1() {
        String text = "上海自来水来自海上";
        ArrayStack<Character> stack = new ArrayStack<>();
        for (int i = 0; i < text.length(); i++) {
            if(text.length() %2 == 1 && i == text.length() /2) continue;
            char c = text.charAt(i);
            if (stack.isEmpty()) {
                stack.push(c);
            }
            else {
                if(c != stack.peek()) stack.push(c);
                else  stack.pop();
            }
        }
        System.out.println(stack.isEmpty());
    }
}

括号匹配问题

public class MatchBracket {
    public static void main(String[] args) {
        solution_1();
        solution_2();

    }

    private static void solution_2() {
        String str = "{()[[()]]<{()>}()";
        HashMap<Character,Character> map = new HashMap<>();
        map.put('{','}');
        map.put('[',']');
        map.put('(',')');
        map.put('<','>');
        ArrayStack<Character> stack = new ArrayStack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if(stack.isEmpty()){
                stack.push(c);
            }else {
                char top = stack.peek();
                if(map.containsKey(top) && c == map.get(']')){
                    stack.pop();
                }else  stack.push(c);
            }
        }
        System.out.println(stack.isEmpty());
    }

    private static void solution_1() {
        String str = "{{()[()]<>}}";
        ArrayStack<Character> stack = new ArrayStack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (stack.isEmpty()) {
                stack.push(c);
            }
            else  {
                char top = stack.peek();
                if(top -c == -1 || top - c == -2){
                    stack.pop();
                }
                else stack.push(c);
            }
        }
        System.out.println(stack.isEmpty());
    }
}

双端栈

public class ArrayDoubleEndStack <E> implements Iterable<E> {
//    左端栈栈顶
    private  int ltop;
//    右端栈栈顶
    private  int rtop;
//    存储元素的容器
    private E[] data;
//    数组容器的默认容量
    private static int DEFAULT_CAPACITY = 10;
    public ArrayDoubleEndStack(){
        data = (E[]) new Object[DEFAULT_CAPACITY];
        ltop = -1;
        rtop = data.length;
    }
//  进栈的方法
    public void  pushLeft(E element){
        if(ltop +1 == rtop){
            resize(data.length * 2);
        }
        data[++ltop] = element;
    }
    public void  pushRight(E element){
        if(ltop +1 == rtop ){
            resize(data.length*2);
        }
        data[--rtop] = element;
    }
    private void resize(int newLen){
        E[] newDate = (E[]) new Object[newLen];
//        复制左端栈的元素
        for (int i = 0; i < ltop; i++) {
            newDate[i]=data[i];
        }
//      复制右端栈的长度
        int index = rtop;
        for (int i = newLen-sizeRight(); i < newLen; i++) {
            newDate[i] = data[index++];
        }
        rtop = newLen-sizeRight();
        data = newDate;
    }
    public E peekLeft(){
        if(isLeftEmpty()){
            throw  new IllegalArgumentException("left Stack is null");
        }
        return  data[ltop];
    }
    public E peekRight(){
        if(isRightEmpty()){
            throw new IllegalArgumentException("Right stack is null");
        }
        return data[rtop];
    }
//    出栈
    public E popLeft(){
        if(isLeftEmpty()){
            throw  new IllegalArgumentException("left Stack is null");
        }
        E ret = data[ltop--];
        if(sizeRight() + sizeLift() <= data.length /4 && data.length > DEFAULT_CAPACITY){
            resize(data.length/2);
        }
        return  ret;
//        if(sizeRight() + sizeLift())
    }
    public E popRight(){
        if(isRightEmpty()){
            throw new IllegalArgumentException("Right stack is null");
        }
        E ret = data[rtop++];
        if(sizeLift() + sizeRight() <= data.length /4 && data.length > DEFAULT_CAPACITY){
            resize(data.length/2);
        }
        return ret;
    }
    public boolean isLeftEmpty(){
        return ltop==-1;
    }
    public boolean isRightEmpty(){
        return rtop == data.length;
    }
    public  int sizeLift(){
        return ltop+1;
    }
    public int sizeRight(){
        return data.length - rtop;
    }
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        if(isLeftEmpty() && isRightEmpty()){
            sb.append("]");
            return sb.toString();
        }
//        左空又不空
//        if(isRightEmpty() && !isRightEmpty()){

//        }
//        遍历左边
        for (int i = 0; i <= ltop; i++) {
            sb.append(data[i]);
            if(i == ltop && isRightEmpty()){
                sb.append("]");
                return sb.toString();
            }else sb .append(",");
        }
//        遍历右边
        for (int i = rtop; i < data.length; i++) {
            sb.append(data[i]);
            if(i == data.length-1){
                sb.append("]");
            }
            else  sb.append(",");
        }
        return sb.toString();
    }
    @Override
    public Iterator<E> iterator() {
        return new ArrayDoubleEndStackIterator();
    }
    class ArrayDoubleEndStackIterator implements  Iterator<E>{
        private ArrayList<E> list;
        private Iterator<E> it;
        public ArrayDoubleEndStackIterator(){
            list = new ArrayList<>();
            for (int i = 0; i < ltop;i++) {
                list.add(data[i]);
            }
            for (int i = rtop; i < data.length; i++) {
                list.add(data[i]);
            }
            it = list.iterator();
        }
        @Override
        public boolean hasNext() {
            return it.hasNext();
        }

        @Override
        public E next() {
            return it.next();
        }
    }
}

队列

queue接口定义

public interface Queue<E> extends Iterable<E> {
//    入队
    public  void  offer(E element);
    public E poll(); //出队
    public E element(); //查看队顶元素
    public  boolean isEmpty();//判断是不是空
    public void clear();//清空
    public int size(); //获取元素个数
}

结构实现

public class ArrayQueue<E> implements Queue<E> {
    private ArrayList<E> list;
    public  ArrayQueue(){list = new ArrayList<>();}
    @Override
    public void offer(E element) {
        list.add(list.size(),element);
    }

    @Override
    public E poll() {
        return list.remove(0);
    }

    @Override
    public E element() {
        return list.get(0);
    }


    @Override
    public int size() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public void clear() {
        list.clear();
    }
    public String toStrong(){
        return list.toString();
    }
    @Override
    public Iterator<E> iterator() {
        return list.iterator();
    }
    public  boolean equals(Object o){
        if(o == null) return false;
        if(this == o) return true;
        if(o instanceof ArrayQueue){
            ArrayQueue other = (ArrayQueue) o;
            return  list.equals(other.list);
        }
        return false;
    }
}

数据结构文件遍历

public class DirectoryTraversal {
    public static void main(String[] args) {
        File dir = new File("D:");
        ArrayQueue<File> queue = new ArrayQueue<>();
        queue.offer(dir);
        while (!queue.isEmpty()){
            File file = queue.poll();
            System.out.println("{"+file.getName()+"}");
            File[] files = file.listFiles();
            for (File f: files) {
                if(f.isFile()) System.out.println(f.getName());
                else  queue.offer(f);
            }
        }
    }
}

栈实现队列

public class StackToQueue {
    public static void main(String[] args) {
        QueueImplByStack<Integer> queueImplByStack = new QueueImplByStack<>();
        for (int i = 1; i <=5 ; i++) {
            queueImplByStack.offer(i);
        }
        System.out.println(queueImplByStack);
        System.out.println(queueImplByStack.poll());
        System.out.println(queueImplByStack.element());
        System.out.println(queueImplByStack.poll());
    }
}
class  QueueImplByStack<E> implements Queue<E>{
    private ArrayStack<E> stack_A;
    private ArrayStack<E> stack_B;
    public QueueImplByStack(){
        stack_A = new ArrayStack<>();
        stack_B = new ArrayStack<>();
    }

    @Override
    public void offer(E element) {
        stack_A.push(element);
    }

    @Override
    public E poll() {
        if(isEmpty()){
            throw  new IllegalArgumentException("queue is null");
        }
        while (stack_A.size()!=1){
            stack_B.push(stack_A.pop());
        }
        E ret = stack_A.pop();
        while (!stack_B.isEmpty()){
            stack_A.push(stack_B.pop());
        }
        return ret;
    }

    @Override
    public E element() {
        if(isEmpty()){
            throw  new IllegalArgumentException("queue is null");
        }
        while (stack_A.size()!=1){
            stack_B.push(stack_A.pop());
        }
        E ret = stack_A.peek();
        while (!stack_B.isEmpty()){
            stack_A.push(stack_B.pop());
        }
        return ret;
    }

    @Override
    public int size() {
        return stack_A.size();
    }

    @Override
    public boolean isEmpty() {
        return  stack_A.isEmpty();

    }

    @Override
    public void clear() {
        stack_A.clear();
        stack_B.clear();
    }

    @Override
    public Iterator<E> iterator() {
        return null;
    }
    public String toString(){
        return stack_A.toString();
    }
}

队列实现栈

public class QueueToStack {
    public static void main(String[] args) {
        StackImplByQueue<Integer> stack = new StackImplByQueue<>();
        System.out.println(stack);
        for (int i = 1; i <= 5; i++) {
            stack.push(i); //队列A
        }
        System.out.println(stack.toString());
        System.out.println(stack.pop());
        System.out.println(stack);  //队列B

    }
}
class StackImplByQueue<E> implements Stack<E> {
    private ArrayQueue<E> queueA;
    private ArrayQueue<E> queueB;

    public StackImplByQueue() {
        queueA = new ArrayQueue<>();
        queueB = new ArrayQueue<>();
    }

    @Override
    public int size() {
        if (queueA.isEmpty() && queueB.isEmpty()) {
            return 0;
        } else if (!queueA.isEmpty()) {
            return queueA.size();
        } else {
            return queueB.size();
        }
    }

    @Override
    public boolean isEmpty() {
        return queueA.isEmpty() && queueB.isEmpty();
    }

    @Override
    public void push(E element) {
        if (queueA.isEmpty() && queueB.isEmpty()) {
            queueA.offer(element);
        } else if (!queueA.isEmpty()) {
            queueA.offer(element);
        } else {
            queueB.offer(element);
        }
    }

    @Override
    public E pop() {
        if (isEmpty()) {
            return null;
        }
        E ret = null;
        if (!queueA.isEmpty()) {
            while (queueA.size() != 1) {
                queueB.offer(queueA.poll());
            }
            ret = queueA.poll();
        } else {
            while (queueB.size() != 1) {
                queueA.offer(queueB.poll());
            }
            ret = queueB.poll();
        }
        return ret;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        E ret = null;
        if (!queueA.isEmpty()) {
            while (queueA.size() != 1) {
                queueB.offer(queueA.poll());
            }
            ret = queueA.poll();
            queueB.offer(ret);
        } else {
            while (queueB.size() != 1) {
                queueA.offer(queueB.poll());
            }
            ret = queueB.poll();
            queueA.offer(ret);
        }
        return ret;
    }

    @Override
    public void clear() {
        queueA.clear();
        queueB.clear();
    }

    @Override
    public Iterator<E> iterator() {
        if (isEmpty()) {
            return queueA.iterator();
        } else if (!queueA.isEmpty()) {
            return queueA.iterator();
        } else {
            return queueB.iterator();
        }
    }
    @Override
    public String toString() {
        if (isEmpty()) {
            return "[]";
        } else if (!queueA.isEmpty()) {
            return queueA.toString()+"!!";
        } else {
            return queueB.toString();
        }
    }

}

循环队列

public class ArrayLoopQueue<E> implements Queue<E> {
//    存储数据的容器
    private E[] data;
//    队首指针
    private int font;
//    队尾指针
    private int rear;
    private  int size;
//    默认容量
    private static int DEFAUL_CAPACITY = 10;
    public ArrayLoopQueue(){
        data = (E[]) new Object[DEFAUL_CAPACITY+1];
        font = rear = size =0;
    }
    @Override
    public void offer(E element) {
//        判断满没有
        if((rear +1)% data.length == font ){
            resize(data.length *2-1);
        }
        data[rear] = element;
        rear = (rear+1)% data.length;
        size++;
    }

    @Override
    public E poll() {
        if(isEmpty()){
            throw new IllegalArgumentException("queue 为空");
        }
        E ret = data[font];
        font = (font+1) % data.length;
        size --;
        if(size<= (data.length-1)/4 && data.length-1 > DEFAUL_CAPACITY){
            resize(data.length/2 +1);
        }
        return ret;
    }

    @Override
    public E element() {
        if ((isEmpty())) throw new IllegalArgumentException("queue is null ");
        return data[font];
    }

    private void resize(int newLen){
        E[] newData = (E[]) new  Object[newLen];
        int index =0;
        for(int i = font;i!=rear;i = (i+1)& data.length){
            newData[index++] = data[i];
        }
        data = newData;
        font = 0;
        rear = index;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return font == rear;
    }

    @Override
    public void clear() {
    data = (E[]) new Object[DEFAUL_CAPACITY];
    font = rear = size =0;
    }
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()){
            sb.append(']');
            return sb.toString();
        }
        for(int i = font; i!= rear;i = (i+1)% data.length){
            sb.append(data[i]);
            if((i+1)% data.length == rear) sb.append(']');
            else {
                sb.append(',');
                sb.append(' ');
            }
        }
        return sb.toString();
    }
    @Override
    public boolean equals(Object o){
        if(o == null){
            return false;
        }
        if (this == o) {
            return true;
        }
        if (o instanceof ArrayLoopQueue){
            ArrayLoopQueue<E> other = (ArrayLoopQueue<E>) o;
            if (size!= other.size){
                return false;
            }
            int i = font;
            int j = other.font;
            while (i != rear){
                if(data[i].equals(other.data[j])){
                    return false;
                }
                i = (i+1)% data.length;
                j = (j+1)%other.data.length;
            }
            return true;
        }
        return false;
    }
    @Override
    public Iterator iterator() {
        return new ArrayLoopQueueIterator();
    }
    class ArrayLoopQueueIterator implements Iterator<E> {
        private  int cur = font;
        @Override
        public boolean hasNext() {
            return cur != rear;
        }

        @Override
        public E next() {
            E ret = data[cur];
            cur = (cur+1)%data.length;
            return ret;
        }
    }
}

双端栈

接口

public interface Deque<E> extends Queue<E> {
    public  void addFirst(E element);
    public  void addLast(E element);
    public E removeFist();
    public E removeLast();
    public  E getFirst();
    public  E getLast();
}

结构

public class ArrayDeque<E> implements Deque<E>, Stack<E> {
    private E[] data;
    private int front;
    private int rear;
    private int size;
    private static int DEFAULT_CAPACITY = 10;
    public ArrayDeque(){
        data = (E[]) new Object[DEFAULT_CAPACITY+1];
        front = 0;
        rear = 0;
        size = 0;
    }
    @Override
    public void addFirst(E element) {
        if((rear +1) % data.length == front){
            resize(data.length * 2 -1);
        }
        front = (front-1 + data.length)% data.length;
        data[front] = element;
        size++;
    }

    @Override
    public void addLast(E element) {
        if((rear +1) % data.length == front){
            resize(data.length * 2 -1);
        }
        data[rear] = element;
        rear = (rear +1) % data.length;
        size++;
    }
    private void resize(int newLen){
        E[] newData = (E[]) new Object[newLen];
        int index = 0;
        for(int i = front;i != rear; i = (i+1)% data.length){
            newData[index++] = data[i];
        }
        data = newData;
        front= 0;
    }


    @Override
    public E removeFist() {
        if(isEmpty()){
            throw new IllegalArgumentException("queue is null");
        }
        E ret = data[front];
        front = (front+1)% data.length;
        size--;
        if(size<=(data.length-1)/4 && data.length -1 > DEFAULT_CAPACITY){
            resize(data.length/2);
        }
        return ret;
    }

    @Override
    public E removeLast() {
        if(isEmpty()){
            throw new IllegalArgumentException("queue is null");
        }
        rear = (rear-1+ data.length)% data.length;
        E ret = data[rear];
        size--;
        if(size<=(data.length-1)/4 && data.length -1 > DEFAULT_CAPACITY){
            resize(data.length/2+1);
        }
        return ret;
    }

    @Override
    public E getFirst() {
        if(isEmpty()){
            throw new IllegalArgumentException("queue is null");
        }
        return data[front];
    }

    @Override
    public E getLast() {
        if(isEmpty()){
            throw new IllegalArgumentException("queue is null");
        }
        return data[((rear-1)+ data.length)% data.length];
    }

    @Override
    public void offer(E element) {
        addFirst(element);
    }

    @Override
    public E poll() {
        return removeFist();
    }

    @Override
    public E element() {
        return getFirst();
    }
    @Override
    public  E peek(){
        return getLast();
    }
    @Override
    public boolean isEmpty() {
        return size == 0 && front ==rear;
    }

    @Override
    public void push(E element) {
        addLast(element);
    }

    @Override
    public E pop() {
        return removeLast();
    }

    @Override
    public void clear() {
        E[] data = (E[]) new Object[DEFAULT_CAPACITY];
        front = 0;
        size=0;
        rear = 0;
    }

    @Override
    public int size() {
        return size;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()) {
            sb.append(']');
            return sb.toString();
        }
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            sb.append(data[i]);
            if ((i + 1) % data.length == rear) {
                sb.append(']');
            } else {
                sb.append(',');
                sb.append(' ');
            }
        }
        return sb.toString();
    }

    @Override
    public Iterator<E> iterator() {
        return new ArrayDequeIterator();
    }

    class ArrayDequeIterator implements Iterator<E> {
        private int cur = front;

        @Override
        public boolean hasNext() {
            return cur != rear;
        }

        @Override
        public E next() {
            E ret = data[cur];
            cur = (cur + 1) % data.length;
            return ret;
        }
    }
}