Java复习常用的数据结构和常用面试题之栈和队列

提示：看之前请先学习链表知识点

Java复习常用的数据结构和常用面试题之数组和链表

文章目录

Java复习常用的数据结构和常用面试题之数组和链表
堆栈和队列
- 栈(Stack)
- - 栈的常用方法
  - 用链表实现栈
- 队列(Queue)
- - - 基本概念
    - jdk自带队列的基本操作
    - 用单链表自己实现队列（linkQueue）
- 实战题目
- - 思路解法
  - - [844. 比较含退格的字符串](https://leetcode-cn.com/problems/backspace-string-compare/)
    - [20. 有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)
    - 150.逆波兰表达式求值问题
    - [232. 用栈实现队列](https://leetcode-cn.com/problems/implement-queue-using-stacks/)
    - [225. 用队列实现栈](https://leetcode-cn.com/problems/implement-stack-using-queues/)
总结

堆栈和队列

Stack - First In First Out (FIFO)
• Array or linked List
Queue - First In Last Out (FILO)
• Array or linked List

栈(Stack)

先进后出的结构特点

栈的常用方法

boolean empty( )——如果堆栈是空的，则返回true，当堆栈包含元素时，返回false。
Object peek( )———–返回位于栈顶的元素，但是并不在堆栈中删除它。
Object pop( )————返回位于栈顶的元素，并在进程中删除它。
Object push (Object element )———将element压入堆栈，同时也返回element。
int search(Object element)———在堆栈中搜索element，如果发现了，则返回它相对于栈顶
的偏移量。否则，返回-1。

用链表实现栈

package com.gdpu.Stack;

import linkedList.ListNode;

import java.util.Iterator;


public class Stack implements Iterable{

    //记录首结点
    private ListNode head;
    //栈中元素的个数
    private int N;

    public Stack() {
        this.head = new ListNode(null,null);
        this.N=0;
    }

    //判断当前栈中元素个数是否为0
    public boolean isEmpty(){
        return N==0;
    }

    //获取栈中元素的个数
    public int size(){
        return N;
    }

    //把t元素压栈
    public void push(T t){
        //找到首结点指向的第一个结点
        ListNode oldFirst = head.next;
        //创建新结点
        ListNode newNode = new ListNode(t, null);
        //让首结点指向新结点
        head.next = newNode;
        //让新结点指向原来的第一个结点
        newNode.next=oldFirst;
        //元素个数+1；
        N++;
    }
    
    //弹出栈顶元素
    //返回位于栈顶的元素，并在进程中删除它
    public T pop(){
        //找到首结点指向的第一个结点
        ListNode oldFirst = head.next;
        if (oldFirst==null){
            return null;
        }
        //让首结点指向原来第一个结点的下一个结点
        head.next=oldFirst.next;
        //元素个数-1；
        N--;
        return (T) oldFirst.val;
    }
    
    //返回位于栈顶的元素，但是并不在堆栈中删除它。
    public T peek(){
        //找到首结点指向的第一个结点
        ListNode oldFirst = head.next;
        if (oldFirst==null){
            return null;
        }
        return (T) oldFirst.val;
    }


    @Override
    public Iterator iterator() {
        return new SIterator();
    }

    private class SIterator implements Iterator{
        private ListNode n;

        public SIterator(){
            this.n=head;
        }

        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.val;
        }
    }
}

队列(Queue) 基本概念

队列（Queue):简称队。是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。其操作特性为先进先出（First In First Out，FIFO），并且只允许在队尾进，队头出。

队头（Front）：允许删除的一端，又称队首

队尾（Rear）：允许插入的一端

空队列：不包含任何元素的空表

jdk自带队列的基本操作

Queue queue1 = new linkedList();

方法	作用
add()	入队（若失败则抛出IllegalStateException异常）
offer()	将指定元素插入队列，成功返回true，否则返回false
element()	获取队头的值，但不出队（若队列为空则抛出异常NoSuchElementException）
peek()	获取队头的值，但不出队（若队列为空则返回null
poll()	获取并移除队头（若队列空则返回null）
remove	获取并移除队头（若队列空则抛出NoSuchElementException异常）

用单链表自己实现队列（linkQueue）

package Queue;

import linkedList.ListNode;

import java.util.Iterator;


public class linkQueue implements Iterable {
    // 队头
    private ListNode front;
    // 队尾
    private ListNode rear;
    // 元素个数
    private int size;

    
    public linkQueue() {
        rear = front = null;
        size=0;
    }

    
    public void offer(T data) {
        ListNode node = new ListNode(data);
        //如果是空队列
        if (isEmpty()) {
            front = rear = node;
        } else {
            //在尾部插入
            rear.next = node;
            rear = node;
        }
        size++;
    }


    
    public T poll() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        ListNode delete = front;
        //更改头部节点
        front = delete.next;
        delete.next=null; // help GC
        //数量减1
        size--;

        if (size == 0) {
            // 删除掉最后一个元素时，front值已经为null，但rear还是指向该节点，需要将rear置为null
            // 最后一个结点front和rear两个引用都没指向它，帮助GC处理该节点对象
            rear = front;
        }

        return (T) delete.val;
    }

    
    public T peek(){
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return (T) front.val;
    }

    
    public boolean isEmpty() {
        return front == null && rear == null;
    }

    
    public int size() {
        return this.size;
    }

    //自己添加遍历模块
    @Override
    public Iterator iterator() {
        return new QIterator();
    }

    private class QIterator implements Iterator{
        private ListNode n = new ListNode();

        public QIterator(){
            n.next=front;
        }

        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.val;
        }
    }
}

实战题目

844. 比较含退格的字符串
232. 用栈实现队列
225. 用队列实现栈
20. 有效的括号
150.逆波兰表达式求值问题

思路解法 844. 比较含退格的字符串

暴力遍历，按规则翻译出最终的字符串

package com.gdpu.day1;

public class NO_844_backspaceCompare {

    public boolean backspaceCompare(String S, String T) {
        return transfer(S).equals(transfer(T));
    }
    
    public String transfer(String str){
        StringBuffer ret = new StringBuffer();
        for (int i =0;i0){
                    ret.deleteCharAt(ret.length()-1);
                }
            }
        }
        return ret.toString();
    }
}

双指针分别逆序遍历S和T

    public boolean doublePointCompare(String S, String T) {
        int i = S.length() - 1;
        int j = T.length() - 1;
        int skipS = 0, skipT = 0;
        while (i > 0 || j > 0) {
            while (i >= 0) {
                if (S.charAt(i) == '#') {
                    skipS++;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    //找到一个无法消除的了，跳出
                    break;
                }
            }
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    skipT++;
                } else if (skipT > 0) {
                    skipS--;
                    j--;
                } else {
                    //找到一个无法消除的了，跳出
                    break;
                }
            }
            //如果两步的索引都是大于等于0
            if (i >= 0 && j >= 0) {
                //如果此时双方无法消除的不相等
                if (S.charAt(i) != T.charAt(j)) {
                    return false;
                }
            } else {
                //排除了都是大于等于0，如果有一个是大于等于0
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }

20. 有效的括号

用辅助栈的机制解

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        //如果是奇数，必然是不能匹配完全
        if (n % 2 == 1) {
            return false;
        }
        //定义一个映射map
        Map pairs = new HashMap() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Stack stack = new Stack();
        for (int i = 0;i 
150.逆波兰表达式求值问题 
class Solution {
       public int evalRPN(String[] tokens) {
        Stack stack = new Stack();
        for (int i = 0;i 
232. 用栈实现队列 
class MyQueue {
    //输入栈
    private Stack inStack;
    //输出栈
    private Stack outStack;  

    
    public MyQueue() {
    
    this.inStack=new Stack();
    this.outStack=new Stack();

    }
    
    //入栈
    public void push(int x) {
        inStack.push(x);
    }

    //出栈
    public int pop() {
        //如果输出栈为空，则将输入栈全部弹出并压入输出栈栈中，然后outStack.pop()
        if(outStack.isEmpty()){
            while(!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }

    //取得队头数据
    public int peek() {
        if(outStack.isEmpty()){
            while(!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}

 
225. 用队列实现栈 
-用两个队列
  
class MyStack {
   Queue queue1;
   Queue queue2;

   
   public MyStack() {
       queue1 = new linkedList();
       queue2 = new linkedList();
   }
   //入栈
   public void push(int x) {
       //当前新增元素后进队列
       queue1.offer(x);
       //老队列后进
       while (!queue2.isEmpty()){
           queue1.offer(queue2.poll());
       }

       //搞完后更新老队列
       //其实此时的queue1已经是空队列了
       Queue tmp = queue1;
       queue1 = queue2;
       queue2 = tmp;
   }

   //出栈
   public int pop() {
       return queue2.poll();
   }

   public int top() {
       return queue2.peek();
   }

   public boolean empty() {
       return queue2.isEmpty();
   }

}
 
-用1个队列
  
class MyStack {
    Queue queue;

    
    public MyStack() {
        queue = new linkedList();
    }
    
    
    public void push(int x) {
        int n = queue.size();
        queue.offer(x);
        for (int i = 0; i < n; i++) {
            queue.offer(queue.poll());
        }
    }
    
    
    public int pop() {
        return queue.poll();
    }
    
    
    public int top() {
        return queue.peek();
    }
    
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

 
总结 
通过以上几道题，反复去求解多种解法，栈和队列就基本掌握了

Java复习常用的数据结构和常用面试题之栈和队列

Java相关栏目本月热门文章