精华内容
下载资源
问答
  • 队列的链表实现

    2018-05-11 00:12:29
    前面我们看了队列的数组实现,本文来看看用链表实现队列的方法。 链式队列的出现:存储队列元素的数组大小是固定的,另外,队列的数组实现需要...而队列的链表实现简化了 数组实现的许多特殊情况,并且动态分配...

    前面我们看了队列的数组实现,本文来看看用链表实现队列的方法。

    链式队列的出现:存储队列元素的数组大小是固定的,另外,队列的数组实现需要用特殊的方式处理数组(保留一个数组元素用
    	于判断数组是否已满),以及索引front和rear(计算front/rear时用(front/rear + 1 )% maxSize 操作)。而队列
    	的链表实现简化了数组实现的许多特殊情况,并且动态分配内存,所以队列永远也不会满。
    


    看以下程序:

    /** 链表类 */
    class Link{
    
    	/** 结点类,用于初始化结点 */
        class Entry{
            int data;
            Entry next;
            public Entry(){
                data = -1;
                next = null;
            }
            public Entry(int data){
                this.data = data;
                next = null;
            }
        }
    
    	/** 定义头尾索引 */
        public Entry front = null;
        public Entry rear = null;
        public int usedSize = 0;
    
    	/** 判断队列是否为空 */
        public boolean isEmpty(){
    	    return usedSize == 0;
        }
    
    	/** 插入元素 */
        public void insetTail(int data) {
    	    // 若此时队列为空,则直接插入,头尾索引指向该结点
            if (isEmpty()) {
                rear = new Entry(data);
                front = rear;
                // 若队列不为空则尾索引后移指向新结点
            } else {
                rear.next = new Entry(data);
                rear = rear.next;
            }
            // 已用长度每次加1
            usedSize++;
        }
    
    	/** 数据出队列操作 */
        public void pop(){
    		// 若队列为空则直接结束该操作
            if(isEmpty()){
                return;
            }
            // 若不为空则头索引指向第二个结点
            Entry cur = front;
            front = front.next;
            // 第一个结点置为null,便于垃圾回收
            cur.next = null;
            // 已用长度每次减1
            usedSize--;
        }
    
    	/** 获取队列头元素操作 */
        public int getTop(){
    	    // 若队列为空则返回-1
            if (isEmpty()){
                return -1;
            }
            // 若不为空则返回头索引对应的结点数据
            return front.data;
        }
    
    	/** 队列元素的遍历输出 */
        public void print(){
            Entry cur = front;
            while (cur != null){
                System.out.print(cur.data + " ");
                cur = cur.next;
            }
            System.out.println();
        }
    }
    

    用一个例子来验证以上程序是否正确:

    public class LinkQueue {
        public static void main(String[] args){
    	    // 动态制作一个链式队列
            Link link = new Link();
            for (int x = 0; x < 5; x++){
            link.insetTail(x);
            }
            
            System.out.print("队列里的元素是:");
            link.print();
            System.out.println("队列头元素是 :"+ link.getTop());
            System.out.println("队列长度是 :" + link.usedSize);
            System.out.println("==================" );
            
            link.pop();
            System.out.print("执行一次出队操作后队列里的元素是:");
            link.print();
            System.out.println("执行一次出队操作后队列头元素是 :"+ link.getTop());
            System.out.println("执行一次出队操作后队列长度是 :" + link.usedSize);
        }
    }
    

    以上程序的输出结果是:

    		队列里的元素是:0 1 2 3 4 
    		队列头元素是 :0
    		队列长度是 :5
    		==================
    		执行一次出队操作后队列里的元素是:1 2 3 4 
    		执行一次出队操作后队列头元素是 :1
    		执行一次出队操作后队列长度是 :4
    
    展开全文
  • 数据结构——队列的链表实现

    数据结构——队列的链表实现

    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct Node//定义节点
    {
    	int Element;
    	struct Node* Next;
    }Node;
    
    typedef struct Queue//定义队列
    {
    	Node* Front;//队头指针
    	Node* Rear;//队尾指针
    }Queue;
    
    Queue* CreateQueue()//创建一个空队列
    {
    	Queue* q;
    
    	q = (Queue*)malloc(sizeof(Queue));//给队列分配内存空间
    
    	if (q == NULL)
    		printf("分配内存空间失败!");
    
    	q->Front = NULL;//让队头指针指向空,则该队列为空队列
    
    	return q;
    }
    
    Queue* Enqueue(int X, Queue* q)//Enqueue入队
    {
    	Node* n;//定义一个新节点
    
    	n = (Node*)malloc(sizeof(Node));//分配内存空间
    
    	n->Element = X;//将X存入新节点
    	n->Next = NULL;//新节点的指针指向NULL
    
    	if (q->Front == NULL)//若该队列为空
    	{
    		q->Front = n;
    		q->Rear = n;//让队头指针和队尾指针都指向新节点
    	}
    	else
    	{
    		q->Rear->Next = n;//否则,将队尾指针的下一个指针指向新节点
    		q->Rear = n;//更新队尾指针使其指向新节点(新的队尾)
    	}
    
    	return q;
    }
    
    Queue* Dequeue(Queue* q)//Dequeue出队
    {
    	if (q->Front == NULL)
    		printf("该队列为空!");//判断该队列是否为空
    
    	if (q->Front == q->Rear)//若该队列只有一个元素
    	{
    		q->Front = NULL;
    		q->Rear = NULL;//让该队列的Front和Rear指针都指向空
    	}
    	else//若该队列不只一个元素
    		q->Front = q->Front->Next;//更新队头指针使其指向下一个元素
    
    	return q;
    }
    
    void Display(Queue* q)
    {
    	Node* n;
    
    	n = q->Front;//此处使用一个新指针n指向队头元素,通过改变n来实现队列打印,这样做能保证队头指针Front不被更新,否则在下一次入队判空时会出错
    
    	if(n==NULL)
    		printf("该队列为空!");//判断该队列是否为空
    
    	while (n != NULL)
    	{
    		printf("%d", n->Element);
    		n = n->Next;
    	}
    
    	printf("\n");
    }
    
    int main()
    {
    	Queue* q;
    	int i;
    
    	q = CreateQueue();//创建一个空队列
    
    	for (i = 1; i < 10; i++)
    	{
    		q = Enqueue(i, q);//将1~9依次入队
    		Display(q);//每次入队后打印当前队列中元素
    	}
    
    	q = Dequeue(q);//队头元素1出队
    
    	Display(q);//打印出队后队列中元素
    }
    
    展开全文
  • 数据结构——队列的链表实现 队列:队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端...

    数据结构——队列的链表实现

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

    操作:利用链表的形式,对队列进行初始化,入队,出队,遍历队列。

    #include<stdio.h>
    #include<stdlib.h>
    #define ERROR -1
    #define OK 1
    #define OVERFLOW 0
    typedef int QElemType;
    typedef int Status;
    typedef struct QNode
    {
    	QElemType data;
    	struct QNode *next;
    }QNode,*QueuePtr;
    
    typedef struct
    {
    	QueuePtr front;
    	QueuePtr rear;
    }LinkQueue;
    
    //初始化链队列
    Status InitQueue(LinkQueue &Q)
    {
    	Q.front =Q.rear =(QueuePtr)malloc(sizeof(QNode));
    	if(!Q.front )
    	{
    		exit(OVERFLOW);
    	}
    	Q.front ->next =NULL;
    	return OK;
    }
    
    //入队列
    Status EnterQueue(LinkQueue &Q,QElemType e)
    {
    	QueuePtr p;
    	p=(QueuePtr)malloc(sizeof(QNode));
    	if(!p)
    	{
    		exit(OVERFLOW);
    	}
    	p->data =e;
    	p->next =NULL;
    	Q.rear ->next =p;
    	Q.rear =p;
    	return OK;
    }
    
    //出队列
    Status PopQueue(LinkQueue &Q,QElemType &e)
    {
    	QueuePtr p;
    	if(Q.front ==Q.rear )
    	{
    		printf("队列为空,无法出队列!\n");
    		return ERROR;
    	}
    	p=Q.front ->next ;
    	e=p->data ;
    	Q.front ->next =p->next ;
    	if(Q.rear ==p)
    	{
    		Q.rear =Q.front ;
    	}
    	free(p);
    	return OK;
    }
    
    //遍历队列
    void PrintQueue(LinkQueue &Q)
    {
    	QNode *p;
    	printf("遍历已输入数据的队列:");
        for(p=Q.front->next;p!=NULL;p=p->next)
    	{
    			printf("%d ",p->data);
    	}
    }
    
    int main()
    {
    	LinkQueue Q;
    	int x,n;
    	InitQueue(Q);
    	printf("请输入队列的元素个数:\n");
    	scanf("%d",&n);
    	while(n--!=0)
    	{
    		printf("请输入队列元素:\n");
    		scanf("%d",&x);
    		EnterQueue(Q,x);//入队列
    		PrintQueue(Q);//遍历队列
    		printf("\n");
    	}
    	printf("\n出队列一个元素\n");
    	PopQueue(Q,x);
    	printf("%d\n",x);
    	return 0;
    }
    

    若代码有错误的地方或是其他代码,请各位指教。

    展开全文
  • 优先队列的链表实现

    千次阅读 2016-10-10 20:48:57
    插入时需要按照优先级从高到低排序,一般操作系统任务队列调度会用到 /* 优先队列(链表实现) * front 为队头指针(链表头节点) * rear 为队尾指针 */ #include<stdio.h> #include<stdlib.h> typedef struct...
    插入时需要按照优先级从高到低排序,一般操作系统的任务队列调度会用到  
    
    /* 优先队列(链表实现) 
     * front 为队头指针(链表头节点) 
     * rear 为队尾指针 
     */  
    #include<stdio.h>  
    #include<stdlib.h>  
    
    typedef struct list_t{  
        int _element;  
        int _priority;  
        struct list_t *_next;  
    }list_t;  
    
    /* 要改变一个变量的值,需要传入变量的地址作参数; 
     * 要改变一个指针的值,需要传入该指针的地址作参数(即指针的指针);  
     */  
    void insertPriorQueue(list_t **front, list_t **rear, int value, int priority)  
    {  
        list_t *prev;  
        list_t *curr;  
        curr = (list_t*)malloc(sizeof(list_t));  
        if(curr == NULL) {  
            printf("error: malloc\n");  
            exit(0);  
        }  
        curr->_element = value;  
        curr->_priority = priority;  
        curr->_next = NULL;  
        if(*rear == NULL) { //empty queue: we need make front = rear = NULL  
            *rear = curr;  
            *front = *rear;  
        }   
        else   
        {  
            /* if node to be inserted has highest priority hence should be the first node */  
            if((*front)->_priority < priority) {  
                curr->_next = *front;  
                *front = curr;  
            }  
            /* if node has the lowest priority hence should be inserted the last node */  
            else if ((*rear)->_priority > priority)  
            {  
                (*rear)->_next = curr;  
                *rear = curr;  
            }  
            /* find the proper place to insert */  
            else {  
                prev = *front;  
                while((prev->_next)->_priority >= priority)  
                    prev = prev->_next;  
                curr->_next = prev->_next;  
                prev->_next = curr;  
            }  
    
        }  
    }  
    
    void delPriorQueue(list_t **front, list_t **rear, int *value)  
    {  
        list_t *temp;  
        if((*front == *rear) && (*rear == NULL)) {  
            printf("Queue underflow\n");  
            exit(0);  
        }  
        *value = (*front)->_element;  
        temp = *front;  
        *front = (*front)->_next;  
        if(*rear == temp)  
            *rear = (*rear)->_next;  
        printf("%d(%d)\n", temp->_element, temp->_priority);  
        free(temp);  
    }  
    
    void printPriorQueue(list_t *head)  
    {  
        while(head != NULL) {  
            printf("%d", head->_element);  
            printf("(%d) ", head->_priority);  
            head = head->_next;  
        }  
        putchar('\n');  
    }  
    
    void item()  
    {  
        printf("*************** Welcome to the Queue *************\n");  
        printf("1: Insert one element;\n");  
        printf("2: Delete one element;\n");  
        printf("0: Exit.\n");  
        printf("*************************************************\n");  
        printf("Select your operation: ");  
    }  
    
    main(void)  
    {  
        char item_choice;  
        list_t *front = NULL;  
        list_t *rear = NULL;  
        int n, priority;  
        item();  
        while(1)  
        {  
            item_choice = getchar();  
            switch (item_choice)  
            {  
                case '1':  
                    printf("Insert a element to the queue: ");  
                    scanf("%d %d", &n, &priority);  
                    insertPriorQueue(&front, &rear, n, priority);  
                    printf("\nQueue: ");  
                    printPriorQueue(front);  
                    putchar('\n');  
                    item();  
                    break;  
                case '2':  
                    printf("Get an element from the queue: ");  
                    delPriorQueue(&front, &rear, &n);  
                    //printf("Element: %d\n", n);  
                    printf("Queue: ");  
                    printPriorQueue(front);  
                    putchar('\n');  
                    item();  
                    break;  
                case '0':  
                    printf("Good luck to you!\n");  
                    return 0;  
            }  
        }  
        return;  
    }  
    
    
    展开全文
  • 队列的链表实现 C

    2019-05-02 12:03:41
    使用链表实现队列的时候,就不存在队满的情况了,入队就是在一端加入一个节点,出队就是在另一端删除一个节点。当然队首在链表的首或者尾都无所谓,但是最好在队首,那么入队就是使用的头插法建立链表。 特别注意...
  • 1 链表实现队列的示意图 使用单向无头非循环链表来表示队列,这里对链表进行优化,添加一个尾指针,指向队列的队尾,链表表头则指向队列的队头。 进行入队操作(尾插): 进行出队操作(头删): 2 链表实现队列 ...
  • java队列的链表实现

    千次阅读 2018-11-15 10:30:50
    package Interface; /** * 队列接口 ... * ps:还存在一种 双端队列 即队头和队尾都可以进行插入和删除操作,队头和队尾在这里叫端点 * 以及输入受限双端队列(一端输入和删除,另一端只能删除) ...
  • 队列实现系列(一)——队列的数组实现(Java版)  链表实现队列时,不需要考虑ElementOutOfBoundary问题,因此不需要做成循环队列。 Before:这里实现时,使用的链表不是Java自带的链表,是我自己写的链表,代码见...
  • 为了阅读方便和保持内容的完整性,这部分使用了队列的数组实现(C语言)中的内容 队列是一种允许在一端(队尾,rear)进行插入操作,另一端(队头,front)进行删除操作的数据结构。 插入:在队尾进行,也称为入队 ...
  • 循环队列的链表实现

    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()//初始...
  • 链表实现队列的各种操作
  • 5.2 队列的链表实现

    千次阅读 2013-08-24 18:46:22
    队列操作的链表实现: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 ...
  • 定义背包,队列以及栈基本数据结构, 其中背包支持数据添加以及查询操作,...最基本数据结构有数组以及链表,可以使用基本结构来实现上述数据结构,这里采用链表形式来实现链表数据结构 可以使用链表来...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,800
精华内容 4,320
关键字:

队列的链表实现