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

发布时间:2024年01月23日

目录

(一)?栈(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),元素从队列的前端出队,从队列的后端入队。队列常用于实现广度优先搜索、任务调度等场景。

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