队列_队列 c语言 - 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();
    
    	}
    
    }
    

     

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

    千次阅读 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;
        }
    }
    
    展开全文
  • 队列的几种实现方式

    千次阅读 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();
    	}
    	
    }
    

     

     

    展开全文
  • 队列定义 队列(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”
          
    所谓双端队列是指两端都可以进行进队和出队操作的队列,如下图所示,将队列的两端分别称为前端和后端,两端都可以入队和出队。其元素的逻辑结构仍是线性结构


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

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

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

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

    展开全文
  • 队列基本操作

    万次阅读 多人点赞 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;...}...
  • ** 用栈实现 ** 建立一个栈。 根节点进栈,访问左子树。 根节点出栈,访问右子树。 代码(以中序遍历为例)。 Status InOrderTraverse(BiTree T){ //创建一个指针T,指向根节点 ...StackEmpty...
  • 层次遍历(bfs+队列); #include &lt;vector&gt; #include &lt;iostream&gt; #include &lt;stack&gt; #include &lt;queue&gt; using namespace std; struct BitNode { int ...
  • 栈和队列在遍历二叉树中的使用

    千次阅读 2016-08-31 13:11:36
    栈和队列在二叉树遍历的使用,非递归二叉树遍历
  • 首先我们要先自己建立一个二叉树,我们先根据我自己随便写的二叉树建立一个列表保存二叉树的各个节点的信息,当然你也可以直接写个程序自己建立。 node_list = [ {'data':'A', 'left':'B', 'right':'C', 'is_...
  • 数据结构系列-队列的基本操作

    万次阅读 多人点赞 2018-03-20 07:31:52
    队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。允许插入的端是队尾,允许删除的端是队头。所以说队列是一个先进先出的线性表,相应的也有顺序存储和链式存储两种方式。顺序存储就是用...
  • 循环队列 基本概念

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

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

    万次阅读 2018-01-15 13:39:54
    像栈一样,队列(queue)也是一种线性表,它的特性是先进先出,插入在一端,删除在另一端。就像排队一样,刚来的人入队(push)要排在队尾(rear),每次出队(pop)的都是队首(front)的人。如图1,描述了一个队列模型。...
  • 怎么理解无界队列和有界队列

    万次阅读 2018-11-03 16:15:26
    有界队列:就是有固定大小的队列。比如设定了固定大小的 LinkedBlockingQueue,又或者大小为 0,只是在生产者和消费者中做中转用的 SynchronousQueue。 无界队列:指的是没有设置固定大小的队列。这些队列的特点是...
  • hive 设置队列

    万次阅读 2016-11-01 09:09:32
    set mapreduce.job.queuename=queue1
  • MQ 基本概念

    万次阅读 2012-05-07 19:06:04
    对象(objects) ...队列管理器(Queue managers) 队列(Queues) 名字列表(Namelists) 分发列表(Distribution lists) 进程定义(Process definitions) 通道(Channels) 存储类(Storage cl
  • RabbitMQ的死信队列的应用

    万次阅读 多人点赞 2019-12-03 18:37:15
    最近在项目中用到了RabbitMQ来做异步处理,自己将这块儿系统的搞了搞,下面主要记录一下自己在研究过程中对死信队列的一些研究。 【实践】 一、如何配置死信队列? 1、增加死信队列(exchange-ttl-to.q...
  • ipcs -qp: 显示往消息队列中放消息和从消息队列中取消息的进程ID ipcs -q -i msgid: 显示该消息队列结构体中的消息信息: ipcs -ql : 显示消息队列的限制信息: 取得ipc信息: ipcs [-m|-q|-s] -m 输出有关...
  • 现有一个循环队列,其队头指针为 front,队尾指针为 rear,循环队列的总长度为 N,问怎么判断循环队列满了? 正确答案: D front==rear front==rear+1 front==rear%n front==(rear+1)%n 当...
  • kafka查看队列的消费情况

    万次阅读 2017-05-15 12:59:57
    kafka-run-class.sh kafka.tools.ConsumerOffsetChecker --broker-info --group $group --topic $topic --zookeeper $zk_host:2181
1 2 3 4 5 ... 20
收藏数 1,228,488
精华内容 491,395
关键字:

队列