thaiall logomy background

คิว (Queue)

my town
datastructure | รหัสเทียม | เซต | คิว | สแตก | ลิงค์ลิสต์ | ทรี | จัดเรียง | กราฟ | งานมอบหมาย
คิว (Queue)

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


Code : Data Structures

ตัวอย่าง 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 (BCC55 Compiler) short code : https://gist.github.com/mycodeschool/7510222
view code : http://www.thaiall.com/datastructure/queue.cpp
compiler : http://www.thaiall.com/tc [3]p.32
DOS> cd C:\Borland\BCC55\Bin
DOS> copy con bcc32.cfg
-I"c:\Borland\Bcc55\include"
-L"c:\Borland\Bcc55\lib"
DOS> bcc32 queue.cpp
DOS> queue
/*
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
ตัวอย่างการประกาศ 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);
}
pointer ใน BCC 5.5
/*
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
}	
Struct in ADT of Queue ใช้ BCC 5.5
/*
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/
Slides : Queue

psu : janya *

rmutt : burasakorn

buu: tharatat

itebansomdej.com

learnwww.com

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

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

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

Mark Allen Weiss

A Byte of Python
เอกสารอ้างอิง (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.
Thaiall.com