[java数据结构] 栈(Stack)和队列(Queue)

目录

(一)?栈(Stack)

1.?栈的概念

2.?栈的常见的方法

3.?栈的使用

4. 栈的模拟实现

(二) 队列(Queue)

1. 队列的概念

2. 队列常见的方法

3. 队列的使用

5. 队列的模拟实现

6.?循环队列

总结

---

(一)?栈(Stack)

1.?栈的概念

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

进栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

假设S = ( a 1 , a 2 , . . . . a n ) S=(a1, a2,....an)S=(a1,a2,....an)，则称a 1 a1a1为栈底元素，a n anan为栈顶元素。栈中元素按a 1 , a 2 , . . . a n a1,a2,...ana1,a2,...an的次序进栈，那么出栈的第一个元素应为栈顶元素。

如图:

栈在现实生活中的例子：

也是遵循后进先出,先进看不出原则

2.?栈的常见的方法

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

3.?栈的使用

import java.util.Stack;

class Main {
    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); //插入5个元素, 1 2 3 4 5 栈顶是5, 栈底是1
        System.out.println(stack.size()); // 获取栈中有效元素个数---> 5
        System.out.println(stack.peek()); // 获取栈顶元素---> 5
        System.out.println(stack.pop()); // 5出栈，栈中剩余1  2  3  4，栈顶元素为4
        System.out.println(stack.pop()); // 4出栈，栈中剩余1  2  3 栈顶元素为3
       
        //为空则返回true 否则false
        if(stack.empty()){   
            System.out.println("栈空");
        }else{
            System.out.println(stack.size()); //出了两个元素还有1 2 3----->3个
        }
    }
}

4. 栈的模拟实现

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。

package Stack;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Stack;

public class myStack {
    public int[] arr; // 用于存储栈元素的数组
    public int usedSize; // 记录栈中已使用的元素个数
    public static final int MAX = 10; // 栈的最大容量

    // 构造函数，初始化数组
    public myStack(){
        arr = new int[MAX];
    }

    // 获取栈中已使用的元素个数
    public int size(){
       return usedSize;
    }

    // 判断栈是否已满，若满则扩容
    private void isFull(){
        if (usedSize == MAX) {
            arr = Arrays.copyOf(arr, arr.length * 2); // 扩容为原来的两倍
        }
    }

    // 打印栈中元素
    public void display(){
        for (int i = 0; i < usedSize; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }

    // 入栈操作
    public void push(int data){
        // 判断是否栈满，若满则扩容
        isFull();
        arr[usedSize++] = data; // 将元素入栈
    }

    // 判断栈是否为空
    private boolean isEmpty(){
        if (usedSize == 0){
            return true;
        }
        return false;
    }

    // 出栈操作，获取并删除栈顶元素
    public int pop(){
        // 判断是否栈空 如果空了就没必要出栈了
        if (isEmpty()){
            throw new EmptyStackException("栈为空了！");
        }
        int ret = arr[usedSize-1]; // 获取栈顶元素
        usedSize--; // 栈中元素个数减一
        return ret; // 返回被删除的栈顶元素
    }

    // 获取栈顶元素 如果空了就不用返回栈顶元素了
    public int peek(){
        if (isEmpty()){
            throw new RuntimeException("栈为空了");
        }
        return arr[usedSize-1]; // 返回栈顶元素
    }


    // 获取栈中已使用的元素个数
    public int getUsedSize() {
        return usedSize;
    }
}

(二) 队列(Queue)

1. 队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

生活中体现出队列也挺常见的, 比如排队, 先来的先排在前面, 后来的排在后面?

2. 队列常见的方法

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

3. 队列的使用

在Java中，Queue是个接口，底层是通过链表实现的。

import java.util.LinkedList;
import java.util.Queue;
class Main {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);  // 从队尾入队列 队头是1 队尾是4

        // 获取队列有效元素个数 -> 4
        System.out.println(q.size());

        // 获取队头元素 -> 1
        System.out.println(q.peek());

        // 从队头出队列，并将删除的元素返回 -> 1
        System.out.println(q.poll());
            
        //为空则返回true 否则false
        if (q.isEmpty()) {
            System.out.println("队列空");
        } else {
            System.out.println(q.size()); //前面执行了一次删除操作, 还剩下3个元素        
        }
    }

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

5. 队列的模拟实现

package Queue;

public class myQueue {

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

        public ListNode(int val){
            this.val = val;
        }
    }
    public int usedSize; // 已使用的队列元素个数
    public ListNode head; // 队列头部节点
    public ListNode tail; // 队列尾部节点

    // 入队操作
    public void offer(int data){
        ListNode node  = new ListNode(data); // 创建新节点
        if (head == null){ // 如果队列为空
            tail = node;
            head = node;
        }else {
            tail.next = node; // 将新节点连接到队列尾部
            tail = tail.next; // 更新尾部节点
        }
    }

    // 出队操作
    public int poll(){
        if (head == null){ // 如果队列为空
            return -1; // 返回-1表示出队失败
        }
        ListNode cur = head; // 记录当前头部节点
        head = head.next; // 头部指针后移
        return cur.val; // 返回出队的元素值
    }

    // 获取队首元素
    public int peek(){
        if (head == null){ // 如果队列为空
            return  -1; // 返回-1表示队列为空
        }
        return head.val; // 返回队首元素的值
    }

    // 打印队列中元素
    public void display(){
        ListNode cur = head;
        while (cur != null){ // 遍历队列
            System.out.print(cur.val+" "); // 打印节点值
            cur = cur.next; // 指针后移
        }
        System.out.println();
    }

    // 获取队列中元素个数
    public int size(){
        ListNode cur = head;
        int len = 0;
        while (cur != null){ // 遍历队列
            cur = cur.next; // 指针后移
            len++; // 元素个数加一
        }
        return len; // 返回队列中元素个数
    }
}

当我们使用队列这种基本的数据结构时，很容易发现，随着入队和出队操作的不断进行，队列的数据区域不断地偏向队尾方向移动。当我们的队尾指针指向了队列之外的区域时，我们就不能再进行入队操作了，而此时由于队头已经偏离原来位置，也就意味着实际上队列并没有满。这种实际上还有空间，但是却发生了溢出的现象就称为假溢出现象

6.?循环队列

什么是假溢出现象

假设有以下队列，初始元素为1、2、3、4、队头元素是1，队尾元素就4

当我们弹出队头元素两次得到队列：

这就是假溢出, 可以看出还有多余的空间, 但是当队尾入一个元素发现满了

如何解决这个问题?

为了避免假溢出问题，我们需要对队列进行优化---循环队列,? 形如如图

循环队列的性质

数组实现

• 空队列：front == rear
• 满队列：牺牲一个单元判满（不牺牲的话队空队满无法区分）

?????（rear+1）% len?== front

• 进队：rear?= （rear+1）% maxSize
• 出队：front?= （front+1）% maxSize
• 队中元素个数/长度：(rear - front + len) % len

循环队列题

622. 设计循环队列?编辑https://leetcode.cn/problems/design-circular-queue/

循环队列代码实现:

package Queue;

import java.util.Arrays;

public class CircleQueue {

    public int[] arr; // 数组存储队列元素
    public int usedSize; // 已使用的队列元素个数
    public int font; // 队列头部指针
    public int rear; // 队列尾部指针
    public static final int MAX = 5; // 队列最大容量

    public CircleQueue(){
        arr = new int[MAX]; // 初始化数组
    }

    // 打印队列中元素
    public void display(){
        for (int i = font; i < arr.length-1; i++) {
            System.out.print(arr[i]+" "); // 打印队列元素
        }
        System.out.println();
    }

    // 判断队列是否已满
    private boolean isFull(){
        if ((rear + 1) % MAX == font){ // 判断队列是否已满
          return true;
        }
        return false;
    }

    // 入队操作
    public boolean offer(int data){
      if(isFull()){ // 如果队列已满
          return false; // 返回入队失败
      }
      arr[rear] = data; // 将元素放入队列尾部
      rear = (rear + 1) % arr.length; // 更新队列尾部指针
      usedSize++; // 更新队列元素个数
      return true; // 返回入队成功
    }

    // 判断队列是否为空
    private boolean isEmpty(){
        if (font == rear){ // 判断队列是否为空
            return true;
        }
        return false;
    }

    // 出队操作
    public boolean poll(){
        if (isEmpty()){ // 如果队列为空
            return false; // 返回出队失败
        }
        font = (font+1) % arr.length; // 头部指针后移
        usedSize--; // 更新队列元素个数
        return true; // 返回出队成功
    }

    // 获取队头元素
    public int Front(){
        if(isEmpty()){ // 如果队列为空
            return -1; // 返回-1表示队列为空
        }
        int ret = arr[font]; // 获取队头元素
        return ret; // 返回队头元素的值
    }

    // 获取队尾元素
    public int Rear(){
        if (isEmpty()){ // 如果队列为空
            return -1; // 返回-1表示队列为空
        }
        int ret = (rear == 0) ? arr.length-1 : rear - 1; // 计算队尾元素的下标
        return arr[ret]; // 返回队尾元素的值
    }
    
    // 获取队列元素个数
    public int size() {
    return usedSize; // 返回队列元素个数
    }

}

总结

栈（Stack）和队列（Queue）是两种常见的数据结构，它们在数据存储和访问的方式上有一些重要的区别。

栈（Stack）是一种后进先出（LIFO，Last In First Out）的数据结构，类似于一摞盘子，最后放入的盘子最先取出。栈的操作包括入栈（push）和出栈（pop），只能在栈顶进行操作，不支持随机访问。栈常用于实现函数调用、表达式求值、括号匹配等场景。

队列（Queue）是一种先进先出（FIFO，First In First Out）的数据结构，类似于排队等候的过程，先到先得。队列的操作包括入队（offer）和出队（poll），元素从队列的前端出队，从队列的后端入队。队列常用于实现广度优先搜索、任务调度等场景。