精华内容
下载资源
问答
  • /* 1、在队列中,允许插入的一端叫队尾(rear),允许删除的一端称为队头(front)。 2、队头指针始终指向队列头元素(先出队,后++) ... (rear+1) % MAXQSIZE = front,循环队列满(rear始终指向空...
    /*
        1、在队列中,允许插入的一端叫队尾(rear),允许删除的一端称为队头(front)。
        2、队头指针始终指向队列头元素(先出队,后++)
       	   队尾指针始终指向队列尾元素的下一个位置(先++,后进队)
        3、少用一个元素的空间
    	  front = rear,循环队列空
    	  (rear+1) % MAXQSIZE = front,循环队列满(rear始终指向空)
        4、
    */
    typedef int ElementType;
    
    class queueRecord{
    private:
        int capacity;
        int front;
        int rear;//队尾
        int size;//实际队长(也可用来判断空或满)
        ElementType *pArray;
    public:
        queueRecord(int c=100,int f=0,int r=0,int s=0,ElementType*p=NULL):
            capacity(c),front(f),rear(r),size(s),pArray(p){
                createQueue();
            };//调用createQueue申请数组空间
        ~queueRecord(){};
    
        void createQueue();
        bool isEmpty();
        bool isFull();
        void makeEmpty();
        void disposeQueue();
        void enQueue(ElementType e);
        ElementType getFront();
        void deQueue();
    
    };
    
    void queueRecord::createQueue(){
        pArray = new ElementType[capacity];
    }
    
    bool queueRecord::isEmpty(){
        return front==rear;//return size==0;
    }
    
    bool queueRecord::isFull(){
        return (rear+1)%capacity==front;
    }
    
    void queueRecord::makeEmpty(){
        front=0;
        rear=0;
        size=0;
    }
    
    void queueRecord::disposeQueue(){
        if(!pArray) delete pArray;
    }
    
    void queueRecord::enQueue(ElementType e){
        if(isFull())
            cout<<"full queue!";
        else{
            pArray[rear]=e;
            rear=(rear+1)%capacity;
            size++;
        }
    }
    
    ElementType queueRecord::getFront(){
        return pArray[front];
    }
    
    void queueRecord::deQueue(){
        front=(front+1)%capacity;
    }
    
    #include<cstdlib>
    #include<iostream>
    using namespace std;
    typedef int ElementType;
    
    class Node{
        friend class queueRecord;
    private:
        ElementType data;
        Node* _next;
    public:
        Node(ElementType e=0, Node*p=NULL):data(e),_next(p){}
        ~Node();
    };
    class queueRecord{
    private:
        Node* front;
        Node* rear;//队尾
        int size;//实际队长(也可用来判断空或满)
    public:
        queueRecord();
        ~queueRecord(){};
    
        bool isEmpty();
        void makeEmpty();
        ElementType getFront();
        void enQueue(ElementType e);
        void deQueue();
    };
    
    queueRecord::queueRecord(){
        front = new Node(0,NULL);//front指向头结点且始终不变
        rear = front;
        size = 0;
    }
    
    bool queueRecord::isEmpty(){
        return size==0;//front==rear
    }
    
    void queueRecord::makeEmpty(){
        while(!isEmpty())
            deQueue();
    }
    
    ElementType queueRecord::getFront(){
        if(isEmpty()){
            cout<<"Empty queue!";
            return 0;
        }
        else
            return front->_next->data;
    }
    
    void queueRecord::enQueue(ElementType e){
        Node* newNode = new Node(e,NULL);
        rear->_next =  newNode;
        rear = rear->_next;
        size++;
    }
    
    void queueRecord::deQueue(){
        Node* dele = front->_next;
        front->_next = dele->_next;
        free(dele);
        size--;
    }
    int main(){}

    展开全文
  • 普通队列与循环队列链表实现单队列实现循环链表 单队列实现 队列的定义就不赘述了,直接上代码把。为了方便使用了无头的链表。插入方式为尾插法。 #include <stdio.h> #include <stdlib.h> #include &...

    普通队列与循环队列的链表实现

    单队列实现

    队列的定义就不赘述了,直接上代码把。为了方便使用了无头的链表。插入方式为尾插法。

    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    typedef struct node
    {
    	int data;
    	struct node* next;
    }List;
    
    typedef struct
    {
    	int rear;
    	int front;
    	List* list;
    }Queue;
    
    void Queue_init(Queue* Q)
    {
    	Q->front = 0;
    	Q->rear = 0;
    	Q->list = NULL;
    }
    
    //很简单的尾插法,使用了无头的链表
    void __Queue_enQ(Queue* Q, int num)
    {
    	if (Q->list == NULL)
    	{
    		Q->front++;
    		Q->list = (List*)malloc(sizeof(List));
    		Q->list->next = NULL;
    		Q->list->data = num;
    	}
    	else
    	{
    		Queue* temp = Q;
    		List* p = temp->list;
    		temp->front++;
    
    		List* new_node = (List*)malloc(sizeof(List));
    
    		while (p->next != NULL)
    		{
    			p = p->next;
    		}
    
    		new_node->data = num;
    		new_node->next = NULL;
    		p->next = new_node;
    	}
    }
    
    int __Queue_DeQ(Queue* Q)
    {
    	if (Q == NULL)
    	{
    		printf("Q is empty\n");
    		assert(0);
    	}
    	else if(Q->rear == Q->front)
    	{
    		printf("Q is empty\n");
    		assert(0);
    	}
    	else
    	{
    		Q->rear++;
    		int data = Q->list->data;
    		Q->list = Q->list->next;//将第一个节点指向下一个
    		return data;
    	}
    }
    
    void __Print_Q(Queue* Q)
    {
    	if (Q == NULL)
    	{
    		printf("Q is empty\n");
    		assert(0);
    	}
    	else if (Q->rear == Q->front)
    	{
    		printf("Q is empty\n");
    		assert(0);
    	}
    	else
    	{
    		List* temp = Q->list;
    		while (temp != NULL)
    		{
    			printf("%d ", temp->data);
    			temp = temp->next;
    		}
    		printf("\n");
    	}
    }
    
    
    int main()
    {
    	Queue* new_Q = (Queue*)malloc(sizeof(Queue));
    	Queue_init(new_Q);
    
    	for (int i = 0; i < 10; i++)
    	{
    		//new_Q->list = __Queue_enQ(new_Q, i);
    		__Queue_enQ(new_Q, i);
    	}
    	
    	printf("%d ", __Queue_DeQ(new_Q));
    	printf("%d ", __Queue_DeQ(new_Q));
    	printf("%d ", __Queue_DeQ(new_Q));
    	printf("%d ", __Queue_DeQ(new_Q));
    	printf("%d ", __Queue_DeQ(new_Q));
    	printf("%d ", __Queue_DeQ(new_Q));
    	printf("\n");
    
    	__Print_Q(new_Q);
    	
    
    }
    

    循环队列

    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    typedef struct node
    {
    	int data;
    	struct node* next;
    }List;
    
    typedef struct
    {
    	int rear;
    	int front;
    	List* list;
    }Queue;
    
    void Queue_init(Queue* Q)
    {
    	Q->front = 0;
    	Q->rear = 0;
    	Q->list = NULL;
    }
    
    //很简单的尾插法,使用了无头的链表
    void __Queue_enQ(Queue* Q, int num)
    {
    	if (Q->list == NULL)
    	{
    		Q->front++;
    		Q->list = (List*)malloc(sizeof(List));
    		Q->list->next = Q->list;
    		Q->list->data = num;
    	}
    	else
    	{
    		Queue* temp = Q;
    		List* p = temp->list;
    		temp->front++;
    
    		List* new_node = (List*)malloc(sizeof(List));
    
    		while (p->next != temp->list)
    		{
    			p = p->next;
    		}
    
    		new_node->data = num;
    		new_node->next = p->next;
    		p->next = new_node;
    	}
    }
    
    int __Queue_DeQ(Queue* Q)
    {
    	if (Q == NULL)
    	{
    		printf("Q is empty\n");
    		assert(0);
    	}
    	else if (Q->rear == Q->front)
    	{
    		printf("Q is empty\n");
    		assert(0);
    	}
    	else
    	{
    		List* temp = Q->list;
    		while (temp->next != Q->list)
    		{
    			temp = temp->next;
    		}
    		Q->rear++;
    		int data = Q->list->data;
    		Q->list = Q->list->next;//将第一个节点指向下一个
    		temp->next = Q->list;
    		return data;
    	}
    }
    
    void __Print_Q(Queue* Q)
    {
    	if (Q == NULL)
    	{
    		printf("Q is empty\n");
    		assert(0);
    	}
    	else if (Q->rear == Q->front)
    	{
    		printf("Q is empty\n");
    		assert(0);
    	}
    	else
    	{
    		List* temp = Q->list;
    		while(1)
    		{
    			printf("%d ", temp->data);
    			temp = temp->next;
    			if (temp == Q->list)
    				break;
    		}
    		printf("\n");
    	}
    }
    
    int main()
    {
    	Queue* new_Q = (Queue*)malloc(sizeof(Queue));
    	Queue_init(new_Q);
    
    	for (int i = 0; i < 10; i++)
    	{
    		__Queue_enQ(new_Q, i);
    	}
    
    	printf("%d ", __Queue_DeQ(new_Q));
    	printf("%d ", __Queue_DeQ(new_Q));
    	printf("%d ", __Queue_DeQ(new_Q));
    	printf("%d ", __Queue_DeQ(new_Q));
    	printf("%d ", __Queue_DeQ(new_Q));
    	printf("%d ", __Queue_DeQ(new_Q));
    	printf("\n");
    
    	__Print_Q(new_Q);
    
    
    }
    
    展开全文
  • 循环队列的双循环链表结构

    运行环境Visual studio 2017
    运行平台Windows 7

    list.h

    #pragma once
    typedef int Elemtype;
    typedef enum{OK=1,ERROR=0}Status;
    typedef struct coord {
        int x;/*abscissa(横坐标)*/
        int y;/*ordinate(纵坐标)*/
    }Coord;
    enum Direction{up = 1,down ,left ,right  };
    
    
    typedef struct elements {
        Coord coord;/*坐标*/
        enum Direction direction;/*下一步的方向*/
    };
    typedef struct list
    {
        Elemtype data;
        struct list* prev;
        struct list* next;
    }List, *Ptrlist;
    
    typedef struct queue
    {
        Ptrlist  front;
        Ptrlist  tail;
        int cursize;
    }Queue;
    
    Status Initqueue(Queue &Lq);
    Status Clear(Queue &Lq);
    Status Destroy(Queue &Lq);
    bool Queueempty(Queue &Lq);
    int Queuelength(Queue &Lq);
    Status Getfront(Queue &Lq,Elemtype &x);
    Status Gettail(Queue &Lq,Elemtype &x);
    Status push_front(Queue &Lq, Elemtype x);
    Status push_tail(Queue &Lq, Elemtype x);
    void Showqueue(Queue &Lq);
    
    
    
    

    list.cpp

    #include "list.h"
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <stdbool.h>
    
    void Freenode(Ptrlist p)
    {
        free(p);
        p = NULL;
    }
    Ptrlist Buynode()
    {
        Ptrlist s = (Ptrlist)malloc(sizeof(List));
        if (s == NULL) exit(0);
    
        memset(s, 0, sizeof(List));
        return s;
    }
    Status Initqueue(Queue &Lq)
    {
        Lq.cursize = 0;
    
        Lq.tail = NULL;
        Lq.front = Lq.tail;
    
    
        return OK;
    }
    Status Clear(Queue &Lq)
    {
        while (Lq.front->next != Lq.front->prev)
        {
            Ptrlist p = Lq.front;
            Freenode(p);
            Lq.front = Lq.front->next;
        }
        Ptrlist q = Lq.front;
        Freenode(q);
        Lq.front = Lq.tail = NULL;
        Lq.cursize = 0;
        return OK;
    
    }
    Status Destroy(Queue &Lq)
    {
        Clear(Lq);
        Freenode(Lq.front);
        Freenode(Lq.tail);
        return OK;
    }
    bool Queueempty(Queue &Lq)
    {
        return (Lq.cursize == 0);
    }
    int Queuelength(Queue &Lq)
    {
        return Lq.cursize;
    }
    Status Getfront(Queue &Lq,Elemtype &x)
    {
        if (Queueempty(Lq))
        {
            return ERROR;
        }
        else
        {
            x = Lq.front->data;
            return OK;
        }
    }
    Status Gettail(Queue &Lq,Elemtype &x)
    {
        if (Queueempty(Lq))
        {
            return ERROR;
        }
        else
        {
            x = Lq.tail->data;
            return OK;
        }
    }
    Status push_front(Queue &Lq, Elemtype x)
    {
        Ptrlist s = Buynode();
        if (Lq.front == NULL)
        {
            Lq.front = s;
            Lq.tail = Lq.front;
            Lq.tail->next = Lq.front;
            Lq.tail->prev = Lq.front;
            Lq.front->next = Lq.tail;
            Lq.front->prev = Lq.tail;
            s->data = x;
            Lq.cursize++;
            return OK;
        }
        s->prev = Lq.front->prev;
        Lq.front->prev->next = s;
        Lq.front->prev = s;
        s->next = Lq.front;
    
        s->data = x;
        Lq.cursize++;
        Lq.front = s;
        return OK;
    }
    Status push_tail(Queue &Lq, Elemtype x)
    {
        Ptrlist s = Buynode();
        if (Lq.tail == NULL)
        {
            Lq.tail = s;
            Lq.front = Lq.tail;
            Lq.tail->next = Lq.front;
            Lq.tail->prev = Lq.front;
            Lq.front->next = Lq.tail;
            Lq.front->prev = Lq.tail;
            s->data = x;
            Lq.cursize++;
            return OK;
        }
        s->prev = Lq.front->prev;
        Lq.front->prev->next = s;
        Lq.front->prev = s;
        s->next = Lq.front;
    
        s->data = x;
        Lq.cursize++;
        Lq.tail = s;
        return OK;
    }
    Status Pop_front(Queue &Lq)
    {
        if (Queueempty(Lq))
        {
            return ERROR;
        }
        Ptrlist p = Lq.front;
        Lq.front->next->prev = Lq.front->prev;
        Lq.front->prev->next = Lq.front->next;
        Lq.front = Lq.front->next;
        Freenode(p);
        Lq.cursize--;
        return OK;
    }
    Status Pop_tail(Queue &Lq)
    {
        if (Queueempty(Lq))
        {
            return ERROR;
        }
        Ptrlist p = Lq.tail;
        Lq.tail->prev->next = Lq.tail->next;
        Lq.tail->next->prev = Lq.tail->prev;
        Lq.tail = Lq.tail->prev;
        Freenode(p);
        Lq.cursize--;
        return OK;
    }
    
    void Showqueue(Queue &Lq)
    {
        Ptrlist p = Lq.front;
        while (p->next != Lq.tail)
        {
            printf("%d,", p->data);
        }
        printf("\n");
    }
    

    主函数(对于函数模块可以自己添加进去进行测试)
    main.c

    #include "list.h"
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    
    int main()
    {
        Queue myq;
        Initqueue(myq);
        Elemtype data[3] = { 11,22,33 };
        Elemtype out[3] ;
        push_front(myq, data[0]);
        push_tail(myq, data[1]);
        push_front(myq, data[2]);
        Status Getfront(myq,out[0]);
         Status Gettail(myq,out[1]);
         Status Getfront(myq,out[2]);
    
        return 0;
    }
    
    展开全文
  • 循环链表循环队列

    万次阅读 2017-03-07 14:05:38
    单向循环链表 和普通的链表结构不同,单向循环链表的最后一个节点的指针指向了头结点,也就是和Head指针有相同的引用 和普通链表相比,循环链表不需要头指针,能够从任意位置实现链表遍历 双向循环...

    单向循环链表

    和普通的链表结构不同,单向循环链表的最后一个节点的指针指向了头结点,也就是和Head指针有相同的引用



    和普通链表相比,循环链表不需要头指针,能够从任意位置实现链表遍历


    双向循环链表

    和单向链表相比,双向链表多了一个指向上一个节点的前向指针



    相比于单向链表,双向循环链表的遍历更加灵活,但缺点是,进行插入和删除操作需要修改更多的指针


    队列的“假溢出”


    如上图所示,front和rear分别是队列的头、尾指针,在出入队列的过程中会出现一种现象:尾指针指向了对垒的尾部,也就是达到了maxSize,但这是,头指针并没有指向对头,这样就造成的存储空间的浪费,也会导致队列无法继续实现入队、出队操作。因此,提出了循环队列。

    优先级队列

    和普通的队列相比,优先级队列在出栈是是按照优先级进行的,也就是每次选取优先级最高的元素出列,这在计算机的任务调度中有很大的用处

        private Object element;   //数据域
        private int priority;     //用整型数字表示对雷元素的优先级
    
        public Element(Object element, int priority) {
            this.element = element;
            this.priority = priority;
        }
    public Object delete() {
            if(isEmpty()){                //判断队列是否为空
                System.out.println("队列为空");
            }
    
                                         //找优先级最低的元素,默认为队头元素
            Element MIN = queue[0];
            int index = 0;
            for (int i = 0; i < count; i++) {
                if(queue[i].getPriority() < MIN.getPriority()){
                    MIN = queue[i];
                    index = i;
                }
            }
    
                                           //出队,后面的元素向前移
            for (int i = index + 1; i < count; i++) {
                queue[i -1] = queue[i];
                }
            rear--;
            count--;
            return MIN;
        }


    循环队列


    附上循环对垒的代码:

    public class ImplQueue implements CircularQueue{
    
        static final  int defauleSize = 10;
        int front,rear,count,maxSize;
        Object[] queue;
    
    
        public static void main(String[] args) {
            ImplQueue circleQueue = new ImplQueue();
            circleQueue.append(10);
            circleQueue.append("d");
            circleQueue.append("sss");
            circleQueue.append(1);
            System.out.println(circleQueue.isEmpty());
            System.out.println(circleQueue.getFront());
            while (!circleQueue.isEmpty()){
                System.out.println(circleQueue.delete());
            }
        }
    
        //默认队列长度
        public ImplQueue() {
            rear = 0;
            front = 0;
            count = 0;
            maxSize = defauleSize;
            queue = new Object[defauleSize];
        }
    
        //自定义队列那长度
        public ImplQueue(int maxSize) {
            this.maxSize = maxSize;
            rear = 0;
            front = 0;
            count = 0;
            queue = new Object[maxSize];
        }
    
        @Override
        public void append(Object obj) {
            //判断队列是否为满
            if(front == rear && count > 0) {
                System.out.println("队列已满,无法插入");
            }else {
                queue[rear] = obj;
                rear = (rear + 1) % maxSize;
                count++;
            }
        }
    
        @Override
        public Object delete() {
            Object obj = null;
            //判断队列是否为空
            if(isEmpty()){
                System.out.println("队列为空,无法删除");
            }else {
                obj = queue[front];
                front = (front +1) % maxSize;
                count--;
            }
            return obj;
        }
    
        @Override
        public Object getFront() {
            Object obj = null;
            if(isEmpty()){
                System.out.println("队列为空");
            }else {
                obj = queue[front];
            }
            return obj;
        }
    
        @Override
        public boolean isEmpty() {
            return count == 0;
        }
    }          
    展开全文
  • 链表实现的队列 /*********************************************** *file : queue_link.h ************************************************/ #ifndef QUEUE_LINK_H_ #define QUEUE_LINK_H_ #include ...
  • 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),请完成下列任务: 1: 队列初始化,成功返回真,否则返回假:bool init_queue(LinkQueue *LQ); 2: 入队列,成功返回真,...
  • import java.util.Random; public class QueueTest { private static double testStack(Queue<Integer> queue, int opCount) { long startTime = System.nanoTime(); Random random = new Random();...
  • VC 运用循环队列链表技巧开发的贪吃蛇游戏,游戏的玩法和其它的贪食蛇游戏没什么区别,但是编程思路和运用的技巧却与其它的同类游戏大相径庭,本游戏运用了循环队列链表的技巧而编写,操作方法:按键盘上的W/A/S...
  • 当我们使用数组的时候创建循环队列是为了节省存储空间,而来到链表中时,每一个节点都是动态申请和释放的,不会造成空间的浪费,所以不需要采用循环队列了。第二,大家在很多书上看到的是使用单链表实现队列,我这里...
  • 循环队列链表实现

    2013-06-09 18:10:41
    循环队列链表实现).cpp : 定义控制台应用程序的入口点。 //   #include "stdafx.h" #include using namespace std;   struct d_Queue {  d_Queue *next,*prior;  int data; };   d_Queue *initQueue()//初始...
  • 链表队列和循环队列的基本操作 实验内容 完成以下任务: 数组7 5 3 9 2 4 全部入队列 进行三次出队列 将15 18入队列 输出从队头到的队尾所有元素 分别用链队列、循环队列(最大长度为7 队列的操作比较简单 链表队列...
  • 下面是关于队列的一些基本操作:
  • 循环队列-链表实现

    千次阅读 2014-05-16 23:05:23
    //插入元素e为队列的新队尾元素 int EnQueue(LinkQueue *Q,int e) {  QueuePtr p;  p=(QueuePtr)malloc(sizeof(QNode));  p->data=e;  p->next=NULL;  Q->rear->next=p;  Q->rear=p; ...
  • #include using namespace std; typedef struct node{ int data;... ///此时循环队列里的元素是 3 2 1 3 cout(Q); cout(Q); //cout(Q); cout(Q); ///应该输出的是 3 2 3 return 0; }
  • 系列文章参考资料为《大话数据结构》,源码为个人私有,未经允许不得转载将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾详解的单链表就是单循环链表,简称循环链表...
  • 循环队列: class XhDl(): def __init__(self,num): self.tou=0 self.wei=0 self.queue=[None]*num self.size=num def rudui(self): if (self.wei+1)%self.size==self.t...
  • Java实现队列的两种方式(链表,循环数组)数组实现循环队列1、需要一个theSize变量,来判断队列是否填满了数组,或者判断队列是否为空代码如下public class cycleQueue { private int front ;//队头 private int ...
  • 数据结构篇:循环队列的C语言实现及其基本操作 #简述 循环队列在有些嵌入式软件开发中使用频繁,同时队列是非常重要的数据结构。 #include<stdio.h> #include<stdlib.h> #define Maxsize 20 //队列达到...
  • 循环队列链表表示

    千次阅读 2008-09-05 10:30:00
    队列时,新结点成为队列的第一个结点,既是对头也是队尾   if (front == NULL ) return  false ;  }   else  {  rear -> link = new  LinkNode < T > (x); // 非空时在链尾追加新的结点并更新队尾指针   ...
  • 用带头结点的循环链表表示队列,并设置一个尾指针指向队尾元素。 不设置投指针。编写置队空,判断队空,出队,入队等算法,  /* 链队结构定义 */ //定义节点类型 typedef struct QNode{ int data;...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,682
精华内容 1,072
关键字:

循环队列链表