คิว (Queue)

ปรับปรุง : 2560-09-16 (ปรับเป็น responsive)

คิว (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

<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

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
edit from http://www.dreamincode.net/forums/topic/49439-concatenating-queues-in-c/
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

#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);
}

แนะนำเว็บ

1 2	`http://embed.plnkr.co/NauLDO/` `http://www.dreamincode.net/forums/topic/49439-concatenating-queues-in-c/`

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

"Imagination is more important than knowledge" - Albert Einstein

http://goo.gl/72BPC