专栏首页Mybatis学习数据结构——队列

数据结构——队列

数据结构——队列

队列的概念:队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

1、基本属性:

  • 队头front:删除数据的一端。对于数组,从后面插入更容易,前面插入较困难,所以一般用数组实现的队列队头在前面。(删除直接index游标前进,不超过队尾即可)。而对于链表。插入删除在两头分别进行那么头部(前面)删除尾部插入是最方便的选择。
  • 队尾rear:插入数据的一端,同上,在数组和链表中通常均在尾部位置。当然,其实数组和链表的front和rear还有点小区别,后面会具体介绍。
  • enQueue(入队):在队尾rear插入元素
  • deQueue(出队):在对头front删除元素

2、普通队列:

  • 初始化:数组的front和rear都指向0
  • 入队:队不满,数组不越界,先队尾位置传值,再队尾下标+1
  • 出队:队不空,先取队头位置元素,在队头+1
package 队栈;

public class seqQueue<T> {
	private T data[];// 数组容器
	private int front;// 头
	private int rear;// 尾
	private int maxsize;// 最大长度

	public seqQueue(int i)// 设置长为i的int 型队列
	{
		data = (T[]) new Object[i+1];
		front = 0;
		rear = 0;
		maxsize = i+1;
	}

	public int  lenth() {
		return (rear+maxsize-front)%maxsize;
	}
	public boolean isempty() {
		return rear == front;
	}

	public boolean isfull() {
		return (rear + 1) % maxsize == front;
	}

	public void enQueue(T i) throws Exception// 入队
	{
		if (isfull())
			throw new Exception("已满");
		else {
			data[rear] = i;
			rear=(rear + 1) % maxsize;
		}
	}

	public T deQueue() throws Exception// 出队
	{
		if (isempty())
			throw new Exception("已空");
		else {
			T va=data[front];
			front=(front+1)%maxsize;
			return va;
		}
	}

	public String toString()// 输出队
	{
		String va="队头: ";
		int lenth=lenth();
		for(int i=0;i<lenth;i++)
		{
			va+=data[(front+i)%maxsize]+" ";
		}
		return va;
	}

}

3、链表实现

对于链表实现的队列,要根据先进先出的规则考虑头和尾的位置

我们知道队列是先进先出的,对于链表,我们能采用单链表尽量采用单链表,能方便尽量方便,同时还要兼顾效率。

方案一 如果队头设在链表尾,队尾设在链表头。那么队尾进队插入在链表头部插入没问题。容易实现,但是如果队头删除在尾部进行,如果不设置尾指针要遍历到队尾,但是设置尾指针删除需要将它指向前驱节点那么就需要双向链表。都挺麻烦的。

方案二但是如果队头设在链表头,队尾设在链表尾部,那么队尾进队插入在链表尾部插入没问题(用尾指针可以直接指向next)。容易实现,如果队头删除在头部进行也很容易,就是我们前面常说的头节点删除节点。

所以我们最终采取的是方案2的带头节点,带尾指针的单链表!

主要操作为:

package 队栈;

public class listQueue<T> {
	static class node<T> {
		T data;// 节点的结果
		node next;// 下一个连接的节点
		public node() {}
		public node(T data) {
			this.data = data;
		}
	}
	node front;//相当于head 带头节点的
	node rear;//相当于tail/end
	public listQueue() {
		front=new node<T>();
		rear=front;
	}
	public int  lenth() {
		int len=0;
		node team=front;
		while(team!=rear)
		{
			len++;team=team.next;
		}
		return len;
	}
	public boolean isempty() {
		return rear == front;
	}
	public void enQueue(T value) // 入队.尾部插入
	{
		node va=new node<T>(value);
		rear.next=va;
		rear=va;
	}

	public T deQueue() throws Exception// 出队
	{
		if (isempty())
			throw new Exception("已空");
		else {
			T va=(T) front.next.data;
			front.next=front.next.next;
			return va;
		}
	}
	public String toString()
	{
		node team=front.next;
		String va="队头: ";
		while(team!=null)
		{
			va+=team.data+" ";
			team=team.next;
		}
		return va;
	}
}

我一般采用java中的封装好的函数来进行:

import java.util.LinkedList;
import java.util.Queue;

public class Queue_test {
    public static void main(String[] args) {
        //创建一个队列
        Queue<Integer> queue = new LinkedList<>();
        //在队列中添加元素
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(5);
        queue.add(6);
        System.out.println(queue);
        //获取即将出队的元素
        int temp1 = queue.peek();
        System.out.println(temp1); //这里的结果是1  因为1是最先进入队列的,所以,先进先出

        //删除即将出队的元素
        int temp2 = queue.poll();
        System.out.println(temp2); //这里的结果是1  因为1是最先进入队列的,所以,先进先出,删除了1

        System.out.println(queue); //队列为 6 5 4 3 2

        //判断队列是否为空
        System.out.println(queue.isEmpty()); // false

        //输出队列的长度
        System.out.println(queue.size()); // 5

        //遍历输出队列
        /*
        我们在遍历的过程中,最好是使用边删除,边遍历的方法啊,因为删除之后,下一个元素是即将出队的元素,就好遍历出来了
        * */
        while(!queue.isEmpty()){//当队列不为空,就遍历,为空就终止
            int temp = queue.poll();
            System.out.println(temp);
        }                    //出来的顺序为 2 3 4 5 6
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构----队列

    SuperHeroes
  • 数据结构——队列

    我们在使用手机的时候,偶尔都会碰到过卡住的时候,比如一个地方怎么点都没有用,屏幕也卡住不显示其他东西,但当你把卡住的App关闭掉之后,手机的操作显示就又恢复正常...

    Originalee
  • [快学Python3]数据结构-队列

    概述 什么是队列,简单而言:先进先出。 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,...

    苦叶子
  • 数据结构-队列

    队列(queue)在计算机科学中,是一种先进先出的线性表。 它只允许在表的前端进行删除操作,而在表的后端进行插入操作。进行插入操作的端称为队尾,进行删除操作的端...

    杨小杰
  • 数据结构-队列

    队列的定义 在很多资料中,队列与栈往往一同出现,因为它与栈有很多相似的地方。队列是只允许在一端插入另一端删除的线性表,即一种先入先出(FIFO)的结构,队列有顺...

    chaibubble
  • 数据结构-队列

    Wilbur-L
  • 数据结构【队列】

      1、链式队列:内部属于链表,对链表的操作做一些限制,就是链式队列   2、静态队列:内部属于数组     静态队列通常都必须是循环队列

    Sky_Mao
  • 数据结构-队列

    队列(queue)在计算机科学中,是一种先进先出的线性表。 它只允许在表的前端进行删除操作,而在表的后端进行插入操作。进行插入操作的端称为队尾,进行删除操作的端...

    乱敲代码
  • [javaSE] 数据结构(队列)

    陶士涵
  • 3.4 数据结构队列

    1、和栈相反,队列是一种先进先出(FIFO)的线性表。它只允许在表的一端进行插入,而在另一端删除元素。

    小林C语言
  • 数据结构|队列的实现[6]

    队列的特性是先进先出。每次数据出去只能的队列的头部,每次数据进来只能加在队列的尾部。 队列实现一般有两种方式,线性队列,链表队列。

    rare0502
  • 前端中的数据结构——队列篇

    队列是数据结构中的一种,它与实际生活中的排队相似:在一条队伍中,先来的人总是能够先得到服务,后来的人只能排在队伍末尾等候。队列也是一样,它符合先进先出 FIFO...

    企鹅号小编
  • python算法与数据结构-队列(44)

      队列的定义:队列是一种特殊的线性表,只允许在表的头部(front处)进行删除操作,在表的尾部(rear处)进行插入操作的线性数据结构,这种结构就叫做队列。进...

    Se7eN_HOU
  • 数据结构--队列Queue--循环顺序队列

    针对顺序队列中的入队操作:if 队列没满,但是队尾到达数组末尾了,队列"满"了,其实没有满,数据需要整体移至数组头部,才可以继续入队。 为解决该问题,避免数据...

    Michael阿明
  • 数据结构:队列的链式存储结构

    队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列。为了操作上的方便,我们将队头指针指向链队列的头节点,而队尾指针指向终...

    s1mba
  • 数据结构--队列Queue--链式队列、顺序队列

    Michael阿明
  • 《数据结构》 队列(Queue)操作代码集合

    队列基本操作代码集合,来自《数据结构-用C语言描述》(第二版) 高教社 队列是受限制的链表或顺序表(只能从队首取结点,先进先出FIFO),相关操作可以...

    Steve Wang
  • 数据结构--队列Queue--打印杨辉三角

    杨辉三角大家很熟悉,不做介绍了,第n行的首末两元素均为1,中间n-2个元素由n-1行相邻两元素相加得到。

    Michael阿明
  • PHP数据结构-队列的相关逻辑操

    在逻辑结构中,我们已经学习了一个非常经典的结构类型:栈。今天,我们就来学习另外一个也是非常经典的逻辑结构类型:队列。相信不少同学已经使用过 redis 、 ra...

    硬核项目经理

扫码关注云+社区

领取腾讯云代金券