队列的链式存储结构示意图
时间: 2023-12-07 07:37:01 浏览: 43
以下是队列的链式存储结构示意图:
```
front指针指向队头,rear指针指向队尾
+------+ +------+ +------+ +------+ +------+
| data |-->| data |-->| data |-->| data |-->| data |-->NULL
+------+ +------+ +------+ +------+ +------+
front rear
```
其中,每个节点包含一个数据域和一个指针域,指针域指向下一个节点。队列的头指针front指向队头节点,尾指针rear指向队尾节点,队列的长度可以通过计算队列中节点的个数得到。
相关问题
队列的链式存储结构的实现
队列的链式存储结构实际上就是线性表的单链表,只不过是能尾进头出,简称为链队列。为了操作上的方便,将队头指针指向链队列的头结点,而队尾指针指向终端结点。空队列时,front和rear都指向头结点。链队列的结构可以用以下代码表示:
```
typedef int QElemType; /* QElemType类型根据实际情况而定,这里假设为int */
typedef struct QNode /* 结点结构 */
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct /* 队列的链表结构 */
{
QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
```
其中,QNode为队列的结点结构体,QueuePtr为指向QNode的指针类型,LinkQueue为队列的链表结构体,包含队头指针front和队尾指针rear。
队列的链式存储结构的入队操作可以用以下代码表示:
```
/* 链式队列的入队操作 */
Status EnQueue(LinkQueue *Q,QElemType e)
{
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
if(!s) /* 存储分配失败 */
exit(OVERFLOW);
s->data = e;
s->next = NULL;
Q->rear->next = s; /* 把拥有元素e新结点s赋值给原队尾结点的后继 */
Q->rear = s; /* 把当前的s设置为队尾结点,rear指向s */
return OK;
}
```
其中,EnQueue为入队操作函数,Q为链队列指针,e为要入队的元素。该函数首先创建一个新结点s,将要入队的元素e赋值给s的data域,将s的next指针置为NULL。然后将s赋值给原队尾结点的后继,将rear指向s,完成入队操作。
链式存储结构实现队列
链式存储结构实现队列,即使用链表来存储队列中的元素。队列的头部和尾部分别对应链表的头结点和尾结点,入队操作相当于在链表尾部插入一个新结点,出队操作相当于删除链表头部的结点。下面是链式存储结构实现队列的具体实现方法:
1.定义队列结点类
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
```
2.定义队列类
```python
class Queue:
def __init__(self):
self.head = None
self.tail = None
def is_empty(self):
return self.head is None
def enqueue(self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
def dequeue(self):
if self.is_empty():
raise Exception("Queue is empty")
else:
data = self.head.data
self.head = self.head.next
if self.head is None:
self.tail = None
return data
def size(self):
count = 0
current = self.head
while current is not None:
count += 1
current = current.next
return count
```
3.测试代码
```python
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue()) # 输出:1
print(q.dequeue()) # 输出:2
print(q.size()) # 输出:1
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)