คิว (Queue) คือ โครงสร้างข้อมูลจัดเรียงข้อมูลแบบลิเนียร์ลิสต์ (Linear List) ทำงานแบบ FIFO (First In First Out) เข้ามาใหม่ต่อท้าย ต่อนานที่สุดออกก่อน คิว (Queue) คือ ชุดของข้อมูลที่เรียงต่อกัน และจัดลำดับการเก็บข้อมูลแบบเข้าก่อนและนำออกก่อน มักเรียกว่าไลโฟ (FiFo = First in First out) อาจมองว่าข้อมูลเข้าใหม่จะมาเรียงต่อท้าย หากเรียกใช้ก็นำข้อมูลที่เคยเข้ามาก่อนออกไปใช้ก่อน ดังนั้นข้อมูลที่เข้ามาก่อน จะอยู่หน้าสุด และพร้อมจะออกเร็วที่สุด
Code : Data Structures
<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>
/* 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> // required for malloc() // 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
#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); }
/* bin>bcc32 ppointer.cpp int* p p is a pointer to an integer. int** p p is a pointer to a pointer to an integer. &p is address of a variable http://www.cplusplus.com/doc/tutorial/pointers/ */ #include <stdio.h> int main (void) { int i[1], j[1]; i[0] = 2; j[0] = 4; int* num1; num1 = &i[0]; // 1703752 int* num2 = num1; i[0] = 3; // printf("%d \n", num1); // 1703752 printf("%d \n", num2); // 1703752 int k = *num2; printf("%d \n", k); // 3 printf("%d \n", *num2); // 3 num2 = &j[0]; printf("%d \n", *num1); // 3 printf("%d \n", *num2); // 4 printf("%d \n", num2); // 1703748 int** num3; num3 = &num1; printf("%d \n", **num3); // 3 **num3 = j[0]; printf("%d \n", **num3); // 4 }
/* bin>bcc32 strucq.cpp */ #include <stdio.h> #include <stdlib.h> typedef struct node { void* dataPtr; struct node* next; } QUEUE_NODE; typedef struct { QUEUE_NODE* front; QUEUE_NODE* rear; int count; } QUEUE; int main (void) { QUEUE* queue = (QUEUE*) malloc (sizeof (QUEUE)); queue->count = 0; queue->front = NULL; queue->rear = NULL; // int d[3] ={100,200,300}; int *data[3]; data[0] = &d[0]; data[1] = &d[1]; data[2] = &d[2]; // QUEUE_NODE* newData1 = (QUEUE_NODE*)malloc(sizeof(QUEUE_NODE)); newData1->dataPtr = data[0]; newData1->next = NULL; queue->front = newData1; queue->rear = newData1; queue->count++; printf("%d %d %d \n", queue->count , *(int*)queue->front->dataPtr , *(int*)queue->rear->dataPtr ); // QUEUE_NODE* newData2 = (QUEUE_NODE*)malloc(sizeof(QUEUE_NODE)); newData2->dataPtr = data[1]; newData2->next = NULL; queue->rear->next = newData2; queue->rear = newData2; queue->count++; printf("%d %d %d \n", queue->count , *(int*)queue->front->dataPtr , *(int*)queue->rear->dataPtr ); // QUEUE_NODE* newData3 = (QUEUE_NODE*)malloc(sizeof(QUEUE_NODE)); newData3->dataPtr = data[2]; newData3->next = NULL; queue->rear->next = newData3; queue->rear = newData3; queue->count++; printf("%d %d %d \n", queue->count , *(int*)queue->front->dataPtr , *(int*)queue->rear->dataPtr ); // QUEUE_NODE* node = queue->front; printf ("Front=>"); while (node) { printf (" %3d ", *(int*)node->dataPtr); node = node->next; } printf("<=Rear\n"); }
http://embed.plnkr.co/NauLDO/ http://www.dreamincode.net/forums/topic/49439-concatenating-queues-in-c/
