栈和队列详解

发布时间:2024年01月22日

栈和队列详解

目录

  • 栈的概念
  • 队列的概念
  • 栈和队列oj题目详解
  • 循环队列的概念及设计

1、栈的概念

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

基本操作:

  • Stack() 构造一个空的栈
  • E push(E e) 将e入栈,并返回e
  • E pop() 将栈顶元素出栈并返回
  • E peek() 获取栈顶元素
  • int size() 获取栈中有效元素个数
  • boolean empty() 检测栈是否为空

事实上,我们可以自己使用数组模拟实现一个栈,栈的特点是先进后出,我们在入栈时就应该将元素插入到数组的最后,在元素出栈时删除数组相应的最后一个元素(所谓删除只是让下一次入栈的元素覆盖这个需要被删除的元素,并不是让它凭空消失)。当然其中有一些需要注意的地方,比如栈为空时不能出栈元素,栈满时需要扩容,接下来我们结合代码一起分析一下:

public class MyStack {

    public int[] elem;
    public int usedSize;

    public static final int DEFAULT_CAPACITY = 10;//默认数组容量
    public MyStack() {
        this.elem = new int[DEFAULT_CAPACITY];//重载构造方法初始化数组
    }

    //压栈 入栈
    public void push(int val) {
        if(isFull()) {
            this.elem = Arrays.copyOf(elem,2*elem.length);//数组满时2倍扩容
        }
        elem[usedSize++] = val;
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

    //出栈
    public int pop() {
        if(isEmpty()) {
            throw new EmptyStackException("栈为空....");//栈为空时出栈抛出异常
        }
        int oldVal = elem[usedSize-1];
        usedSize--;
        //elem[usedSize] = null;
        return oldVal;
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }

    public int peek() {
        if(isEmpty()) {
            throw new EmptyStackException("栈为空....");//栈为空时获取栈顶元素抛出异常
        }
        return elem[usedSize-1];
    }
}

2、队列的概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头(Head/Front)。
基础操作:

  • boolean offer(E e) 入队列
  • E poll() 出队列
  • peek() 获取队头元素
  • int size() 获取队列中有效元素个数
  • boolean isEmpty() 检测队列是否为空

与stack类实现相比较,要实现队列Queue这个类,我们还能使用数组(顺序表)吗?由于队列的特点是先进先出,如果使用顺序结构,那么在出队列时就会显得十分麻烦,因为被删除的元素后面的元素都要相应的向前移动。那么,我们是否有更好的选择呢?有,就是链表。我们在模拟实现时,使用单向链表即可,通过尾插和头删法,我们即可模拟出队列的基本操作。

public class MyQueue {
    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;

    //入队
    public void offer(int val) {
        ListNode node = new ListNode(val);
        if(head == null) {//只有一个元素
            head = last = node;
        }else {
            last.next = node;//尾插法
            node.prev = last;
            last = node;
        }
    }
    //出队
    public int poll() {
        if(head == null) {//队列为空
          return -1;
        }
        int val = -1;
        if(head.next == null) {//队列中只有一个元素
            val = head.val;
            head = null;
            last = null;
            return val;
        }
        val = head.val;//头删法
        head = head.next;
        head.prev = null;
        return val;
    }
    public boolean empty() {
        return head == null;
    }
    public int peek() {
        if(head == null) {//队列为空
            return -1;
        }
        return head.val;
    }

}

在Java中,Queue是个接口,底层是通过链表实现的,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口。

     Queue<> queue = new LinkedList<>(); 

3、栈和队列oj题目详解

1、栈的最经典问题之一——逆波兰表达式(后缀表达式)的值

leetcode链接
给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。例如下图:
在这里插入图片描述
逆波兰表达式由于将操作符放在数字的后面,当我们遇到操作符时,就应该从前去找数字,这时栈的优势就有所体现,将遍历过的数字放入栈中,遇到操作符时就可以弹出栈顶的两个元素,分别作为右操作数和左操作数(顺序不可颠倒,因为先放的是左操作数,在栈的下层),计算后再将结果放入栈中,重复这个过程,最后栈中留下的就是答案。以上图为例,2入栈,1入栈,遇到‘+’,取出2,取出1,1+2=3,3入栈,3入栈,遇到‘’,取出3,取出3,33=9,9入栈,数组遍历结束,栈中留下来的9就是答案。注意:这里是字符串数组,否则字符‘1’‘2’,无法确定表示的是1和2还是12。
下面给出代码:

public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = tokens.length;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));//将字符串转化为整型
            } else {
                int num2 = stack.pop();//右操作数出栈
                int num1 = stack.pop();//左操作数出栈
                switch (token) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:
                }
            }
        }
        return stack.pop();
    }

    public boolean isNumber(String token) {//判断是否是数字
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));//字符串判断相等调用equals方法
    }

2、最小栈

leetcode链接
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

一个普通的栈无法实现最小栈,因为我们每次只能获取栈顶的元素,但又没有办法保证栈顶的元素是最小的。所以我们需要两个栈,一个当作普通的栈用存放题目数据,称为栈1,另一个栈来记录前一个栈的数据最小值,称为栈2,保证栈1的最小数据永远在栈2的顶部。我们主要研究在什么条件下可以让数据入栈2和出栈2。
入栈:栈1为空(此时栈2也必为空)时,数据同时入栈1,栈2;栈1不为空时(栈2也比不为空),获取栈2顶的数据,如果该数据小于等于栈2顶的数据,则同时入栈1,栈2;否则数据只入栈1。
出栈:栈1、栈2不为空时,如果栈1出的元素和栈2顶1的元素相同,则同时出栈1、栈2;否则只出栈1。
构建好了栈2,调用getMin方法只要获取栈2顶的元素即可。下面是代码呈现:

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()) {
            int top = minStack.peek();
            if (x <= top) {
                minStack.push(x);
            }
        }else{
            minStack.push(x);
        }
    }

    public void pop() {
        int pop = stack.pop();
        int top = minStack.peek();
        if (pop == top) {
            minStack.pop();
        }
    }

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

    public int getMin() {
        return minStack.peek();
    }
}

3、用队列模拟栈

leetcode链接
队列和栈最大的不同就是:队列是先进先出,栈是先进后出。这就意味着使用队列模拟栈,如果要获取(删除)栈顶的元素,就必须得到队列的最后一个元素,还不能丢掉之前的元素。因此,使用一个普通的队列是无法完成这个任务的,但是使用两个队列就可以做到。这两个队列没有实质性的差别。
入栈:入那一个不为空的队列即可。(保证另外一个是空队列,可以用来进行下一步操作)。
出栈:找到那个不为空的队列,获取它的大小size,将size-1个元素出队列,同时入到另外一个队列,这样原来的队列就只剩下最后入队的那个元素(相当于最后入栈的那个元素)
获取栈顶元素:与出栈的操作十分类似,只是要将size个元素全部出队列,再入到另外一个队列。同时在这个过程中,要记录下出队的元素,这样所有元素都操作完成后,记录下的就是最后入队的元素(相当于栈顶的元素),返回即可。
下面直接上代码:

	Queue<Integer> queue1;
    Queue<Integer> queue2;
class MyStack {
    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }
    
    public void push(int x) {
        if(!queue1.isEmpty()) {
            queue1.offer(x);
        }else {
            queue2.offer(x);
        }
    }
    
    public int pop() {
        if(!queue1.isEmpty()) {
            int size = queue1.size();
            for(int i =0; i<size-1;i++) {
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        }else {
             int size = queue2.size();
            for(int i =0; i<size-1;i++) {
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        }
    }
    
    
    public int top() {
        if(!queue1.isEmpty()) {
            int size = queue1.size();
            int temp = -1;
            for(int i =0; i<size;i++) {
                temp = queue1.poll();//记录出队元素
                queue2.offer(temp);
            }
            return temp;
        }else {
            int size = queue2.size();
            int temp = -1;
            for(int i =0; i<size;i++) {
                temp = queue2.poll();
                queue1.offer(temp);
            }
            return temp;
        }
    }
    
    public boolean empty() {
        return queue1.isEmpty()&&queue2.isEmpty();//队1,队2都为空才是空
    }
}

4、用栈实现队列

leetcode链接
用栈模拟队列的过程与用队列模拟栈的过程有点不同,但是根据上述的过程,我们知道我们应该也要使用两个栈来实现队列。但是这两个栈是有区别的,第一个栈用来入队列,第二个栈用来做出队列操作。
出队列或获取队列头元素,栈2为空时,就将栈1的元素都倒入栈2(出栈再入栈),返回(获取)栈2顶的元素即可;栈2不为空时,直接出栈(获取)即可。
不多赘述,直接上代码:

import java.util.Stack;
class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
    public MyQueue() {
        s1 = new Stack<Integer>();
        s2 = new Stack<Integer>();
    }
    
    public void push(int x) {
       s1.push(x); 
    }
    
    public int pop() {
        if(s2.isEmpty()) {
            while(!s1.isEmpty()) {
            s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    
    public int peek() {
       if(s2.isEmpty()) {
            while(!s1.isEmpty()) {
            s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    
    public boolean empty() {
        return s1.isEmpty()&&s2.isEmpty();
    }
}

4、循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。下图就是一个循环队列(环形队列):
在这里插入图片描述
对于循环队列来说,有头(front)和尾(rear)两个标记。遇到的问题是:

1、front和rear存放元素之后,怎么向后走?
由于它是一个循环数组,(不考虑扩容的情况下)容量是有限的,因此我们不能直接让front与rear++,因为可能直接越界。我们可以使用一个公式:index = (index+1) % length

2、front和rear删除元素之后,怎么向前走?
同样我们有公式: index = (index + length - 1) % length

3、怎么判断循环队列是空的还是满的?

  • 定义usedSize记录使用空间的大小
  • 保留一个位置
  • 使用标记(boolean flag)

循环队列的实现

leetcode链接
你的实现应该支持如下操作:

  • MyCircularQueue(k): 构造器,设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空,返回 -1 。
  • Rear: 获取队尾元素。如果队列为空,返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

我们在这里采用保留一个位置的方式判断是满还是空。如果队列是空,那么rear与front相等;如果队列是满的,那么(rear+1)%length与front相等。下面直接呈现代码,结合注释分析:

class MyCircularQueue {
    int[] elem;
    public int front;
    public int rear;
    public MyCircularQueue(int k) {
        elem = new int[k+1];//保留一个位置,所以初始化数组时要多给一位
    }
    
    public boolean enQueue(int value) {
        if(isFull()) {
            return false;
        }
        elem[rear] = value;
        rear = (rear+1)%elem.length;//rear向后走
        return true;
    }
    
    public boolean deQueue() {
        if(isEmpty()) {
            return false;
        }
        front = (front+1)%elem.length;
        return true;
    }
    
    public int Front() {
        if(isEmpty()) {
            return -1;
        }
        return elem[front];
    }
    
    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        int index = (rear==0)?elem.length-1:rear-1;
        //判断rear是不是头元素,决定回退一个元素的下标
        return elem[index];
    }
    
    public boolean isEmpty() {
        return rear == front;
    }
    
    public boolean isFull() {
        return (rear+1)%elem.length==front;
    }
}

总结

栈和队列都是十分有用的数据结构,可以帮助我们模拟许多场景,也是学习后序数据结构的基础。熟练掌握使用栈和队列是十分有必要的!

文章来源:https://blog.csdn.net/ling_zu_qi/article/details/135739555
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。