队列 订阅
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(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();
    
    	}
    
    }
    

     

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

    千次阅读 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;
        }
    }
    
    展开全文
  • 队列定义 队列(queue )简称队,它同堆栈一样,也是一种运算受限的线性表, 其限制是仅允许在表的一端进行插入,而在表的另一端进行删除。 在队列中把插入数据元素的一端称为 队尾(rear) ),删除数据元素的一端...

    队列定义

    队列(queue )简称队,它同堆栈一样,也是一种运算受限的线性表,
    其限制是仅允许在表的一端进行插入,而在表的另一端进行删除。
    在队列中把插入数据元素的一端称为 队尾(rear) ),删除数据元素的一端称为 队首(front) )。
    向队尾插入元素称为 进队或入队,新元素入队后成为新的队尾元素;
    从队列中删除元素称为 离队或出队,元素出队后,其后续元素成为新的队首元素。
    由于队列的插入和删除操作分别在队尾和队首进行,每个元素必然按照进入的次序离队,
    也就是说先进队的元素必然先离队,所以称队列为 先进先出表(First In First Out,简称FIFO)。

    生活案例:排队打饭,排队进地铁站,上地铁
    技术案例:多线程中就绪队列和阻塞队列


    对于队列的主要操作是入队和出队操作

    public interface Queue {
        // 返回队列的大小
        public int getSize();
    
        // 判断队列是否为空
        public boolean isEmpty();
    
        // 数据元素 e 入队
        public void enqueue(Object e);
    
        // 队首元素出队
        public Object dequeue();
    
        // 取队首元素
        public Object peek();
        
    }       

    队列的存储结构
        顺序队列
        
        方法1:使用数组作为存储结构:
         
        
            
        缺点:通过出队操作将数据弹出队列后,front之前的空间还能够再次得到吗?
            不能。所以使用普通数组实现队列,就再也不能使用front之前的空间了,这会导致大量空间丢失

        
        方法2:使用循环数组作为存储结构:    
        为了解决这个问题,将普通数组换成循环数组。在循环数组中,末尾元素的下一个元素不是数组外,而是数组的头元素。
        这样就能够再次使用front之前的存储空间了
         

        链式队列
        队列的链式存储可以使用单链表来实现。
        为了操作实现方便,这里采用带头结点的单链表结构。
        根据单链表的特点,选择链表的头部作为队首,链表的尾部作为队尾。
        除了链表头结点需要通过一个引用来指向之外,还需要一个对链表尾结点的引用,以方便队列的入队操作的实现。
        为此一共设置两个指针,一个队首指针和一个队尾指针,如图 所示。
        队首指针指向队首元素的前一个结点,即始终指向链表空的头结点,队尾指针指向队列当前队尾元素所在的结点。
        当队列为空时,队首指针与队尾指针均指向空的头结点

    双端队列deque  double ended queue  通常读为“deck”
          
    所谓双端队列是指两端都可以进行进队和出队操作的队列,如下图所示,将队列的两端分别称为前端和后端,两端都可以入队和出队。其元素的逻辑结构仍是线性结构


     
    在双端队列进队时:前端进的元素排列在队列中后端进的元素的前面,后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时,无论前端出还是后端出,先出的元素排列在后出的元素的前面。

    输出受限的双端队列,即一个端点允许插入和删除,另一个端点只允许插入的双端队列。 

    输入受限的双端队列,即一个端点允许插入和删除,另一个端点只允许删除的双端队列。 

        双端队列既可以用来队列操作,也可以用来实现栈操作(只操作一端就是栈了)

    展开全文
  • 队列基本操作

    万次阅读 多人点赞 2018-08-28 21:59:36
    /*****************************************/ //LQueue.h #pragma once typedef int QElemType; //typedef struct BTNode* QElemType; typedef struct QNode { QElemType data; struct QNode *_pNext;...}...

    1.队列的概念
    只允许在一端插入数据操作,在另一端进行删除数据操作的特殊线性表;进行插入操作的一端称为队尾(入队列),进行删除操作的一端称为队头(出队列);队列具有先进先出(FIFO)的特性。


    2.顺序队列
    (1)队头不动,出队列时队头后的所有元素向前移动
    这里写图片描述
    缺陷:操作是如果出队列比较多,要搬移大量元素。

    (2)队头移动,出队列时队头向后移动一个位置
    这里写图片描述
    如果还有新元素进行入队列容易造成假溢出。

    • 假溢出:顺序队列因多次入队列和出队列操作后出现的尚有存储空间但不能进行入队列操作的溢出。
    • 真溢出:顺序队列的最大存储空间已经存满二又要求进行入队列操作所引起的溢出。

    3.循环队列
    这里写图片描述
    循环队列如何进行判空和满操作:

    • 少用一个存储单元
    • 设置一个标记flag;
      初始值 flag = 0;入队列:flag = 1; 出队列:flag = 0;
      队列为空时:(front == rear && flag == 0)
      队列为满时:(front == rear && flag == 1)
    • 设置一个计数器

    4.链式队列
    链式队列:特殊的单链表,只在单链表上进行头删尾插的操作
    ***【1.定义一个队列结构体】***】

    • 由于是链式队列,所以先定义一个存放数据域和指针域的结构体
    • 队列结构体中定义一个队头指针和队尾指针
    typedef int QElemType;
    //typedef struct BTNode* QElemType;
    typedef struct QNode
    {
    	QElemType data;
    	struct QNode *_pNext;
    }QNode;
    
    typedef struct LQueue
    {
    	QNode *pFront;
    	QNode *pRear;
    }LQueue;
    

    【2.创建新结点】

    //创建新结点
    static QNode *BuyLQNode(QElemType data)
    {
    	QNode *pLQNode = (QNode *)malloc(sizeof(QNode));
    	if (NULL == pLQNode)
    	{
    		printf("申请空间失败!\n");
    		assert(pLQNode);
    	}
    	pLQNode->data = data;
    	pLQNode->_pNext = NULL;
    
    	return pLQNode;
    }
    

    【3.初始化队列】

    • 让队列的队头,队尾分别指向空
    void LQueueInit(LQueue *q)
    {
    	assert(q);
    	q->pFront = q->pRear = NULL;
    }
    

    【4.入队列】
    这里写图片描述

    • 判断队中是否有元素
    • 找到队尾元素
    • 让新入队的元素链在原先队列的队尾上,更新新的队尾
    void LQueuePush(LQueue *q, QElemType data)
    {
    	assert(q);
    	if (NULL == q->pFront)
    	{
    		q->pFront = q->pRear = BuyLQNode(data);
    		return;
    	}
    	q->pRear->_pNext = BuyLQNode(data);
    	q->pRear = q->pRear->_pNext;
    }
    

    【5.出队列】
    这里写图片描述

    • 这里的出队列采用是让队头元素不断后移,刷新队头元素,这样优化时间效率
    void LQueuePop(LQueue *q)
    {
    	assert(q);
    	QNode *pDel;
    	if (NULL == q->pFront)
    	{
    		return;
    	}
    
    	if (q->pFront == q->pRear)
    	{
    		q->pRear = NULL;
    	}
    
    	pDel = q->pFront;
    	q->pFront = q->pFront->_pNext;
    	free(pDel);
    }
    

    【6.返回队头元素】

    • 直接返回队头元素
    QElemType LQueueTop(LQueue *q)
    {
    	assert(q);
    	return q->pFront->data;
    }
    

    【7.返回队尾元素】

    • 直接返回队尾元素
    QElemType LQueueBack(LQueue *q)
    {
    	assert(q);
    	return q->pRear->data;
    }
    

    【8.计算队列长度】

    • 定义一个变量count
    • 将队列从头到尾遍历,每访问一个元素count加1一下
    • 最后count的值就是队列长度
    int LQueueSize(LQueue *q)
    {
    	int count = 0;
    	QNode *pCur;
    	assert(q);
    	pCur = q->pFront;
    	while (pCur)
    	{
    		pCur = pCur->_pNext;
    		count++;
    	}
    	return count;
    }
    

    【9.队列判空操作】

    int LQueueEmpty(LQueue *q)
    {
    	return NULL == q->pFront;
    }
    

    5.完整代码块

    /*****************************************/
    //LQueue.h
    
    typedef int QElemType;
    //typedef struct BTNode* QElemType;
    typedef struct QNode
    {
    	QElemType data;
    	struct QNode *_pNext;
    }QNode;
    
    typedef struct LQueue
    {
    	QNode *pFront;
    	QNode *pRear;
    }LQueue;
    
    
    //初始化
    void LQueueInit(LQueue *q);
    
    //入队列
    void LQueuePush(LQueue *q, QElemType data);
    
    //出队列
    void LQueuePop(LQueue *q);
    
    //返回队头元素
    QElemType LQueueTop(LQueue *q);
    
    //返回返回队列长度
    int LQueueSize(LQueue *q);
    
    //队列是否为空
    int LQueueEmpty(LQueue *q);
    
    
    /************************************************/
    //LQueue.c
    
    #include <stdlib.h>
    #include <assert.h>
    #include <stdio.h>
    
    //创建新结点
    static QNode *BuyLQNode(QElemType data)
    {
    	QNode *pLQNode = (QNode *)malloc(sizeof(QNode));
    	if (NULL == pLQNode)
    	{
    		printf("申请空间失败!\n");
    		assert(pLQNode);
    	}
    	pLQNode->data = data;
    	pLQNode->_pNext = NULL;
    
    	return pLQNode;
    }
    
    //初始化
    void LQueueInit(LQueue *q)
    {
    	assert(q);
    	q->pFront = q->pRear = NULL;
    }
    
    //入队列
    void LQueuePush(LQueue *q, QElemType data)
    {
    	assert(q);
    	if (NULL == q->pFront)
    	{
    		q->pFront = q->pRear = BuyLQNode(data);
    		return;
    	}
    	q->pRear->_pNext = BuyLQNode(data);
    	q->pRear = q->pRear->_pNext;
    }
    
    //出队列
    void LQueuePop(LQueue *q)
    {
    	assert(q);
    	QNode *pDel;
    	if (NULL == q->pFront)
    	{
    		return;
    	}
    
    	if (q->pFront == q->pRear)
    	{
    		q->pRear = NULL;
    	}
    
    	pDel = q->pFront;
    	q->pFront = q->pFront->_pNext;
    	free(pDel);
    }
    
    //返回队头元素
    QElemType LQueueTop(LQueue *q)
    {
    	assert(q);
    	return q->pFront->data;
    }
    
    //返回队尾元素
    QElemType LQueueBack(LQueue *q)
    {
    	assert(q);
    	return q->pRear->data;
    }
    
    //返回返回队列长度
    int LQueueSize(LQueue *q)
    {
    	int count = 0;
    	QNode *pCur;
    	assert(q);
    	pCur = q->pFront;
    	while (pCur)
    	{
    		pCur = pCur->_pNext;
    		count++;
    	}
    	return count;
    }
    
    //队列是否为空
    int LQueueEmpty(LQueue *q)
    {
    	return NULL == q->pFront;
    }
    

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

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

    2020-11-19 17:43:41
    目录一、Queue1、什么是队列(Queue)2、方法3、代码实现4、运行结果二、Deque1、什么是双端队列(Deque)2、方法3、代码实现4、运行结果 一、Queue 1、什么是队列(Queue) 队列是一种特殊的线性表,它只允许在表...
  • 队列

    2020-11-18 15:55:34
    队列】 顺序队列 如果不采用循环队列的方式,很多空间会被浪费掉,效率低,因此使用循环队列。 循环队列: 判空:front == rear 判满:front == (rear + 1) % MaxSize 入队尾后移:rear = (rear + 1) % MaxSize ...
  • @队列一.概念二.原理实现1.节点2.队列3.入队4.出队5.销毁三.代码 一.概念 和栈相反,队列是一种先进先出(first in first out = FIFO)的结构。FIFO是单片机的FIFO吗?它是一种线性表,只允许在表的一端插入元素,另...
  • 队列Java实现

    2020-11-21 16:29:31
    队列 1、数组实现队列 1)基本思路 (1)类属性 ①数组的最大容量:maxSize ②数组:arr[] ③队头:front 指向队首的前一个元素 ④队尾:rear 指向队尾元素 (2)类方法 ①判断队列是否为空 ②判断队列是否已满 ③...
  • 数据结构系列-队列的基本操作

    万次阅读 多人点赞 2018-03-19 23:41:27
    队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。允许插入的端是队尾,允许删除的端是队头。所以说队列是一个先进先出的线性表,相应的也有顺序存储和链式存储两种方式。顺序存储就是用...
  • 队列(queue)原理

    万次阅读 2016-11-17 10:19:57
    像栈一样,队列(queue)也是一种线性表,它的特性是先进先出,插入在一端,删除在另一端。就像排队一样,刚来的人入队(push)要排在队尾(rear),每次出队(pop)的都是队首(front)的人。如图1,描述了一个队列模型。...
  • 循环队列 基本概念

    万次阅读 多人点赞 2018-03-07 15:45:16
    循环队列队列的一种特殊形式。首先介绍队列,然后引申出循环队列队列又称为“先进先出”(FIFO)线性表 限定插入操作只能在队尾进行,而删除操作只能在队首进行 队列也可以采用顺序存储结构或链表结构来实现...
  • 循环队列–C语言实现–数据结构

    万次阅读 多人点赞 2017-06-22 16:36:45
    循环队列–C语言实现–数据结构目录循环队列C语言实现数据结构目录 一 要求 二 循环队列循环队列的算法设计 1 建立循环队列 2 置空队列 3 入队 4 出队 5 打印队 四 程序 1 程序的结构 2 程序源码 五 程序测试 1 ...
  • 循环队列

    万次阅读 多人点赞 2018-10-31 18:25:58
    循环队列出现的原因 :顺序队列出队后 的空间不能再次利用,造成资源浪费。所以出现循环队列 这个代码是用tag标记的循环队列 思路:(rear+1)%m==front 则队列满,(front+1)%m == rear则队列空。队列开始为空,设...
  • 队列只允许在表的一端进行插入(入队)、删除(出队)操作。允许插入的一端称为队尾,允许删除的一端称为队头。 &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;队列的基本操作包括: 初始化...
  • 循环队列是对队列的一种改进,它比队列适用的范围更广,例如Linux内核当中的环形缓冲区就是基于循环队列来设计的。本文主要任务是通过C语言来实现一个循环队列的数据结构,以及对循环队列的基本操作。 1、循
  • JAVA循环队列

    千次阅读 2017-09-15 15:25:44
    关于自定义循环队列的实现原理和要点可以参见之前的博文系列:循环队列及C语言实现。这里主要对JAVA下的具体实现方式与原理进行说明。 一、JAVA 中已经自带了 Queue、DQueue、ArrayList、LinkedList 等常用的数据...
  • 队列——链队列和循环队列

    千次阅读 2018-11-03 16:02:15
    队列 转载:https://www.cnblogs.com/muzijie/p/5655228.html 1 链队列的存储结构  将对头指针front指向链队列的头结点,队尾指针rear指向终端结点。 空队列时,头指针front和尾指针rear都指向头结点。 ...
  • 循环队列和链式结构队列

    千次阅读 2017-02-27 13:22:04
    一、循环队列的基础知识 1,循环队列有几个参数需要确定:  有两个参数,front和rear 2,循环队列各个参数的含义 (1)队列初始化时,front和rear值都为零; (2)当队列不为空时,front指向队列的第一...
  • 循环队列的各种基本运算

    千次阅读 2017-12-04 16:07:33
    循环队列的各种基本运算 码文不易,如果帮助到您,希望您可以帮我刷一下点击量,与您无害,与我有益谢谢 支持原创 。   欢迎大家阅读我的博客,如果有错误请指正,有问题请提问,我会尽我全力改正错误回答...
  • 队列的顺序存储实现—循环队列

    千次阅读 2015-04-17 21:37:40
    队列(queue)是一种只允许在一端插入元素,而在另一端删除元素的线性表。它是一种先进先出(First In First Out,FIFO)的线性表。我们把允许插入的一端称为队尾,允许删除元素的一端称为队头。由于队列也是一种...
  • 没什么背景,就是想研究下队列。 什么是队列队列在生活中可谓是无处不在。最常见的就是去超市买菜称重时大妈们排得贼长的队列(这是理想情况,通常是围成一圈),还有超市结账的队伍,还有以前食堂打饭...
  • C语言实现循环队列

    千次阅读 2020-06-24 15:58:46
    详解循环队列的巧妙之处
  • 循环队列的操作(循环队列

    千次阅读 2013-10-17 18:58:46
    现有一长度为n的整数序列和一最大容量为m的循环队列(用长为m+1的一维数组实现),要求将该序列中的偶数存入循环队列中;当循环队列满时,将循环队列中的所有元素全部出队,并按存入的先后顺序在同一行内依次输出,...
  • 队列之顺序队列与循环队列

    千次阅读 2016-03-24 16:03:32
    一、队列的概念  只能在表的一端进行插入操作,只能在表的另一端进行删除操作,这种数据结构称为队列。把允许插入的一端叫队尾(rear),允许删除的一端叫对头(front)。 二、队列的分类  队列本身也是一种...
  • 循环队列为充分利用向量空间,克服”假溢出”...循环队列的问题循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列
  • 队列 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端...
  • 数据结构:循环队列(C语言实现)

    万次阅读 多人点赞 2014-03-07 19:15:06
    静态队列一般用数组来实现,但此时的队列必须是循环队列,否则会造成巨大的内存浪费;链式队列是用链表来实现队列的。这里讲的是循环队列,首先我们必须明白下面几个问题 一、循环队列的基础知识 1
  •  循环队列的提出主要是用于解决顺序队列的假溢出问题。解决假溢出的办法就是后面满了,再从头开始,头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。本文将从循环队列的顺序存储和链队列出发...
  • 一、循环队列循环队列存储结构typedef int QElemType; typedef struct{ QElemType *base; int front; int rear; }SqQueue; 实现循环语句 可以把循环队列想象成一个圈 因为循环队列假如是数据能占所

空空如也

1 2 3 4 5 ... 20
收藏数 1,329,680
精华内容 531,872
关键字:

队列