DTS 08- 11/08/2009

สรุป คิว (queue)
คิวหรือแถวคอย (อังกฤษ: queue) เป็นประเภทข้อมูลอย่างย่อที่มีลักษณะการเรียงลำดับข้อมูล ในการเข้า-ออกในลักษณะเข้าก่อนออกก่อน FIFO (First In First Out) กล่าวคือข้อมูลที่เข้าแรกๆจะได้ออกก่อน คล้ายคนต่อคิวที่มาก่อนจะได้ซื้อของก่อน จึงเรียกว่า แถวคอย หรือ คิว

แถวคอย หรือ คิว จึงจัดเป็นวิธีการจัดการเข้า-ออกของข้อมูลอีกแบบหนึ่ง เป็นโครงสร้างข้อมูลที่นำมาใช้ในการทำงานของโปรแกรมคอมพิวเตอร์หลายประการ อาทิการเข้าคิวในการทำงานของเครือข่าย การออกแบบการทำงานระบบท่อ (pipeline) เป็นต้น

จุดเด่นของคิว
คิวสามารถจัดการการเข้า-ออกของข้อมูล ใช้เก็บข้อมูลที่ต้องการจัดเรียงเป็นระบบ โดยพิจารณาข้อมูลตามลำดับ ในทำนอง ใครถึงก่อนมีสิทธิ์ได้ใช้ก่อน จึงใช้ในการเรียงลำดับในการแบ่งปันทรัพยากรที่มีอยู่จำกัดในการทำงาน เช่น การรอคิวการทำงานของเครื่องพิมพ์ในสำนักงาน เป็นต้น

บริการที่มักจะมีเอาข้อมูลใหม่เข้าท้ายคิว (enqueue)
เอาข้อมูลออกจากหัวคิว (dequeue)
ดูข้อมูลที่อยู่หัวคิว (peek) ทำคิวว่าง ตรวจสอบความว่างของคิว (empty)

ความเร็วที่ใช้ในการทำงานการทำงานของคิว
ไม่จำเป็นต้องไล่พิจารณาสมาชิกทุกตัว เป็นเพียงแต่การพิจารณาข้อมูลที่เข้าแรกสุดออกจากคิว และเอาข้อมูลใหม่เข้าท้ายคิว การทำงานของคิวจึงมีความเร็วคงที่ (O (1))

วิธีการสร้างคิวการสร้างคิวทำได้โดยแถวลำดับประกอบกับจำนวนเต็ม ที่เก็บดัชนีของหัวคิวและท้ายคิว สองตัว หรือใช้ รายการโยงสองชั้นวน(circular doubly linked list)
คิวแถวลำดับสำหรับการใช้แถวลำดับในการทำคิวนั้น (array queue) ตอนเริ่มต้นเราจะให้ดัชนีของหัวคิวและท้ายคิวชี้ที่ศูนย์ เมื่อเข้าคิว (enqueue) ก็จะเก็บข้อมูลตรงดัชนีท้าย พร้อมทั้งเพิ่มค่าดัชนีท้ายคิวจะไปอีกหนึ่ง (increament) ในทางตรงกันข้ามหากเอาข้อมูลตัวแรกออกจากคิว (dequeue) ก็คืนค่าสมาชิกตัวที่ดัชนีหัวคิวชี้อยู่พร้อมทั้งเพิ่มค่าดัชนีหัวคิวไปอีกหนึ่ง (decrement) หากดัชนีหัวคิววิ่งไล่ทับดัชนีท้ายคิวแสดงว่า คิวนั้นเป็นคิวว่าง (empty queue) ไม่ควร dequeue อีกเพราะจะทำให้การทำงานรวนได้ (ควรตรวจสอบก่อน dequeue)
เนื่องจากแถวลำดับมีขนาดจำกัดในบางครั้งอาจมีการทำคิววนรอบ (circular array queue) กล่าวคือบางครั้งคิวอาจมีการ enqueue และ dequeue สลับกันทำให้ดัชนีหัวคิวเลื่อนๆออกไปจนจะตกขอบขวาของแถวลำดับ ทำให้มีเนื้อที่ของแถวลำดับด้านหน้าเหลือไม่ได้ใช้จึงมีการวนเอาหางคิว มาแทนส่วนหน้าของแถวลำดับ กล่าวคือเมื่อท้ายคิวตกขอบขวาของแถวลำดับ ก็จะมีการเริ่มดัชนีท้ายคิวที่ศูนย์ใหม่และต่อท้ายคิวมาเรื่อยๆ ข้อด้อยของวิธีนี้คือ เมื่อท้ายคิวมาทับหัวคิวอีกครั้งจะตีความไม่ได้ว่าคิวเต็มแถวลำดับ หรือคิวว่างกันแน่ จึงอาจใช้ตัวแปรขนาด (size) หรือตัวแปรอื่นๆช่วยในการบอกว่าคิวว่างหรือไม่
คิวรายการโยงสองชั้นวนสำหรับการใช้รายการโยงสองชั้นวน(circular doubly linked list) ในการทำนั้น โดยหัวคิวจะอยู่ที่ปมสุดท้ายนี้ (กล่าวคือเป็นปมก่อนที่จะชี้ปมหัว เพราะว่าเป็นรายการวน) ส่วนท้ายคิวอยู่ที่ปมแรก เมื่อเข้าคิว (enqueue) ก็เพิ่มปมใหม่หลังปมหัว เมื่อจะเอาข้อมูลแรกออกจากคิว (dequeue) ก็จะเอาข้อมูลก่อนปมหัวออก ก็คือข้อมูลที่เข้าแรกๆสุด เมื่อใดที่รายการหรือคิวว่าง ก็คือตอนที่ปมหัวชี้มาที่ตัวเองนั่นเอง

DTS 07- 4/08/2009

สรุป สแตก(Stack)
การเพิ่มข้อมูลในสแตก (pushing stack)
การเพิ่มข้อมูลเข้าสแตก หมายถึงการเพิ่มข้อมูลเข้าในสแตก โดยให้ทับบนข้อมูลสุดท้ายในสแตกจะสามารถเพิ่มเข้าได้เรื่อย ๆ จนกว่าจะเต็มสแตก ความหมายของคำว่า สแตกเต็ม คือท๊อปของสแตกชี้ที่เนื้อที่สุดท้ายของสแตกแล้ว เช่น ถ้า สแตกนั้นจองเนื้อที่ไว้ N เนื้อที่โดยที่สามารถบรรจุสมาชิกในสแตกได้ N ตัว เมื่อสแตกว่างค่าท๊อปเป็นศูนย์ เมื่อสแตกเต็มค่าท๊อปเป็น N ดังนั้นเมื่อท๊อปชี้ที่ N ก็ไม่สามารถ Push ข้อมูลลงสแตกได้อีก

นิยาม push(S,x)
ถ้าให้ S เป็นสแตก และ X เป็นข้อมูล ขบวนการ push (S,X) หมายถึง การ push ข้อมูล X ลงสแตก โดยการ push จะเริ่มจากสแตกว่างโดยให้ค่า TOP เป็นศูนย์ เมื่อมีการ push ข้อมูลเข้าในสแตก ค่า Top จะเปลี่ยนเพิ่มขึ้นทีละหนึ่งทุกครั้งที่ทำการ push

การดึงข้อมูลจากสแตก (Popping Stack)
การดึงข้อมูลออกจากสแตก หมายถึงการนำข้อมูลที่อยู่บนสุดในสแตกหรือที่ชี้ด้วยท๊อปออกจากสแตก จะสามารถ pop สแตกได้เรื่อย ๆ จนกว่าสแตกจะว่าง

นิยาม pop(S)
ถ้าให้ S เป็นสแตก ขบวนการ pop(S) คือการนำข้อมูลบนสุดในสแตกออกจากสแตกและให้ค่าเป็นข้อมูลที่นำออกจากสแตก ดังนั้นถ้านำคำสั่ง X= pop(S) ก็คือการนำข้อมูลที่ท๊อปของสแตกมา และใส่ค่าไว้ที่ X หรือการเซตค่า X ให้เท่ากับข้อมูลที่ดึงจากสแตก

การว่างของสแตก
นิยาม empty(s)
ถ้า S เป็นสแตก ขบวนการ empty(S) จะส่งผลเป็นจริง (true) เมื่อสแตกว่าง และส่งผลเป็นเท็จ (false) เมื่อสแตกไม่ว่าง

การแปลงนิพจน์ Infix ให้เป็น Postfix
ผู้เขียนโปรแกรมสั่งให้เครื่องคำนวณต้องเขียนนิพจน์ที่ต้องการไปในตัวโปรแกรม ซึ่งนิพจน์เหล่านี้เรียกว่า นิพจน์ Infix คือนิพจน์ที่มีโอเปอร์เรเตอร์ (Operator) อยู่ระหว่างโอเปอร์แรนด์ (Operand) ทั้งสอง เช่น A+B เครื่องหมาย + เป็นโอเปอร์เรเตอร์ระหว่างโอเปอร์แรนด์ A และ B ซึ่งเห็นว่าเป็นนิพจน์ที่มนุษย์คุ้นเคย ข้อเสียของนิพจน์ infix ทีททำให้คอมไพเลอร์ยุ่งยาก คือลำดับความสำคัญของโอเปอร์เรเตอร์ (Precedence) ที่ต่างกัน เช่นเครื่องหมายยกกำลัง (ใช้ ^ ในการเขียนโปรแกรม) มีความสำคัญมากกว่าเครื่องหมายคูณ และหาร และเครื่องหมายคูณและหารมีความสำคัญมากกว่าเครื่องหมายบวกและลบ
Operator คือเครื่องหมายกระทำ + - * / ^
Operand คือตัวแปรต่าง ๆ A,B,C,D,E เช่น A+B*C,(A*B)-C

ลำดับความสำคัญ Operator
เครื่องหมายยกกำลัง ^
เครื่องหมายคูณกับหาร *,/
เครื่องหมายบวกกับลบ +,-
เครื่องหมายวงเล็บ () กระทำก่อนเช่น A+(B*C)
เครื่องหมายระดับเดียวกันไม่มีวงเล็บให้ทำจากซ้ายไปขวา เช่น A+B+C

DTS 06-28/07/2009

#include<conio.h>
#include<iostream.h>
void main()
{
int num1,num2,Code,income;
clrscr();
cout<<"**************************************************"<<endl;
gotoxy(6,4);cout<<"Code"<<endl;
gotoxy(3,6);cout<<"1=number1+number2";
gotoxy(3,7);cout<<"2=number1-number2";
gotoxy(3,8);cout<<"3=number1*number2";
gotoxy(3,9);cout<<"4=number1/number2";
gotoxy(3,10);cout<<"5=Exit"<<endl;
cout<<"**************************************************"<<endl;
cout<<endl;
cout<<"Input number1 : ";
cin>>num1; cout<<"Input number2 : ";
cin>>num2; cout<<"Input Code : ";
cin>>Code; cout<&lt"Income : ";
switch(Code)
{
case 1:income=num1+num2;
cout<<income;
break;
case 2:income=num1-num2;
cout<<income;
break;
case 3:income=num1*num2;
cout<<income;
break;
case4:income=num1/num2;
cout<<income; break; default :cout<<"Exit";
}
cout<<endl;
cout<<"**************************************************";
getch();
}