栈和队列-Java

目录

一、栈

     1.1 概念

     1.2 栈的使用

     1.3 栈的模拟实现 

     1.4 栈的应用场景

    1.5 概念区分

二、队列

    2.1 概念

    2.2 队列的使用

    2.3 队列的模拟实现

    2.4 循环队列

三、双端队列

四、面试题


一、栈

     1.1 概念

        栈:一种特殊的线性表,只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底,栈中的元素遵循先进后出的原则。

        压栈:栈的插入操作,也叫进栈或入栈,在栈顶插入数据出栈:栈的删除操作,在栈顶删除数据

        

     1.2 栈的使用

方法 解释
Stack() 构造一个空的栈
E push(E e) 将 e 入栈,并返回e
E pop() 将栈顶元素出栈并返回
E peek() 获取栈顶元素
int size() 获取栈中有效元素个数
boolean empty() 检测栈是否为空
public static void main(String[] args) {
    Stack<Integer> stack = new Stack();
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);

    System.out.println(stack.size());//5
    //获取栈顶元素
    System.out.println(stack.peek());//5
    System.out.println(stack);  //[1, 2, 3, 4, 5]

    stack.pop();//出栈  5

    System.out.println(stack.size());//4
    System.out.println(stack);  //[1, 2, 3, 4]

    System.out.println(stack.empty());//false
}

     1.3 栈的模拟实现 

        由图可知Stack继承了VectorVectorArrayList类似,都是动态的顺序表,不同的是Vector是线程安全的。

public class MyStack {
    int[] elem;
    int usedSize;
    public MyStack(){
        elem = new int[3];
    }
    //判断栈是否满了
    private boolean CapacityIsFull(){
        return  usedSize == elem.length;
    }
    //确保容量充足
    private  void  ensureCapacity(){
        if(CapacityIsFull()){
            elem = Arrays.copyOf(elem,elem.length*2);
        }
    }
    //入栈
    public int push(int data){
        ensureCapacity();
        elem[usedSize++] = data;
        return  data;
    }
    //获取栈顶元素
    public int peek(){
        if(usedSize == 0){
            throw new StackNullEception("栈为空,无法获取栈顶元素");
        }
        return  elem[usedSize-1];
    }

    //出栈
    public int pop (){
        int e = peek();
        usedSize--;
        return  e;
    }
    //获取栈的长度
    public  int size(){
        return  usedSize;
    }
    //判断栈是否为空
    public boolean empty(){
        return  usedSize == 0;
    }
}

     1.4 栈的应用场景

        1. 改变元素的序列

1. 若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是()
        A: 1,4,3,2      B: 2,3,4,1      C: 3,1,4,2      D: 3,4,2,1
2. 一个栈的初始状态为空。现将元素 1 2 3 4 5 A B C D E 依次入栈,然后再依次出栈,则元素出栈的顺
序是( )。
A: 12345ABCDE      B: EDCBA54321      C: ABCDE12345      D: 54321EDCBA
        2. 将递归转化为循环
//递归方式
void printList(Node head){
    if(head == null){
        return;
    }
    printList(head.next);
    System.out.println(head.val+" ");
}
//循环方式
void printList2(Node head){
    if(head == null){
        return;
    }
    Stack<LinkList.Node> stack = new Stack<>();
    //将链表中的元素(节点)放入栈中
    Node cur = head;
    while(cur !=null){
        stack.push(cur);
        cur = cur.next;
    }
    //栈中的元素出栈
    while (!stack.empty()){
        System.out.print(stack.pop().val+" ");
    }
}

     3. 括号匹配

        代码实现

public boolean isValid(String s) {

        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()){

                    return false;

                }

                //从栈中取栈顶

                char ch1 = stack.pop();

                if((ch1 =='(' && ch == ')') || (ch1 == '[' && ch == ']') || (ch1 == '{' && ch == '}')){

                    continue;

                } else {

                    return false;

                }

            }

        }

        //栈中还有左括号

        if(!stack.empty()){

            return false;

        }

        return true;

    }

     4. 逆波兰表达式求值

    代码实现

public int evalRPN(String[] tokens) {

        Stack<Integer> stack = new Stack();

        for(String s:tokens){

            if(!(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/"))){

                stack.push(Integer.parseInt(s));

            }else{

                int num2 = stack.pop();

                int num1 = stack.pop();

                switch(s){

                    case "+":

                        stack.push(num1+num2);

                        break;

                    case "-":

                        stack.push(num1-num2);

                        break;

                    case "*":

                        stack.push(num1*num2);

                        break;

                    case "/":

                        stack.push(num1/num2);

                        break;

                }

            }

        }

        return stack.pop();

    }

     5. 出栈入栈次序匹配

        代码实现

public boolean IsPopOrder (int[] pushV, int[] popV) {

        Stack<Integer> stack = new Stack<>();

        //i遍历pushV,j遍历popV

        int i = 0, j = 0;

        for(;i < pushV.length; i++){

            //入栈

            stack.push(pushV[i]);

            //获取栈顶元素

            int pe = stack.peek();

            //判断栈顶元素是否需要出栈

            while(pe == popV[j]){

                stack.pop();

                j++;

                //栈空

                if(stack.empty()){

                    break;

                }

                //判断后面是否需要出栈

                pe = stack.peek();

            }

        }

        //栈中还有元素

        if(!stack.empty()){

            return false;

        }

        return true;

    }

     6. 最小栈

        代码实现

class MinStack {

    //普通栈

    private Stack<Integer> stack;

    //最小值栈-》存放当前普通栈中的最小值

    private Stack<Integer> minStack;

    public MinStack() {

        stack = new Stack<>();

        minStack = new Stack<>();

    }

    //入栈

    public void push(int val) {

        if(stack.empty()){

            stack.push(val);

            minStack.push(val);

        }else {

            stack.push(val);

            int peek = minStack.peek();

            //判断minStack是否要入栈

            if(val <= peek){

                minStack.push(val);

            }

        }

    }

    //出栈

    public void pop() {

        //普通栈为空

        if(stack.empty()){

            return;

        }

        int po= stack.pop();

        //判断minStack是否要出栈

        if(po == minStack.peek()){

            minStack.pop();

        }

    }

    //获取栈顶元素

    public int top() {

        //普通栈为空

        if(stack.empty()){

            return  -1;

        }

        return stack.peek();

    }

    //获取当前栈中最小值

    public int getMin() {

        //最小值栈-》 空

        if(minStack.empty()){

            return  -1;

        }

        return minStack.peek();

    }

}

    1.5 概念区分

        栈、虚拟机栈、栈帧有何区别?

        栈是一种数据结构,虚拟机栈是JVM划分的一块内存,栈帧是方法调用时,虚拟机给方法分配的一块内存。

二、队列

    2.1 概念

        队列只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的特点入队列:进行插入操作的一端称为队尾(Tail/Rear出队列:进行删除操作的一端称为队头

    2.2 队列的使用

        Queue是个接口,底层是通过链表实现。

        

        

方法 解释
boolean offer(E e) 入队列
E poll() 出队列并返回
E peek() 获取队头元素
int size() 获取队列中有效长度的个数
boolean isEmpty 判断队列是否为空

        Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口。

public static void main(String[] args) {
    Queue<Integer> queue = new LinkedList<>();
    //入队
    queue.offer(1);
    queue.offer(2);
    queue.offer(3);
    System.out.println(queue);//[1, 2, 3]
    //获取队头元素
    int t = queue.peek();
    System.out.println(t);//1
    //出队
    System.out.println(queue.poll());//1
    System.out.println(queue);//[2, 3]
    //判断队列是否为空
    boolean bool = queue.isEmpty();
    System.out.println(bool);//false
}

     2.3 队列的模拟实现

        队列中可以存储元素,那底层肯定要有能够保存元素的空间,通过前面线性表的学习了解到
常见的空间类型有两种:顺序结构 和 链式结构,那么 队列的实现使用顺序结构还是链式结构好?
/*双向链式队列*/
public class MyLinkqueue {
    static  class  ListNode{
        int val;
        ListNode next;
        ListNode pre;
        public ListNode(int val){
            this.val = val;
        }
    }
    ListNode first;//队头
    ListNode last;//队尾
    int usedsize;//队列中元素个数
    //入队列
    public boolean offer(int data){
        ListNode node = new ListNode(data);
        if(first == null){
            //空队列
            first = node;
            last = node;
        }else {
            last.next = node;
            node.pre = last;
            last = last.next;
        }
        usedsize++;
        return  true;
    }
    //获取队头元素
    public int peek(){
        if(usedsize == 0){
            return -1;
        }
        return first.val;
    }
    //出队列
    public int poll(){
        int x = peek();
        //只有一个元素
        if(first.next==null){
            first = null;
            last = null;
        }
        first = first.next;
        first.pre = null;
        usedsize--;
        return  x;
    }
    //获取队列中元素的个数
    public int size(){
        return usedsize;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return usedsize == 0;
    }
}

     2.4 循环队列

        实际中我们有时会使用一种队列叫循环队列,环形队列通常使用数组实现。
        
         设计循环队列

三、双端队列

        双端队列(deque)指允许两端都可以进行入队和出队操作的队列说明元素可以从队头入队和出队,也可以从队尾入队和出队。

        Deque是一个接口,使用时必须创建LinkedList的对象。

        

        实际工程中,使用Deque接口是比较多的,栈和队列均可以使用该接口。

Deque<Integer> stack = new ArrayDeque<>();// 双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

四、面试题

        1、用队列实现栈    链接

        代码实现

class MyStack {

    private Queue<Integer> queue1 ;

    private Queue<Integer> queue2 ;

    public MyStack() {

        queue1 = new LinkedList<>();

        queue2 = new LinkedList<>();

    }

    //入栈

    public void push(int x) {

        //栈为空

        if (empty()){

            queue1.offer(x);

        }else {

            //放入非空队列中

            if(!queue1.isEmpty()){

                queue1.offer(x);

            }else {

                queue2.offer(x);

            }

        }

    }

    //出栈

    public int pop() {

        //栈空

        if(empty()){

            return -1;

        }

        if(!queue1.isEmpty()){

            //将queue1中的size-1个元素放入queue2

            while (queue1.size()>1){

                int x= queue1.poll();

                queue2.offer(x);

            }

            //出队x并返回x

            int x = queue1.poll();

            return  x;

        }else {

            //将queue2中的size-1个元素放入queue1

            while (queue2.size()>1){

                int x= queue2.poll();

                queue1.offer(x);

            }

            //出队x并返回x

            int x = queue2.poll();

            return  x;

        }

    }

    //获取栈顶元素

    public int top() {

        //栈空

        if(empty()){

            return  -1;

        }

        if(!queue1.isEmpty()){

            //将queue1中的size-1个元素放入queue2

            while (queue1.size()>1){

                int x= queue1.poll();

                queue2.offer(x);

            }

            //出队x放入另一队列并返回x

            int x = queue1.poll();

            queue2.offer(x);

            return  x;

        }else {

            //将queue2中的size-1个元素放入queue1

            while (queue2.size()>1){

                int x= queue2.poll();

                queue1.offer(x);

            }

            //出队x放入另一队列并返回x

            int x = queue2.poll();

            queue1.offer(x);

            return  x;

        }

    }

    //判断栈是否为空

    public boolean empty() {

        //两个队都为空-》栈为空

        return queue1.isEmpty() && queue2.isEmpty();

    }

}

         2、 用栈实现队列    链接

        代码实现

class MyQueue {

    private Stack<Integer> stack1;//入队

    private Stack<Integer> stack2;//出队

    public MyQueue() {

        stack1 = new Stack<>();

        sstack2 = new Stack<>();

    }

    //入队

    public void push(int x) {

        stack1.push(x);

    }

    //出队

    public int pop() {

        //队空

        if(empty()){

            return -1;

        }

        //保证stack2不为空

        if(stack2.isEmpty()){

            while (!stack1.isEmpty()){

                stack2.push(stack1.pop());

            }

        }

        return stack2.pop();

    }

    //获取队头元素

    public int peek() {

        //队空

        if(empty()){

            return -1;

        }

        //保证stack2不为空

        if(stack2.isEmpty()){

            while (!stack1.isEmpty()){

                stack2.push(stack1.pop());

            }

        }

        return stack2.peek();

    }

    //判断队列是否为空

    public boolean empty() {

        //两个栈都为空-》队列为空

        return stack1.isEmpty() && stack2.isEmpty();

    }

}