赞
踩
目录
队列是一种数据结构,它遵循先进先出(FIFO)的原则。这意味着最先进入队列的元素将最先被处理或移除,而最后进入队列的元素将最后被处理或移除。
队列的基本操作包括入队(向队列尾部添加元素)和出队(从队列头部移除元素)。
队列是一种具有先进先出(FIFO)特性的数据结构。它类似于在超市排队购物时的情景,新来的人只能排在队尾,而离开队伍的人是从队首开始。在队列中,元素按照插入的顺序排列,并且只能在队尾添加新元素,而只能在队首删除元素。这使得队列成为处理按照先后顺序排列的数据的理想选择。
队列有两个主要操作:入队(enqueue)和出队(dequeue)。入队操作将元素添加到队尾,出队操作将队首的元素删除并返回。除此之外,队列还可以支持其他操作,如获取队首元素、判断队列是否为空等。
队列在计算机科学中广泛应用,例如任务调度、消息传递、缓冲区管理等领域。在编程中,队列通常使用数组或链表来实现。
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数 组头上出数据,效率会比较低。
使用链表结构,要返回多个参数,所以使用结构体封装。
- typedef int QDataType;
-
- typedef struct QueueNode
- {
- struct QueueNode* next;
- QDataType data;
- }QNode;
-
- typedef struct Queue
- {
- QNode* head;
- QNode* tail;
- int size;
- }Queue;
- void QueueInit(Queue* pq)
- {
- assert(pq);
-
- pq->head = pq->tail = NULL;
- pq->size = 0;
- }
- void QueueDestory(Queue* pq)
- {
- assert(pq);
- QNode* cur = pq->head;
- while (cur)
- {
- QNode* next = cur->next;
- free(cur);
- cur = next;
- }
- pq->head = pq->tail = NULL;
- pq->size = 0;
- }
- void QueuePush(Queue* pq, QDataType x)
- {
- QNode* newnode = (QNode*)malloc(sizeof(QNode));
- if (newnode == NULL)
- {
- perror("malloc fail");
- return;
- }
- newnode->data = x;
- newnode->next = NULL;
-
- //没有结点插入时
- if (pq->head == NULL)
- {
- assert(pq->tail == NULL);
-
- pq->head = pq->tail = newnode;
- }
- else
- {
- pq->tail->next = newnode;
- pq->tail = newnode;
- }
- pq->size++;
- }
- void QueuePop(Queue* pq)
- {
- assert(pq && pq->head);
-
- if (pq->head->next == NULL)
- {
- free(pq->head);
- pq->head = pq->tail = NULL;
- }
- else
- {
- QNode* next = pq->head->next;
- free(pq->head);
- pq->head = next;
- }
- pq->size--;
- }
- int QueueSize(Queue* pq)
- {
- assert(pq);
-
- return pq->size;
- }
- bool QueueEmpty(Queue* pq)
- {
- assert(pq);
-
- return pq->size == 0;
- }
- QDataType QueueFront(Queue* pq)
- {
- assert(pq);
- assert(!QueueEmpty(pq));
-
- return pq->head->data;
- }
- QDataType QueueBack(Queue* pq)
- {
- assert(pq);
- assert(!QueueEmpty(pq));
-
- return pq->tail->data;
- }
队列和栈的区别:
在实际应用中,队列和栈经常结合使用,例如使用栈来实现队列,或者使用队列来实现栈。它们是解决问题的重要工具,根据具体的场景和需求选择合适的数据结构是很重要的。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。