队列的基本操作！

浅浅的花香味﹌ 2022-04-11 08:08 329阅读 0赞

1.链式队列

//队列结点结构体

typedef struct QNode

\{ QElemType data;

QNode \*next;

\}\*Queueptr;

\------------------------------

//指向结点的指针

struct LinkQueue

\{  Queueptr front,rear;

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  **<STRONG><SPAN style="COLOR: \#000066; FONT-SIZE: 18px">void InitQueue(LinkQueue &Q)  **
2.  **\{ // 构造一个空队列Q   **
3.  **  if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))  **
4.  **    exit(OVERFLOW);  **
5.  **  Q.front->next=NULL;  **
6.  **\}  **
7.  **  **
8.  **void DestroyQueue(LinkQueue &Q)  **
9.  **\{ // 销毁队列Q(无论空否均可)   **
10. **  while(Q.front)  **
11. **  \{  **
12. **    Q.rear=Q.front->next;  **
13. **    free(Q.front);  **
14. **    Q.front=Q.rear;//释放一块内存要做两点：1.释放指向它的指针。2.将该指针指向空   **
15. **  \}  **
16. **\}  **
17. **  **
18. **void ClearQueue(LinkQueue &Q)  **
19. **\{ // 将Q清为空队列   **
20. **  QueuePtr p,q;  **
21. **  Q.rear=Q.front;  **
22. **  p=Q.front->next;  **
23. **  Q.front->next=NULL;//只留下头结点   **
24. **  while(p)  **
25. **  \{  **
26. **    q=p;  **
27. **    p=p->next;  **
28. **    free(q);  **
29. **  \}  **
30. **\}  **
31. **  **
32. **Status QueueEmpty(LinkQueue Q)  **
33. **\{ // 若Q为空队列，则返回TRUE，否则返回FALSE   **
34. **  if(Q.front->next==NULL)//注意不要把链式队列的判空条件与循环队列混淆   **
35. **    return TRUE;  **
36. **  else  **
37. **    return FALSE;  **
38. **\}  **
39. **  **
40. **int QueueLength(LinkQueue Q)  **
41. **\{ // 求队列的长度   **
42. **  int i=0;  **
43. **  QueuePtr p;  **
44. **  p=Q.front;  **
45. **  while(Q.rear!=p)  **
46. **  \{  **
47. **    i++;  **
48. **    p=p->next;  **
49. **  \}  **
50. **  return i;  **
51. **\}  **
52. **  **
53. **Status GetHead(LinkQueue Q,QElemType &e)  **
54. **\{ // 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR   **
55. **  QueuePtr p;  **
56. **  if(Q.front==Q.rear)  **
57. **    return ERROR;  **
58. **  p=Q.front->next;  **
59. **  e=p->data;  **
60. **  return OK;  **
61. **\}  **
62. **  **
63. **void EnQueue(LinkQueue &Q,QElemType e)  **
64. **\{ // 插入元素e为Q的新的队尾元素   **
65. **  QueuePtr p;  **
66. **  if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败   **
67. **    exit(OVERFLOW);  **
68. **  p->data=e;  **
69. **  p->next=NULL;  **
70. **  Q.rear->next=p;  **
71. **  Q.rear=p;  **
72. **\}  **
73. **  **
74. **Status DeQueue(LinkQueue &Q,QElemType &e)  **
75. **\{ // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR   **
76. **  QueuePtr p;  **
77. **  if(Q.front==Q.rear)  **
78. **    return ERROR;  **
79. **  p=Q.front->next;  **
80. **  e=p->data;  **
81. **  Q.front->next=p->next;  **
82. **  if(Q.rear==p)  **
83. **    Q.rear=Q.front;//如果只有一个节点，那么删除这个节点后rear指针也就丢了，需重新赋值   **
84. **  free(p);  **
85. **  return OK;  **
86. **\}  **
87. **  **
88. **void QueueTraverse(LinkQueue Q,void(\*vi)(QElemType))  **
89. **\{ // 从队头到队尾依次对队列Q中每个元素调用函数vi()   **
90. **  QueuePtr p;  **
91. **  p=Q.front->next;  **
92. **  while(p)  **
93. **  \{  **
94. **    vi(p->data);  **
95. **    p=p->next;  **
96. **  \}  **
97. **  printf("\\n");  **
98. **\}</SPAN></STRONG**>

void InitQueue(LinkQueue &Q) { // 构造一个空队列Q if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)))) exit(OVERFLOW); Q.front->next=NULL; } void DestroyQueue(LinkQueue &Q) { // 销毁队列Q(无论空否均可) while(Q.front) { Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear;//释放一块内存要做两点：1.释放指向它的指针。2.将该指针指向空 } } void ClearQueue(LinkQueue &Q) { // 将Q清为空队列 QueuePtr p,q; Q.rear=Q.front; p=Q.front->next; Q.front->next=NULL;//只留下头结点 while(p) { q=p; p=p->next; free(q); } } Status QueueEmpty(LinkQueue Q) { // 若Q为空队列，则返回TRUE，否则返回FALSE if(Q.front->next==NULL)//注意不要把链式队列的判空条件与循环队列混淆 return TRUE; else return FALSE; } int QueueLength(LinkQueue Q) { // 求队列的长度 int i=0; QueuePtr p; p=Q.front; while(Q.rear!=p) { i++; p=p->next; } return i; } Status GetHead(LinkQueue Q,QElemType &e) { // 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR QueuePtr p; if(Q.front==Q.rear) return ERROR; p=Q.front->next; e=p->data; return OK; } void EnQueue(LinkQueue &Q,QElemType e) { // 插入元素e为Q的新的队尾元素 QueuePtr p; if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败 exit(OVERFLOW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; } Status DeQueue(LinkQueue &Q,QElemType &e) { // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR QueuePtr p; if(Q.front==Q.rear) return ERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front;//如果只有一个节点，那么删除这个节点后rear指针也就丢了，需重新赋值 free(p); return OK; } void QueueTraverse(LinkQueue Q,void(*vi)(QElemType)) { // 从队头到队尾依次对队列Q中每个元素调用函数vi() QueuePtr p; p=Q.front->next; while(p) { vi(p->data); p=p->next; } printf("\n"); }

2.顺序队列---循环队列

**性质如下:**

**1.头指针指向对头元素，尾指针指向队尾的下一个位置。(这里的指针都是为指针，实际是数组序号)**

**2.为了区分队满与对空，则定义一个存储空间为MAX\_QSIZE大小的队列只允许存放MAX\_QSIZE-1个数据。**

**3.判空条件为:if(Q.front ==Q.rear) return true;**

**   判满条件为:if((Q.rear+1)%MAX\_QSIZE==Q.front) return true;**

**4.循环队列的长度为:(Q.read-Q.front+MAX\_SIZE)%MAX\_QSIZE**

**5.当删除对头元素或者在对尾插入元素时指针均需向后移动。操作为:**

**    Q.rear=(Q.rear+1)%MAX\_QSIZE;**

**    Q.front=(Q.front+1)%MAX\_QSIZE;**

**结构体定义如下:**

**struct SqQueue**

**\{QElemType \*base;//指向开辟的空间的首地址**

**  int front;**

**  int rear;**

**\}**

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  **void InitQueue(SqQueue &Q)  **
2.  ** \{ // 构造一个空队列Q   **
3.  **   Q.base=(QElemType \*)malloc(MAX\_QSIZE\*sizeof(QElemType));  **
4.  **   if(!Q.base) // 存储分配失败   **
5.  **     exit(OVERFLOW);  **
6.  **   Q.front=Q.rear=0;  **
7.  ** \}  **
8.  **  **
9.  ** void DestroyQueue(SqQueue &Q)  **
10. ** \{ // 销毁队列Q，Q不再存在   **
11. **   if(Q.base)  **
12. **     free(Q.base);  **
13. **   Q.base=NULL;  **
14. **   Q.front=Q.rear=0;  **
15. ** \}  **
16. **  **
17. ** void ClearQueue(SqQueue &Q)  **
18. ** \{ // 将Q清为空队列   **
19. **   Q.front=Q.rear=0;  **
20. ** \}  **
21. **  **
22. ** Status QueueEmpty(SqQueue Q)  **
23. ** \{ // 若队列Q为空队列，则返回TRUE；否则返回FALSE   **
24. **   if(Q.front==Q.rear) // 队列空的标志   **
25. **     return TRUE;  **
26. **   else  **
27. **     return FALSE;  **
28. ** \}  **
29. **  **
30. ** int QueueLength(SqQueue Q)  **
31. ** \{ // 返回Q的元素个数，即队列的长度   **
32. **   return(Q.rear-Q.front+MAX\_QSIZE)%MAX\_QSIZE;  **
33. ** \}  **
34. **  **
35. ** Status GetHead(SqQueue Q,QElemType &e)  **
36. ** \{ // 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR   **
37. **   if(Q.front==Q.rear) // 队列空   **
38. **     return ERROR;  **
39. **   e=Q.base\[Q.front\];//等价于e=\*(Q.base+Q.front)   **
40. **   return OK;  **
41. ** \}  **
42. **  **
43. ** Status EnQueue(SqQueue &Q,QElemType e)  **
44. ** \{ // 插入元素e为Q的新的队尾元素   **
45. **   if((Q.rear+1)%MAX\_QSIZE==Q.front) // 队列满   **
46. **     return ERROR;  **
47. **   Q.base\[Q.rear\]=e;//等价于\*(Q.base+Q.rear)=e   **
48. **   Q.rear=(Q.rear+1)%MAX\_QSIZE;  **
49. **   return OK;  **
50. ** \}  **
51. **  **
52. ** Status DeQueue(SqQueue &Q,QElemType &e)  **
53. ** \{ // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR   **
54. **   if(Q.front==Q.rear) // 队列空   **
55. **     return ERROR;  **
56. **   e=Q.base\[Q.front\];  **
57. **   Q.front=(Q.front+1)%MAX\_QSIZE;  **
58. **   return OK;  **
59. ** \}  **
60. **  **
61. ** void QueueTraverse(SqQueue Q,void(\*vi)(QElemType))  **
62. ** \{ // 从队头到队尾依次对队列Q中每个元素调用函数vi()   **
63. **   int i;  **
64. **   i=Q.front;  **
65. **   while(i!=Q.rear)  **
66. **   \{  **
67. **     vi(Q.base\[i\]);  **
68. **     i=(i+1)%MAX\_QSIZE;  **
69. **   \}  **
70. **   printf("\\n");  **
71. ** \}  **

[view plain]: http://blog.csdn.net/kkkkkxiaofei/article/details/8348823#