队列_队列表 - CSDN
队列 订阅
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。 展开全文
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
信息
中文名
队列
队列简介
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。 [1]  建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间,并设置两个指针进行管理。一个是队头指针front,它指向队头元素;另一个是队尾指针rear,它指向下一个入队元素的存储位置,如图所示 每次在队尾插入一个元素是,rear增1;每次在队头删除一个元素时,front增1。随着插入和删除操作的进行,队列元素的个数不断变化,队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时,队列中没有任何元素,称为空队列。当rear增加到指向分配的连续空间之外时,队列无法再插入新元素,但这时往往还有大量可用空间未被占用,这些空间是已经出队的队列元素曾经占用过得存储单元。顺序队列中的溢出现象:(1) "下溢"现象:当队列为空时,做出队运算产生的溢出现象。“下溢”是正常现象,常用作程序控制转移的条件。(2)"真上溢"现象:当队列满时,做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态,应设法避免。(3)"假上溢"现象:由于入队和出队操作中,头尾指针只增加不减小,致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时,也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。在实际使用队列时,为了使队列空间能重复使用,往往对队列的使用方法稍加改进:无论插入或删除,一旦rear指针增1或front指针增1 时超出了所分配的队列空间,就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0,可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间,环形空间中的存储单元循环使用,用这种方法管理的队列也就称为循环队列。除了一些简单应用之外,真正实用的队列是循环队列。 [2]  在循环队列中,当队列为空时,有front=rear,而当所有队列空间全占满时,也有front=rear。为了区别这两种情况,规定循环队列最多只能有MaxSize-1个队列元素,当循环队列中只剩下一个空存储单元时,队列就已经满了。因此,队列判空的条件时front=rear,而队列判满的条件时front=(rear+1)%MaxSize。队空和队满的情况如图:
收起全文
  • 队列

    2019-05-15 11:04:56
    一、什么是队列队列是一种特殊的线性表,单向队列只能在一端插入数据(后),另一端删除数据(前);它和栈一样,队列是一种操作受限制的线性表;进行插入操作的称为队尾,进行删除操作的称为队头;队列中的数据...

    一、什么是队列?

    队列是一种特殊的线性表,单向队列只能在一端插入数据(后),另一端删除数据(前);它和栈一样,队列是一种操作受限制的线性表;进行插入操作的称为队尾,进行删除操作的称为队头;队列中的数据被称为元素;没有元素的队列称为空队列。

    由于只能一端删除或者插入,所以只有最先进入队列的才能被删除,因此又被称为先进先出(FIFO—first in first out)线性表。

    队列分为两种:双向队列和单向队列 

    单向队列:只能在一端删除数据,另一端插入数据。

    双向队列:两端都可以进行插入数据和删除数据操作。

    二、java单向队列模拟实现

    package com.lzw.demo;
    
    /**
     * @author lzw
     * @Date 2019年5月15日
     */
    public class MyQueue {
    
    	  	private Object[] queArray;
    	    //队列总大小
    	    private int maxSize;
    	    //前端
    	    private int front;
    	    //后端
    	    private int rear;
    	    //队列中元素的实际数目
    	    private int nItems;
    	     
    	    public MyQueue(int s){
    	        maxSize = s;
    	        queArray = new Object[maxSize];
    	        front = 0;
    	        rear = -1;
    	        nItems = 0;
    	    }
    	     
    	    //队列中新增数据
    	    public void insert(int value){
    	        if(isFull()){
    	            System.out.println("队列已满!!!");
    	        }else{
    	            //如果队列尾部指向顶了,那么循环回来,执行队列的第一个元素
    	            if(rear == maxSize -1){
    	                rear = -1;
    	            }
    	            //队尾指针加1,然后在队尾指针处插入新的数据
    	            queArray[++rear] = value;
    	            nItems++;
    	        }
    	    }
    	     
    	    //移除数据
    	    public Object remove(){
    	        Object removeValue = null ;
    	        if(!isEmpty()){
    	            removeValue = queArray[front];
    	            queArray[front] = null;
    	            front++;
    	            if(front == maxSize){
    	                front = 0;
    	            }
    	            nItems--;
    	            return removeValue;
    	        }
    	        return removeValue;
    	    }
    	     
    	    //查看对尾数据
    	    public Object peekRear(){
    	        return queArray[rear];
    	    }
    	    
    	    //查看对头数据
    	    public Object peekFront(){
    	        return queArray[front];
    	    }
    	     
    	     
    	    //判断队列是否满了
    	    public boolean isFull(){
    	        return (nItems == maxSize);
    	    }
    	     
    	    //判断队列是否为空
    	    public boolean isEmpty(){
    	        return (nItems ==0);
    	    }
    	     
    	    //返回队列的大小
    	    public int getSize(){
    	        return nItems;
    	    }
    
    	
    	public static void main(String[] args) {
    		 	MyQueue queue = new MyQueue(3);
    	        queue.insert(1);
    	        System.out.println("队列大小:"+queue.getSize());
    	        queue.insert(2);
    	        System.out.println("队列大小:"+queue.getSize());
    	        queue.insert(3);//queArray数组数据为[1,2,3]
    	        System.out.println("队列大小:"+queue.getSize());
    	        System.out.println("队头:"+queue.peekFront()); //1
    	        System.out.println("队尾:"+queue.peekRear());
    	        queue.remove();//queArray数组数据为[null,2,3]
    	        System.out.println(queue.peekFront()); //2
    	        System.out.println("队列大小:"+queue.getSize());
    	        queue.insert(4);//queArray数组数据为[4,2,3]
    	        queue.insert(5);//队列已满,queArray数组数据为[4,2,3]
    	        System.out.println("队列大小:"+queue.getSize());
    	        System.out.println("队头:"+queue.peekFront());
    	        System.out.println("队尾:"+queue.peekRear());
    
    	}
    
    }
    

    三、双向队列 

    双向队列就是队列的两端都可以进行删除和插入的操作。

    package com.lzw.demo;
    
    import java.util.LinkedList;
    
    /**
     * @author lzw
     * @param <T>
     * @Date 2019年5月15日
     */
    public class Deque<T> {
    
    	private LinkedList<T> deque = new LinkedList<T>();
    
    	/**从队头插入元素*/
    	public void addFirst(T e) {
    		deque.addFirst(e);
    	}
    	/**从队尾插入元素*/
    	public void addLast(T e) {
    		deque.addLast(e);
    	}
    	/**获取第一个元素*/
    	public T getFirst(T e) {
    		return deque.getFirst();
    	}
    	/**获取最后一个元素*/
    	public T getLast(T e) {
    		return deque.getLast();
    	}
    	/**从队头移出元素*/
    	public T removeFirst() {
    		return deque.removeFirst();
    	}
    	/**从队尾移出元素*/
    	public T removeLast() {
    		return deque.removeLast();
    	}
    	/**获取队列的大小*/
    	public int size() {
    		return deque.size();
    	}
    
    	public String toString() {
    		return deque.toString();
    	}
    
    	
    	public static void fillTest(Deque<Integer> de) {
    		for (int i = 10; i < 17; i++)
    			de.addFirst(i);
    		for (int i = 50; i < 55; i++)
    			de.addLast(i);
    	}
    
    	public static void main(String[] args) {
    		Deque<Integer> deque = new Deque<Integer>();
    		fillTest(deque);
    		System.out.println(deque);
    		while (deque.size() != 0)
    			System.out.print(deque.removeFirst() + "  ");
    		System.out.println();
    		fillTest(deque);
    		while (deque.size() != 0)
    			System.out.print(deque.removeLast() + "  ");
    		System.out.println();
    
    	}
    
    }
    

     

    展开全文
  • 队列的几种实现方式

    2018-09-20 10:31:15
    队列简介: 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除...

    队列简介:

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

    队列是一种最常用的数据结构,也是最重要的一种数据结构,这里介绍三种实现队列的方法:

    1.基于链表来实现队列。

    2.使用linkedList来实现队列。

    3.使用两个栈来实现一个队列。

     

    1.首先说第一种实现方式,基于链表来实现队列:

    首先添加一个节点类,作为队列中的节点元素

    public class Node {		//链表中的一个节点
    	Node next = null;
    	int data;
    	//构造函数,用于添加链表时候使用
    	public Node(int d) {
    		this.data = d;
    	};
    }

    再新建一个类作为我们的队列,在该类中实现队列的入队和出队以及求队列的长度和判断队列是否为空等方法

    ①.入队操作:

                 首先通过函数参数传入要入队的数据,根据传入的参数,新增一个节点Node,在入队方法中判断该队列是否为空,若该队列为空(head==tail),则该入队的节点既是队头也是队尾。若队列不为空,则将尾节点tail的next指针指向该元素,然后将tail节点指向该节点。

    public void put(Integer data) {
    		Node newNode = new Node(data);		//构造一个新节点
    		if(head == null && tail == null) {	//队列为空
    			head = newNode;
    			tail = newNode;
    		}else {
    			tail.next = newNode;
    			tail = newNode;
    		}
    	}

    ②.出队操作:

    若队列为空,则返回空。若队列不为空,则返回该队列的头结点,然后将头结点的下一个元素重新作为头节点

    public Integer pop() {
    		if(this.isEmpty()) {
    			return null;
    		}
    		int data = head.data;
    		head = head.next;
    		return data;
    	}

    ③.判断队列空和对列长度很简单,直接贴代码,不再多说。

    public int size() {
    		int count = 0;
    		Node tmp = head;
    		while(tmp != null) {
    			count++;
    			tmp = tmp.next;
    		}
    		return count;
    	}

    ④.详细代码实现:

    package com.wp.datastruct;
    
    /**
     * 利用链表来实现队列
     * */
    public class MyQueue<E> {
    	Node head = null;		//队列头
    	Node tail = null;		//队列尾
    	
    	/**
    	 * 入队操作:
    	 * 		若该队列尾空,则入队节点既是头结点也是尾节点
    	 * 		若队列不为空,则先用tail节点的next指针指向该节点
    	 * 		然后将tail节点指向该节点
    	 * */
    	public void put(Integer data) {
    		Node newNode = new Node(data);		//构造一个新节点
    		if(head == null && tail == null) {	//队列为空
    			head = newNode;
    			tail = newNode;
    		}else {
    			tail.next = newNode;
    			tail = newNode;
    		}
    	}
    	
    	/**
    	 * 判断队列是否为空:当头结点等于尾节点的时候该队列就为空
    	 * */
    	public boolean isEmpty() {
    		return head == tail;
    	}
    	
    	/**
    	 * 出队操作:
    	 * 		若队列为空,则返回null
    	 * 		否则,返回队列的头结点,并将head节点指向下一个
    	 * */
    	public Integer pop() {
    		if(this.isEmpty()) {
    			return null;
    		}
    		int data = head.data;
    		head = head.next;
    		return data;
    	}
    	
    	public int size() {
    		int count = 0;
    		Node tmp = head;
    		while(tmp != null) {
    			count++;
    			tmp = tmp.next;
    		}
    		return count;
    	}
    
    }
    

    2.使用linkedList来实现队列

    该方法是使用java中的linkedList集合来实现一个队列,通过调用linkedList中的方法来实现队列的入队出队,判空等操作

    首先new一个类来作为我们的队列,该类中包含两个属性,一个是size:用来统计该队列的长度,另一个是LinkedList对象,

    代表我们的队列。

    private LinkedList<E> list = new LinkedList<>();
    	private int size = 0;						//用于统计队列的长度

    ①.入队操作:

    应为linkedList集合中已经实现好了添加删除操作,在这里我们只需要简单的调用方法就可以实现队列的相关操作了,非常简单而且容易理解。

    public synchronized void put(E data) {		//保证线程安全,实现同步操作
    		list.add(data);
    		size++;
    	}

    ②.出队操作:

    public synchronized E pop() {
    		size--;
    		return list.removeFirst();				//从头取出
    	}

    ③.详细代码:

    public class MyQueue2<E> {
    	
    	private LinkedList<E> list = new LinkedList<>();
    	private int size = 0;						//用于统计队列的长度
    	
    	public synchronized void put(E data) {		//保证线程安全,实现同步操作
    		list.add(data);
    		size++;
    	}
    	
    	public synchronized E pop() {
    		size--;
    		return list.removeFirst();				//从头取出
    	}
    	
    	public synchronized int size() {
    		return size;
    	}
    	
    	public boolean isEmpty() {
    		return size == 0;
    	}	
    	
    }

     

    3.使用两个栈来实现一个队列。

    也可以使用两个实现好的栈来实现一个队列(这个问题可能面试笔试的时候回被问到)。

    实现方法是:

    创建两个栈s1,s2。入队的时候就只压栈到s1中。

    出队分两种情况:1.当s2不为空的使用,就弹出栈顶元素作为出队元素。

                                 2.当s2等于空,则先将s1中的元素全部弹出到s2中,再从s2中弹出栈顶元素作为出队元素。

     

    ①.入队:

    	public synchronized void put(E data) {		//使用同步处理,保证线程安全
    		s1.push(data);
    	}

    ②.出队:

    public synchronized E pop() {
    		if(!s2.isEmpty()) {
    			return s2.pop();
    		}else {
    			s2.push(s1.pop());
    			return s2.pop();
    		}
    	}

    ③.详细代码实现:

    package com.wp.datastruct;
    
    import java.util.Stack;
    
    /**
     * 利用两个栈来模拟队列操作
     * 入队操作就只是想栈s1中添加,
     * 出栈操作分为两部分:
     * 1.当s2中不为空的时候,就直接弹出s2中的栈顶数据
     * 2.当s2中为空的时候,就先把s1中的数据全部弹出到s2中然后将栈顶数据出栈
     * 
     * */
    public class MyQueue3<E> {
    	Stack<E> s1 = new Stack<>();
    	Stack<E> s2 = new Stack<>();
    	
    	public synchronized void put(E data) {		//使用同步处理,保证线程安全
    		s1.push(data);
    	}
    	
    	public synchronized E pop() {
    		if(!s2.isEmpty()) {
    			return s2.pop();
    		}else {
    			s2.push(s1.pop());
    			return s2.pop();
    		}
    	}
    	
    	public synchronized boolean isEmpty() {
    		return s1.isEmpty() && s2.empty();
    	}
    	
    }
    

     

     

    展开全文
  • 简单入门——队列

    2019-03-17 15:47:02
    队列介绍 队列(Queue)是计算机中常见的数据结构,是一种操作受限的线性表。队列遵循 FIFO (先进先出) 原则,队列元素的增加在队尾,队列元素的读、取在队首。可以通过数组、链表两种基本的数据结构来实现。 在 ...

    队列介绍

    队列(Queue)是计算机中常见的数据结构,是一种操作受限的线性表。队列遵循 FIFO (先进先出) 原则,队列元素的增加在队尾,队列元素的读、取在队首。可以通过数组、链表两种基本的数据结构来实现。

    操作系统 中常见的应用有:CPU 进程的调度、内存的分配、磁盘的管理。

    队列的基本操作有:

    1、入队。首先应检测队列中是否能插入元素,不能则不执行插入,能则在队尾插入一个元素。

    2、出队。首先应当检测队列中是否有元素,无元素则无法读取,有元素则读取栈顶元素,并将其从队列中删除。

    3、读取栈顶元素。同出队不同,该元素依旧保存在队首。

    4、判断队列是否为空

    5、返回数组中的元素个数

    基于以上 5 个基本操作,分别用数组和链表来实现队列。

    数组实现:
    用 head、tail、count 分别代表队首、队尾、队列中的元素个数,在 QueueStudy 实例对象构造时将数组大小初始化。

    class QueueStudy
    {
        private int[] queue ; // 数组队列
        private int head; // 队首
        private int tail; // 队尾
        private int count; // 队列元素
    
        public QueueStudy(int len)
        {
            queue = new int[len];
            head = 0;
            tail = 0;
            count = 0;
        }
    
        public void push(int element)
        {
            if(tail== queue.length) 
                System.out.println("队列已满,无法入队");
            else{
                queue[tail++] = element;
                count++;
            }
        }
    
        public int pop()
        {
            if(tail== 0) 
                return -1 ; // 这里用 -1 代表无元素可出队
            int num = queue[head++];
            count--;
            return num;
        }
    
        public int peek()
        {
            if(count == 0) 
                return -1 ; // 这里用 -1 代表队首无元素
            return queue[head];
        }
    
        public Boolean isEmpty()
        {
            return count==0;
        }
    
        public int size()
        {
            return count;
        }
    }
    

    链表实现

    解释:链表队列的实现比数组链表稍微复杂,需要先定义一个链表,每次让 node 指向下一节点,head 始终指向首结点

    class Node // 实现一个链表
    {
        private int element;
        Node next;
    
        public Node(int val,Node node)
        {
            this.element = val;
            this.next = node;
        }
    
        public int getElement() // 读取链表结点数据
        {
            return element;
        }
    
        public void setElement(int val) // 修改链表结点数据
        {
            this.element = val;
        }
    }
    
    public class ListQueue
    {
        Node node;
        private Node head ;
        private int count ;
    
        public ListQueue(int value) // 初始化链表队列
        {
            count = 1;
            node = new Node(value,null);
            head = node;
        }
    
        public void push(int value)
        {
            node.next= new Node(value, null);
            node = node.next;
            count++;
        }
    
        public int pop()
        {
            if(head==null) 
                return -1;
            int  num = head.getElement();
            head = head.next;
            count--;
            return num;
        }
    
        public int peek()
        {
            if(count==0) 
                return -1;
            return head.getElement();
        }
    
        public Boolean isEmpty()
        {
            return count==0;
        }
    
        public int size()
        {
            return count;
        }
    }
    

    循环队列

    循环队列 是队列的特殊形式,队尾连着队首,在队列空间允许存、取的情况下,入队和出队的位置不固定。实际上就是用 count (队列元素个数)来判断队列是否允许入队、出队。

    循环队列的进阶就是循环双端队列,队列的操作不再局限于在队首读取、在队尾插入。增加了队首插入队尾读取 的操作。

    可以尝试做一下 LeetCode 641. 设计循环双端队列

    以下为实现代码参考

    class MyCircularDeque {
        private int[] nums; // 定义一个顺序队列,用数组来存储队列元素
        private int count = 0; // count 来表示队列中当前存在的元素个数
        private int head = 0; // head 表示队列的头
        private int tail =0; // tail 表示队列的尾
    
        /** Initialize your data structure here. Set the size of the deque to be k. */
        public MyCircularDeque(int k) {
            nums =  new int[k]; // 根据 k 来初始化数组的长度
        }
        
        /** Adds an item at the front of Deque. Return true if the operation is successful. */
        public boolean insertFront(int value) {
            if(count>=nums.length) return false; // 队列元素个数超出数组长度则无法再入队
            if(head==0)
                head=nums.length-1;
            else
                head-=1;
            nums[head] = value; // 队列未满则将元素入队,尾指针以及数组元素 +1
            count++;
            return true;
        }
        
        /** Adds an item at the rear of Deque. Return true if the operation is successful. */
        public boolean insertLast(int value) {
            if(count>=nums.length) return false; // 队列元素个数超出数组长度则无法再入队
            nums[tail++] = value; // 队列未满则将元素入队,尾指针以及数组元素 +1
            count++;
            tail = tail % nums.length;
            return true;
        }
        
        /** Deletes an item from the front of Deque. Return true if the operation is successful. */
        public boolean deleteFront() {
            if(count==0) return false; // 队列为空则无法删除元素
            head++;
            head = head % nums.length; // 减少数组搬运操作直接将队列头移向下一元素
            count--;
            return true;
        }
        
        /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
        public boolean deleteLast() {
            if(count==0) return false; // 队列为空则无法删除元素
            if(tail==0)
                tail=nums.length-1; // 减少数组搬运操作直接将队列尾移向上一元素
            else
                tail-=1;
            count--;
            return true;
        }
        
        /** Get the front item from the deque. */
        public int getFront() {
            if(count==0) return -1;
            return nums[head]; 
        }
        
        /** Get the last item from the deque. */
        public int getRear() {
            if(count==0) return -1;
            if(tail==0) return nums[nums.length-1];
            return nums[tail-1];
        }
        
        /** Checks whether the circular deque is empty or not. */
        public boolean isEmpty() {
            return count==0;
        }
        
        /** Checks whether the circular deque is full or not. */
        public boolean isFull() {
            return count == nums.length;
        }
    }
    

    用队列实现栈

    需要用到两个 队列 或是一个 双端队列 实现。

    入栈用 1 个队列来存储,出栈将队列 1 中的元素都出队到队列 2,此时队列 2 首的就是应该出栈的元素,将队列 2 队首出队并返回,剩下元素再出队回队列 2 则队列实现栈完成。

    Java 代码实现如下

    class MyStack {
        private Deque <Integer> deque;
        private Deque <Integer> tempDeque;
        /** Initialize your data structure here. */
        public MyStack() {
            deque = new ArrayDeque<>();     
        }
        
        /** Push element x onto stack. */
        public void push(int x) {
            deque.offer(x);
    
        }
        
        /** Removes the element on top of the stack and returns that element. */
        public int pop() {
            tempDeque = new ArrayDeque<>();
            while(deque.size()!=0)
                tempDeque.push(deque.pop());
            int num = tempDeque.poll();
            while(tempDeque.size()!=0)
                deque.push(tempDeque.poll());
            return num;
        }
        
        /** Get the top element. */
        public int top() {
            tempDeque = new ArrayDeque<>();
            while(deque.size()!=0)
                tempDeque.push(deque.poll());
            int num = tempDeque.peek();
            while(tempDeque.size()!=0)
                deque.push(tempDeque.poll());
            return num;
        }
        
        /** Returns whether the stack is empty. */
        public boolean empty() {
            return deque.size()==0;
        }
    }
    
    展开全文
  • 队列是一种特殊的线性结构,它只允许在队列的首部(head)进行删除操作,这称为出队,在尾部进行加入数据操作,称为入队; 队列这种数据结构非常容易理解,就像我们平时去超市买东西,在收银台结账的时候需要排队,...

    本文大量饮用了相关公众号和博客图片和代码,本人只做整理总结,便于学习和使用,如有涉及到相关作者原创内容,请联系,本人将及时删除。

    img

    线性结构: 有且只有一个根节点,且每个节点最多有一个直接前驱和一个直接后继的非空数据结构

    非线性结构: 不满足线性结构的数据结构

    队列

    1、基本概念:

    1.1 定义:

    队列是指允许在一端进行插入,在另一端进行删除的线性表,又称“先进先出”的线性表

    队列是一种特殊的线性结构,它只允许在队列的首部(head)进行删除操作,这称为出队,在尾部进行加入数据操作,称为入队;

    队列这种数据结构非常容易理解,就像我们平时去超市买东西,在收银台结账的时候需要排队,先去排队的就先结账出去,排在后面的就后结账,有其他人再要过来结账,必须排在队尾不能在队中间插队。

    1.2 概念补充:

    1.2.1 数组

    数组是一个有限的类型相同的数据的集合,在内存中是一段连续的内存区域。 数组在访问操作方面有着独特的性能优势,因为数组是支持随机访问的,也就是说我们可以通过下标随机访问数组中任何一个元素,其原理是因为数组元素的存储是连续的,所以我们可以通过数组内存空间的首地址加上元素的偏移量计算出某一个元素的内存地址;

    因为数组元素的连续性要求,所以导致数组在插入和删除元素的时候效率比较低。如果要在数组中间插入一个新元素,就必须要将要相邻的后面的元素全部往后移动一个位置,留出空位给这个新元素。

    数组的缺陷
    1.一个数组中所有元素的类型必须一致;

    ​ 2.数组元素个数必须事先制定并且制定后就不能更改

    解决方法
    1.第一个缺陷靠结构体去解决,结构体允许其中的元素的类型不相同;

    2.第二个缺陷:普通数组的大小不可以实时收缩或扩展,链表可以解决;

    1.2.2 链表

    链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的,一般用于插入与删除较为频繁的场景。

    img

    上图是“单链表”示例,链表并不需要数组那样的连续空间,它只需要一个个零散的内存空间即可,因此对内存空间的要求也比数组低。

    链表的每一个节点通过“指针”链接起来,每一个节点有2部分组成,一部分是数据(上图中的Data),另一部分是后继指针(用来存储后一个节点的地址),在这条链中,最开始的节点称为Head,最末尾节点的指针指向NULL。

    「 链表 」也分为好几种,上图是最简单的一种,它的每一个节点只有一个指针(后继指针)指向后面一个节点,这个链表称为:单向链表,除此之外还有 双向链表、循环链表 等。

    img

    双向链表与单向链表的区别是前者是2个方向都有指针,后者只有1个方向的指针。双向链表的每一个节点都有2个指针,一个指向前节点,一个指向后节点。双向链表在操作的时候比单向链表的效率要高很多,但是由于多一个指针空间,所以占用内存也会多一点。

    循环链表:

    img

    其实循环链表就是一种特殊的单向链表,只不过在单向链表的基础上,将尾节点的指针指向了Head节点,使之首尾相连。

    • 链表的访问

      链表的优势并不在与访问,因为链表无法通过首地址和下标去计算出某一个节点的地址,所以链表中如果要查找某个节点,则需要一个节点一个节点的遍历

    • 链表的插入与删除

      也正式因为链表内存空间是非连续的,所以它对元素的插入和删除时,并不需要像数组那样移动其它元素,只需要修改指针的指向即可。

    例如:删除一个元素E:

    img

    加入 一个元素:

    img

    2、 队列常见分类:


    顺序队列—>顺序队列是用数组实现的队列

    链式队列—>链式队列即用链表实现的队列

    循环队列–> 循环队列是指队列是前后连成一个圆圈,它以循环的方式去存储元素,但还是会按照队列的先进先出的原则去操作

    2.1顺序队列

    用数组实现的队列,叫做 顺序队列

    用数组实现的思路是这样的:初始化一个长度为n的数组,创建2个变量指针front和rear,front用来标识队头的下标,而rear用来标识队尾的下标。因为队列总是从对头取元素,从队尾插入数据。因此我们在操作这个队列的时候通过移动front和rear这两个指针的指向即可。初始化的时候front和rear都指向第0个位置。

    当有元素需要入队的时候,首先判断一下队列是否已经满了,通过rear与n的大小比较可以进行判断,如果相等则说明队列已满(队尾没有空间了),不能再插入了。如果不相等则允许插入,将新元素赋值到数组中rear指向的位置,然后rear指针递增加一(即向后移动了一位),不停的往队列中插入元素,rear不停的移动,如图:

    img

    当队列装满的时候,则是如下情况

    img

    当需要做出队操作时,首先要判断队列是否为空,如果front指针和rear指针指向同一个位置(即front==rear)则说明队列是空的,无法做出队操作。如果队列不为空,则可以进行出队操作,将front指针所指向的元素出队,然后front指针递增加一(即向后移动了一位),加入上图的队列出队了2个元素:

    img

    所以对于数组实现的队列而言,需要用2个指针来控制(front和rear),并且无论是做入队操作还是出队操作,front或rear都是往后移动,并不会往前移动。入队的时候是rear往后移动,出队的时候是front往后移动。

    2.2 循环队列

    在顺序队列中,当队尾指针已经到数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫做“假溢出”,解决假溢出的途径----采用循环队列。

    ( 当然也可以在数组尾部已满的这种情况下,去移动数据,把数据所有的元素都往前移动以填满前面的空间,释放出尾部的空间,以便尾部还可以继续插入新元素。但是这个移动也是消耗时间复杂度的。 )

    循环队列就可以天然的解决这个问题,下面是循环队列的示意图:

    img

    可以看到,整个队列的入队和出队的过程,就是头指针 _front 和尾指针 _rear互相追赶的过程,如果 _rear追赶上了 _front就说明队满了(前提是相隔一个空闲单元),如果 _front追赶上了 _rear就说明队列空了。

    新问题:
    在循环队列中,空队特征是front = rear, 队满时也会有front = rear; 判断条件将出现二义性
    解决方案有三种:

    1. 加设标志位,让删除动作使其为1,插入动作使其为0, 则可识别当前front == rear;
    2. 使用一个计数器记录队列中元素个数(即队列长度)
    3. 人为浪费一个单元,令队满特征为 front = (rear +1)%N—空闲单元法

    这里分享2、3两种方法的C语言实现代码

    1. 方法2:计数器记录队列中元素的个数
    							
    #define	mQBufNormal			0							
    #define	mQBufFull			1							
    #define	mQBufEmpty			2
    
    typedef	struct
    {												
    	UINT8	*pu8In;								
    	UINT8	*pu8Out;								
    	UINT8	*pu8Start;								
    	UINT8	u8Length;								
    	UINT8 	u8Size;								
    }STQUEUE;	
    
    UINT8 u8QBuff[64] = {0};
    STQUEUE   stRxQueue;
    
    void  sQInit(STQUEUE *pstQ,UINT8 *pu8Start,UINT8 u8SizeTemp);
    UINT8 su8QDataIn(STQUEUE *pstQ,UINT8 u8Data);
    UINT8 su8QDataOut(STQUEUE *pstQ, UINT8 *pData);
    /************************************************************************************
    *Function name: sQInit                                *
    *Parameters:  pq: pointer to queue structure to be initialized          *
    *       start:start address of ring buffer                  *
    *       size:the size of the ring buffer                  *
    *Description: initialize a queue structure                    *
    *************************************************************************************/
    void  sQInit(STQUEUE *pstQ,UINT8 *pu8Start,UINT8 u8SizeTemp)
    {
        pstQ->pu8In = pu8Start;
        pstQ->pu8Out = pu8Start;
        pstQ->pu8Start = pu8Start;
        pstQ->u8Length = 0;
        pstQ->u8Size = u8SizeTemp;
    }
    
    /************************************************************************************
    *Function name: sQDataIn                              *
    *Parameters:  pq: pointer to queue structure to be initialized          *
    *       data:the data to be inserted into the queue             *
    *       option:how to deal with the data when the buffer is full      *
    *       cQCoverFirst:cover the first data                 *
    *       cQCoverLast:cover the latest data                 *
    *Returns:   cQBufNormal:data has been inserted into the queue         *
    *       cQBufFull:the buffer is full                    *
    *Description: insert a data into the queue                    *
    *************************************************************************************/
    UINT8 su8QDataIn(STQUEUE *pstQ,UINT8 u8Data)
    { 
    	if(pstQ->u8Length >= pstQ->u8Size)			// use (>=) just in case
    	{
    		return(mQBufFull);
    	}
    	else
    	{
    		*(pstQ->pu8In) = u8Data;
    		pstQ->u8Length++;
    		if(pstQ->pu8In >= pstQ->pu8Start + pstQ->u8Size - 1)	// use (>=) just in case 
    		{
    			pstQ->pu8In = pstQ->pu8Start;
    		}
    		else
    		{
    			pstQ->pu8In++;
    		}
    		return(mQBufNormal);
    	}
    }
    /************************************************************************************
    *Function name: sQDataOut                             *
    *Parameters:  pq: pointer to queue structure to be initialized          *
    *       pdata:the address to save the data                  *
    *Returns:   cQBufNormal:data has been inserted into the queue         *
    *       cQBufEmpty:the buffer is empty                    *
    *Description: Get a data from the queue                     *
    *************************************************************************************/
    UINT8 su8QDataOut(STQUEUE *pstQ, UINT8 *pData)
    {
    	if(pstQ->u8Length == 0)
    	{
    		return(mQBufEmpty);
    	}
    	*pData = *(pstQ->pu8Out);
    	pstQ->u8Length--;
    	if(pstQ->pu8Out >= pstQ->pu8Start + pstQ->u8Size - 1)	// use (>=) just in case 
    	{
    		pstQ->pu8Out = pstQ->pu8Start;
    	}
    	else
    	{
    		pstQ->pu8Out++;
    	}	
    	return(mQBufNormal);
    }
    
    
    
    
    1. 空闲单元法

    img

    #include <stdio.h>
    #include <stdlib.h>
    #define Maxsize 10
    
    typedef int dataType; 
    typedef struct
    {
    	dataType *base;
    	int front;
    	int rear;
    }CyQueue;
    
    int create(CyQueue *q)
    {
    	q->base=(dataType *)malloc(Maxsize*sizeof(dataType));
    	if(!q->base)
    	{
    		printf("Space allocation failed!\n");
    		return;
    	}
    	q->front=q->rear=0;
    	return;
    }
    
    int EnQueue(CyQueue *q,dataType value)
    {
    	if((q->rear+1)%Maxsize==q->front)
    	{
    		printf("Cyclic Queue is Full!\n");
    		return;
    	}
    	q->base[q->rear]=value;
    	q->rear=(q->rear+1)%Maxsize;
    	printf("EnQueue Element is %d\n",value);
    	return;
    }
    
    int DeQueue(CyQueue *q,dataType *value)
    {
    	if(q->front==q->rear)
    	{
    		printf("Cyclic Queue is Empty!\n");
    		return;
    	}
    	*value=q->base[q->front];
    	q->front=(q->front+1)%Maxsize;
    	printf("DeQueue Element is %d\n",*value);
    	return;
    } 
    
    dataType getHead(CyQueue *q)
    {
    	if(q->front==q->rear)
    	{
    		printf("Cyclic Queue is Empty! Unable to fetch Header of Cyclic Queue\n");
    		return;
    	}
    	return(q->base[q->front]);
    }
    
    int main()
    {
    	CyQueue q;
    	dataType elem;
    	int i;
    	create(&q);
    	
    	for(i=1;i<11;i++)
    	EnQueue(&q,i);
    	printf("The Header is %d\n",getHead(&q));
    	
    	for(i=0;i<10;i++)
    	DeQueue(&q,&elem);
    	printf("The Header is %d\n",getHead(&q));
    	return 0;
    } 
    
    

    2.3 链式队列

    用链表实现的队列,叫做 链式队列: 链式队列就是一个操作受限的单向链表

    在这里插å¥å›¾ç‰‡æè¿°

    简单描述一下上图的步骤

    第一步:初始化队列(就是添加一个头节点在队列中),头结点不存储数据,使队首指针和队尾指针都指向头结点

    第二步:入队(添加节点),使队尾指针指向头新建的节点,队首指针不变仍然指向头结点

    出队时队首指针的位置是不变的,队首指针始终指向头节点,出队时头节点的指针域指向出队节点的后一节点,并将出队的节点用free()函数释放掉

    注:

    1.根据队列的入队,出队规则,设置头结点便于实现出队操作;
    2.头指针front始终指向头结点,尾指针rear指向队列最后一个元素,length用于记录队列中元素个数,遍历操作会用到length。

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef int dataType;
    
    typedef struct Node
    {
    	dataType data;
    	struct Node *next;
    }QueueNode;
    
    typedef struct
    {
    	QueueNode *front;
    	QueueNode *rear;
    	int length;
    }LinkQueue;
    
    int create(LinkQueue *q)
    {
    	q->front=q->rear=(QueueNode *)malloc(sizeof(QueueNode));
    	q->front->next=NULL;
    	q->front->data=0;
    	q->length=0;
    	return;
    }
    
    int EnQueue(LinkQueue *q,dataType value)
    {
    	QueueNode *p;
    	
    	p=(QueueNode *)malloc(sizeof(QueueNode));
        p->data=value;
        p->next=NULL;
        q->length++;
        
        q->rear->next=p;
        q->rear=p;
    	return; 
    }
    
    int DeQueue(LinkQueue *q,dataType *value)
    {
        QueueNode *p;
        
        if(q->front->next==NULL)
        {
        	printf("LinkQueue is Empty!\n");
        	return;
    	}
    	
        p=q->front->next;
    	*value=p->data;
        q->front->next=p->next;
        q->length--;
        printf("DeQueue Element is %d.\n",*value);
        free(p);
    	return;
    }
    
    dataType getHead(LinkQueue *q)
    {
    	if(q->front->next==NULL)
        {
        	printf("LinkQueue is Empty!\n");
        	return;
    	}
    	return(q->front->next->data);
    }
    
    int traverse(LinkQueue *q)
    {
    	QueueNode *p;
    	int i;
    	
    	if(q->front->next==NULL)
        {
        	printf("LinkQueue is Empty!\n");
        	return;
    	}
    	
    	p=q->front->next;
    	printf("Head -> ");
    	for(i=0;i<q->length;i++)
    	{
         	printf("%d -> ",p->data);
    	    p=p->next;
    	}
    	printf("NULL\n");
    	return;
    }
    
    int main()
    {
    	LinkQueue q;
    	int i;
    	dataType value;
    	
    	create(&q);
    	
    	for(i=1;i<10;i++)
    	EnQueue(&q,i);
    	traverse(&q);
    	printf("\n");
    	
    	for(i=1;i<10;i++)
    	{
    	   DeQueue(&q,&value);
    	   printf("First Element is %d.\n",getHead(&q));
    	   traverse(&q);
    	   printf("\n");
    	}
    	
    	return 0;
    }
    
    

    3、小结

    1.顺序、循环队列是用数组实现的,首指针在出队的时候移动,尾指针在入队的时候移动,需要考虑队列为空和队列为满的两种情况

    2.链式队列是用链表实现的,首指针不移动始终指向头节点,尾指针在入队的时候移动,只考虑队列为空的情况(不用考虑满是因为链表长度在程序运行过程中可以不断增加,只要存储空间够malloc就能申请内存空间来存放节点)

    展开全文
  • 队列定义 队列(queue )简称队,它同堆栈一样,也是一种运算受限的线性表, 其限制是仅允许在表的一端进行插入,而在表的另一端进行删除。 在队列中把插入数据元素的一端称为 队尾(rear) ),删除数据元素的一端...
  • 数据结构之队列

    2018-07-25 19:40:40
    队列简介 队列简单来说就是一种允许再一段进行插入,再另一端进行删除操作的线性表,就像排队取票一样。插入的一段我们称之为队尾,删除的一端我们称之为队首。队列具有FIFO(先进先出)的特性。队列的结构图如下所...
  • 队列 队列是一种受限的线性表。它只允许在表的一端进行插入,另一端进行删除。队列具有“先入先出”的特性,它的应用非常广泛,它主要应用在树的层次遍历、图的广度优先遍历、键盘的输入缓冲区、操作系统和事务管理...
  • 队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。允许插入的端是队尾,允许删除的端是队头。所以说队列是一个先进先出的线性表,相应的也有顺序存储和链式存储两种方式。顺序存储就是用...
  • 队列基本操作

    2019-08-04 17:40:43
    /*****************************************/ //LQueue.h #pragma once typedef int QElemType; //typedef struct BTNode* QElemType; typedef struct QNode { QElemType data; struct QNode *_pNext;...}...
  • 什么是队列?

    2019-06-17 19:10:25
    类似于链表和堆栈,队列也是存储数据的结构。队列中数据进入队列的顺序很重要,一般来说,队列就是一群人或者事物按照排好的顺序等待接受服务或者处理。 定义:队列,又称为伫列(queue),是先进先出(FIFO, First...
  • 循环队列 基本概念

    2018-03-07 17:46:53
    循环队列队列的一种特殊形式。首先介绍队列,然后引申出循环队列队列又称为“先进先出”(FIFO)线性表 限定插入操作只能在队尾进行,而删除操作只能在队首进行 队列也可以采用顺序存储结构或链表结构来实现...
  • 队列(queue)原理

    2018-01-15 13:39:54
    像栈一样,队列(queue)也是一种线性表,它的特性是先进先出,插入在一端,删除在另一端。就像排队一样,刚来的人入队(push)要排在队尾(rear),每次出队(pop)的都是队首(front)的人。如图1,描述了一个队列模型。...
  • 循环队列–C语言实现–数据结构目录循环队列C语言实现数据结构目录 一 要求 二 循环队列 三 循环队列的算法设计 1 建立循环队列 2 置空队列 3 入队 4 出队 5 打印队 四 程序 1 程序的结构 2 程序源码 五 程序测试 1 ...
  • 在大型平台的分布式项目中,消息队列MQ具有重要的作用,经常用在边缘业务功能的处理中,比如日志管理【下面将以Bug日志保存为例】,因为像日志保存、新用户注册发送邮件等操作都不是主干业务,可以放在消息队列异步...
  • 周末测试了一下RabbitMQ的性能,RabbitMQ是使用Erlang编写的一个开源的消息队列,本身支持很多的协议:AMQP,XMPP, SMTP, STOMP,也正是如此,使的它变的非常重量级,更适合于企业级的开发。个人认为,在互联网开发...
  • 大型网站架构之分布式消息队列   以下是消息队列以下的大纲,本文主要介绍消息队列概述,消息队列应用场景和消息中间件示例(电商,日志系统)。 本次分享大纲 消息队列概述消息队列应用场景消息中间件示例...
  • 1、消息队列(以下简称MQ)天生就是处理高并发的有力工具,因为他可以把一个完整的流程拆为多部分,并发进行,或者不是很重要的步骤模块延迟进行。大家所熟悉的是消息队列在大基数用户项目的注册模块和电商项目的...
  • posix消息队列与system v消息队列的差别: (1)对posix消息队列的读总是返回最高优先级的最早消息,对system v消息队列的读则可以返回任意指定优先级的消息。 (2)当往一个空队列放置一个消息时,posix消息队列...
  • 下面来说说如何用不用消息队列来进行进程间的通信,消息队列与命名管道有很多相似之处。 一、什么是消息队列 消息队列提供了一种从一个进程向另一个进程发送一个数据块的方法。 每个数据块都被认为含有一个类型,...
  • 生活中有很多队列的影子,比如打饭排队,买火车票排队问题等,可以说与时间相关的问题,一般都会涉及到队列问题;从生活中,可以抽象出队列的概念,队列就是一个能够实现“先进先出”的存储结构。队列分为链式队列和...
1 2 3 4 5 ... 20
收藏数 1,196,147
精华内容 478,458
热门标签
关键字:

队列