คิว (Queue)
คิว (Queue)

คิว (Queue) คือ โครงสร้างข้อมูลจัดเรียงข้อมูลแบบลิเนียร์ลิสต์ (Linear List) ทำงานแบบ FIFO (First In First Out) เข้ามาใหม่ต่อท้าย ต่อนานที่สุดออกก่อน
คิว (Queue) คือ ชุดของข้อมูลที่เรียงต่อกัน และจัดลำดับการเก็บข้อมูลแบบเข้าก่อนและนำออกก่อน มักเรียกว่าไลโฟ (FiFo = First in First out) อาจมองว่าข้อมูลเข้าใหม่จะมาเรียงต่อท้าย หากเรียกใช้ก็นำข้อมูลที่เคยเข้ามาก่อนออกไปใช้ก่อน ดังนั้นข้อมูลที่เข้ามาก่อน จะอยู่หน้าสุด และพร้อมจะออกเร็วที่สุด

ตัวอย่าง Queue ด้วย Javascript enquery คือ การนำข้อมูลเข้าต่อท้ายสุดของรายการ
dequeue คือ การนำข้อมูลออกจากรายการ ที่เคยเข้ารอนานที่สุด

code : http://www.i-programmer.info/programming/javascript/1674-javascript-data-structures-stacks-queues-and-deques.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<script>
var Q=new Queue();
Q.enqueue("A");
Q.enqueue("B");
Q.enqueue("C");
 
document.write(Q.dequeue()); // A
document.write(Q.dequeue()); // B
document.write(Q.dequeue()); // C
document.write(Q.dequeue()); // undefined
function Queue()
{
 this.stac=new Array();
 this.dequeue=function(){
  return this.stac.pop();
 }
 this.enqueue=function(item){
  this.stac.unshift(item);
 }
}
</script>
ตัวอย่าง Queue ที่ใช้ ADT ด้วยภาษา C short code : https://gist.github.com/mycodeschool/7510222
view code : http://www.thaiall.com/datastructure/queue.cpp
compiler : http://www.thaiall.com/tc
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
<script>
/*
Using the queue ADT
bin>bcc32 queue.cpp
*/
#include <stdio.h>
#include <stdlib.h>
//  Queue ADT Type Defintions
    typedef struct node
      {
       void*        dataPtr;
       struct node* next;
      } QUEUE_NODE;
    typedef struct
      {
       QUEUE_NODE* front;
       QUEUE_NODE* rear;
       int       count;
      } QUEUE;
     
//  Prototype Declarations
    QUEUE* createQueue  (void);
    QUEUE* destroyQueue (QUEUE* queue);
 
    bool  dequeue   (QUEUE* queue, void** itemPtr); // * = pointer
    bool  enqueue   (QUEUE* queue, void*  itemPtr); // ** = pointer of pointer
    bool  queueFront (QUEUE* queue, void** itemPtr);
    bool  queueRear  (QUEUE* queue, void** itemPtr);
    int   queueCount (QUEUE* queue);
    bool  emptyQueue (QUEUE* queue);
    bool  fullQueue  (QUEUE* queue);
//  End of Queue ADT Definitions
 
void printQueue   (QUEUE* stack);
 
int main (void)
{
//  Local Definitions
    QUEUE* queue1;
    QUEUE* queue2;
    int*   numPtr;
    int** itemPtr;
 
//  Statements
    // Create two queues
    queue1 = createQueue();
    queue2 = createQueue();
    for (int i = 1; i <= 5; i++)
       {
         numPtr  = (int*)malloc(sizeof(i)); // set pointer to memory
         *numPtr = i;
         enqueue(queue1, numPtr);
         if (!enqueue(queue2, numPtr))
            {
             printf ("\n\a**Queue overflow\n\n");
             exit (100);
            } // if !enqueue
       } // for
    printf ("Queue 1:\n");
    printQueue (queue1); // 1 2 3 4 5
    printf ("Queue 2:\n");
    printQueue (queue2); // 1 2 3 4 5
    return 0;
}
     
/*  ================= createQueue ================
    Allocates memory for a queue head node from dynamic
    memory and returns its address to the caller.
       Pre  nothing
       Post   head has been allocated and initialized
       Return head if successful; null if overflow
*/
QUEUE* createQueue (void)
{
//  Local Definitions
    QUEUE* queue;
//  Statements
    queue = (QUEUE*) malloc (sizeof (QUEUE));
    if (queue)
       {
        queue->front  = NULL;
        queue->rear   = NULL;
        queue->count  = 0;
       } // if
    return queue;
}   // createQueue
 
/*  ================= enqueue ================
    This algorithm inserts data into a queue.
       Pre  queue has been created
       Post   data have been inserted
       Return true if successful, false if overflow
*/
bool enqueue (QUEUE* queue, void* itemPtr)
{
//  Local Definitions
//      QUEUE_NODE* newPtr;
//  Statements
//      if (!(newPtr = (QUEUE_NODE*)malloc(sizeof(QUEUE_NODE)))) return false;
        QUEUE_NODE* newPtr = (QUEUE_NODE*)malloc(sizeof(QUEUE_NODE));
    newPtr->dataPtr = itemPtr;
    newPtr->next = NULL;     
    if (queue->count == 0)
       // Inserting into null queue
       queue->front  = newPtr;
    else
       queue->rear->next = newPtr;
    (queue->count)++;
    queue->rear = newPtr;
    return true;
}   // enqueue
 
/*  ================= dequeue ================
    This algorithm deletes a node from the queue.
       Pre  queue has been created
       Post   Data pointer to queue front returned and
              front element deleted and recycled.
       Return true if successful; false if underflow
*/
bool dequeue (QUEUE* queue, void** itemPtr)
{
//  Local Definitions
    QUEUE_NODE* deleteLoc;
//  Statements
    if (!queue->count)
        return false;
    *itemPtr  = queue->front->dataPtr;
    deleteLoc = queue->front;
    if (queue->count == 1)
       // Deleting only item in queue
       queue->rear  = queue->front = NULL;
    else
       queue->front = queue->front->next;
    (queue->count)--;
    free (deleteLoc);
    return true;
}   // dequeue
 
/*  ================== queueFront =================
    This algorithm retrieves data at front of the queue
    queue without changing the queue contents.
       Pre  queue is pointer to an initialized queue
       Post   itemPtr passed back to caller
       Return true if successful; false if underflow
*/
bool queueFront (QUEUE* queue, void** itemPtr)
{
//  Statements
    if (!queue->count)
        return false;
    else
       {   
        *itemPtr = queue->front->dataPtr;
         return true;
       } // else
}   // queueFront
 
/*  ================== queueRear =================
    Retrieves data at the rear of the queue
    without changing the queue contents.
       Pre  queue is pointer to initialized queue
       Post   Data passed back to caller
       Return true if successful; false if underflow
*/
bool queueRear (QUEUE* queue, void** itemPtr)
{
//  Statements
    if (!queue->count)
        return true;
    else
       {
        *itemPtr = queue->rear->dataPtr;
        return false;
       } // else
}   // queueRear
 
/*  ================== emptyQueue =================
    This algorithm checks to see if queue is empty
    Pre queue is a pointer to a queue head node
    Return true if empty; false if queue has data
*/
bool emptyQueue (QUEUE* queue)
{
//  Statements
    return (queue->count == 0);
}   // emptyQueue
 
/*  ================== fullQueue =================
    This algorithm checks to see if queue is full. It
    is full if memory cannot be allocated for next node.
       Pre  queue is a pointer to a queue head node
       Return true if full; false if room for a node
*/
bool fullQueue (QUEUE* queue)
{
//  Check empty
if(emptyQueue(queue)) return false; // Not check in heap
//  Local Definitions *
QUEUE_NODE* temp;
//  Statements
    temp = (QUEUE_NODE*)malloc(sizeof(*(queue->rear)));
    if (temp)
       {
        free (temp);
        return false; // Heap not full
       } // if  
    return true; // Heap full
}   // fullQueue
 
/*  ================== queueCount =================
    Returns the number of elements in the queue.
       Pre  queue is pointer to the queue head node
       Return queue count
*/
int queueCount(QUEUE* queue)
{
//  Statements
    return queue->count;
}   // queueCount
 
/*  ================== destroyQueue =================
    Deletes all data from a queue and recycles its
    memory, then deletes & recycles queue head pointer.
       Pre  Queue is a valid queue
       Post   All data have been deleted and recycled
       Return null pointer
*/
QUEUE* destroyQueue (QUEUE* queue)
{
//  Local Definitions
    QUEUE_NODE* deletePtr;
//  Statements
    if (queue)
       {
        while (queue->front != NULL)
           {
            free (queue->front->dataPtr);
            deletePtr   = queue->front;
            queue->front = queue->front->next;
            free (deletePtr);
           } // while
        free (queue);
       } // if
    return NULL;
}   // destroyQueue
 
/*  =================== printQueue ================
    A non-standard function that prints a queue. It is
    non-standard because it accesses the queue structures.
       Pre  queue is a valid queue
       Post queue data printed, front to rear
*/
void printQueue(QUEUE* queue)
{
//  Local Definitions
    QUEUE_NODE* node = queue->front;
//  Statements
    printf ("Front=>");
    while (node)
       {
        printf ("%3d", *(int*)node->dataPtr);
        node = node->next;
       } // while
    printf(" <=Rear\n");
    return;
}   // printQueue
ตัวอย่างการประกาศ variable แบบ pointer ในภาษา C view code : http://www.thaiall.com/datastructure/pointer.cpp
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
#include <stdio.h>
#include <conio.h>
typedef struct {
  int mydata;
} DATA;
DATA* getdata (void);
//
void usedata (DATA* x);
//
main(void) {
clrscr(); // use conio.h
DATA* q1;
q1->mydata = 1;
int a; // variable
a =1;
int *b; // pointer
b = &a;
void* c; // nothing in c
c = &b;
void** d;
*d = (void *)&c;
usedata(q1); // 1
printf("value of a is %d \n", a); // 1
printf("a store in %p \n", (void *)&a); // 0013FF54
printf("value of b is %p \n", b); // 0013FF54
printf("b store in %p \n", (void *)&b); // 0013FF50
printf("value of q1->mydata is %d \n", q1->mydata); // 1
printf("value of c is %p \n", c); // 0013FF50
printf("c store in %p \n", (void *)&c); // 0013FF4C
printf("value of d is %d \n", d); // 4246996 (pointer of pointer)
printf("d store in %p \n", (void *)&d); // 0013FF48 (pointer of pointer)
}
//
void usedata (DATA* x) {
printf("%d \n", x->mydata);
}
แนะนำเว็บ
Slides : Queue

psu : janya *

rmutt : burasakorn

buu: tharatat

itebansomdej.com

learnwww.com

sut: ธรรมศักดิ์

disit: kanitha_sri
เอกสารฉบับเต็ม (Full Text)

รศ.ดร.สมชาย ประสิทธิ์จูตระกูล

Bruno R. Preiss

Mark Allen Weiss

William H. Ford

DB: พัฒณืรพี

Michael Mcmillan
เอกสารอ้างอิง (Reference)
[1] นิรุธ อำนวยศิลป์, "โครงสร้างข้อมูล : การเขียนโปรแกรมและการประยุกต์", บริษัท ดวงกมลสมัย จำกัด., กรุงเทพฯ, 2548.
[2] Guy J.Hale, Richard J.Easton, "Applied Daa Structures Using Pascal", D.C.Heath and Company. Canada. 2530.
[3] โอภาส เอี่ยมสิริวงศ์, "โครงสร้างข้อมูล (Data Structures) เพื่อการออกแบบโปรแกรมคอมพิวเตอร์", บริษัท ซีเอ็ดยูเคชั่น จำกัด., กรุงเทพฯ, 2549.
[4] วิวัฒน์ อภิสิทธิ์ภิญโญ, อมร มุสิกสาร, "โครงสร้างข้อมูล (Data Structures)", บริษัท เอ-บุ๊ค ดิสทริบิวชั่น จำกัด., กรุงเทพฯ, 2548.
[5] เนรมิต ชุมสาย ณ อยุธยา, "เรียนรู้โครงสร้างข้อมูลและอัลกอริทึมด้วย Java", บริษัท ซีเอ็ดยูเคชั่น จำกัด., กรุงเทพฯ, 2550.
[6] ขนิษฐา นามี, "โครงสร้างข้อมูลและอัลกอริทึม", บริษัท ไอดีซี อินโฟ ดิสทริบิวเตอร์ เซ็นเตอร์ จำกัด., กรุงเทพฯ, 2548.
[7] Michael McMillan, "Data Structures and Algorithms with JavaScript", O’Reilly Media, Inc., USA., 2014.
[8] Loiane Groner, "Learning JavaScript Data Structures and Algorithms", Packt Publishing, 2014.

Load Time = 3200 milliseconds
http://goo.gl/72BPC