Stack ที่เราเจอในชีวติประจำวัน

คุณสมบัติของ Stack ไลโฟลิสต์ (LIFO list: Last-In-First-Out list) หรือ พูชดาวน์ลิสต์ (Pushdown List) คือสมาชิกที่เข้าลิสต์ที่หลังสุดจะได้ออกจากลิสต์ก่อน หรือ เข้าหลังออกก่อน


Stack ที่เราเจอในชีวิตประจำวันเป็นประจำสำหรับผมก็ คือ "ตั๋วรถเมล์" ที่เรานั่งกันอยู่ทุกๆวันนี้เอง
เพราะ การฉีกตั๋วรถเมล์นั้นจะ ฉีกจากด้านนอกเข้าสู่ศูนย์กลางซึ่งเป็นคุณสมบัติของ Stack นั้นเอง

DST 05-22/07/09

Stack

โครงสร้างของ Stack

สแตกเป็นโครงสร้างข้อมูลแบบลิเนียร์ลิสต์(linear list) ที่สามารถนำข้อมูลเข้าหรือออกได้ทางเดียวคือส่วนบนของสแตกหรือ หรือเรียกว่า ท๊อปของสแตก (Top Of Stack) ซึ่งคุณสมบัติดังกล่าวเรียกว่า ไลโฟลิสต์ (LIFO list: Last-In-First-Out list) หรือ พูชดาวน์ลิสต์ (Pushdown List) คือสมาชิกที่เข้าลิสต์ที่หลังสุดจะได้ออกจากลิสต์ก่อน หรือ เข้าหลังออกก่อน การเพิ่มข้อมูลเข้าสแตกจะเรียกว่าพูชชิ่ง (pushing) การนำข้อมูลจากสแตกเรียกว่า ป๊อปปิ้ง (poping) การเพิ่มหรือลบข้อมูลในสแตกทำที่ท๊อปของสแตก ท๊อปของสแตกนี้เองเป็นตัวชี้สมาชิกตัวท้ายสุดของสแตก การทำงานของสแตกจะประกอบด้วยกระบวนการ 3 กระบวนการที่สำคัญคือ

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

Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตก โดยการนำข้อมูลออกจากสแตก ถ้าสแตกมีสมาชิก เพียง 1ตัว แล้วนำสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง (Stack Empty)คือ ไม่มีสมาชิก อยู่ในสแตกเลย แต่ถ้าไม่มีสมาชิกในสแตก แล้วทำการ pop สแตก จะทำให้ เกิดความผิดพลาดที่เรียกว่า Stack Underflowเพราะฉะนั้นก่อนนำข้อมูลออกจากสแตกจะต้องตรวจสอบ ก่อนว่าสแตกว่างหรือเปล่า จึงจะนำข้อมูลออกจากสแตกได้และ ปรับตัวชี้ตำแหน่งให้ไปชี้ตำแหน่งของข้อมูลที่ต่อจากข้อมูลที่ถูกนำ ออกไป

Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตกการแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ

1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์ ประกอบไปด้วย2 ส่วน คือ1. Head Node จะประกอบไปด้วย 2ส่วนคือ top pointer และจำนวนสมาชิกในสแตก

2. Data Node จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ ที่ชี้ไปยังข้อมูลตัวถัดไป2. การแทนที่ข้อมูลของสแตกแบบอะเรย์การดำเนินการเกี่ยวกับสแตก

ส่วนประกอบของสแตก

การนำสแตกไปใช้งานนั้นไม่ว่าจะเป็นโครงสร้างสแตกแบบแถวลำดับ(array)หรือ แบบลิงค์ลิสต์ (link list) เราจะมีตัวแปรตัวหนึ่งที่ใช้เป็นตัวชี้สแตก(stack pointer ) เพื่อเป็นตัวชี้ข้อมูลที่อยู่บนสุดของสแตก ซึ่งจะทำให้สามารถจัดการข้อมูล ที่จะเก็บในสแตกได้ง่าย ดังนั้นโครงสร้างข้อมูลแบบสแตกจะแบ่งออกเป็น 2 ส่วนที่สำคัญ คือ

1. ตัวชี้สแตก ( Stack Pointer ) ซึ่งมีหน้าที่ชี้ไปยังข้อมูลที่อยู่บนสุดของ สแตก ( Top stack )
2. สมาชิกของสแตก ( Stack Element ) เป็นข้อมูลที่จะเก็บลงไปในสแตก ซึ่งจะต้องเป็นข้อมูลชนิดเดียวกัน เช่น ข้อมูลชนิดจำนวนเต็ม เป็นต้น

ประโยชน์ของ Stack

ประโยชน์ของสแตก ใช้ในการจดจำการกระโดดไปมาระหว่างโปรแกรมย่อย ใช้ในการเขียนโปรแกรมแบบรีเคอร์ซีฟ (Recursive) ใช้ในการจดจำเส้นทางในการเดินทางของโครงสร้างข่ายงาน (Network) หรือ โครงสร้างของต้นไม้ (Tree) ลักษณะสำคัญของสแตก โครงสร้างข้อมูลเป็นแบบเชิงเส้น (Linear structure) มีโครงสร้างที่ไม่ตายตัว (dynamic structure) นำข้อมูลเข้าและดึงข้อมูลออกได้ (push and pop) นำข้อมูลเข้าและดึงข้อมูลออกแบบลำดับ (lifo mechanism) มีการจัดการนำเข้าและดึงข้อมูลในตำแหน่งบนสุด (push and pop at top)

การเขียนโปรแกรมแบบ iostream.h กับ stdio.h

นี้เป็น โปรแกรมสำหรับคำนวณ พื้นที่สี่เหลี่ยม ตามที่เรากำหนดโดยเขียนให้ออกมาเป็น 2 รูปแบบคือ


1."stdio.h"

2."iostream.h"


"stdio.h"


#include"stdio.h"
void main()
{

int hight;
int width;
int sum;
printf(",.:'*':. :Parallelogram area calculating progaram: .:'*':. \n\n");
printf("Hight is : ");
scanf ("%d",&hight);
printf("\nWidth is : ");
scanf ("%d",&width);
sum = hight*width;
printf("\nThe Circle Area :%d",sum);

}


"iostream.h"


#include "iostream.h"
void main()
{

float hight;
float width;
float all;
cout << ",.:'*':. :Parallelogram area calculating progaram: .:'*':. \n \n";
cout << "Hight is : ";
cin >> hight;
cout << "\nWidth is : ";
cin >> width;
all = hight*width;
cout <<"\nThe Circle Area :";
cout << all;

}

Dts 4-15/07/2552

นี้เป้นการเรียนการสอนครั้งที่ 4 วันนี้เป็นกการเรียนเรื่อง Linked List
โครงสร้างข้อมูล Linked List เป็นวิธีแก้ปัญหา ข้อมูลที่พบในการจัดเก็บที่มีรูปแบบ เรียงตามลำดับ (Sequential) เปลี่ยนมาใชรูปแบบใหม่แบบไม่เรียงลำดับ (Non-Sequential) ซึ่งรูปแบบในการเก็บข้อมูลนั้นสมาชิกจะต้องเรียงต่อเนื่องกันติดๆกันในทางตรรกะ (Logical) และทางกายภาพ (Physical)เป็นแบบเดียวกันแต่ รูปแบบไม่เรียงตามลำดับ สมาชิกจะเรียงต่อเนื่องกันในส่วนของ ตรรกะ ส่วนทางกายภาพไม่จำเป็นต้องเหมือนกัน

DTS 3-1/07/2552

การเรียนการสอนครั้งนี้เป็นเรื่องของ Pointer อาจจะสงสัยว่า Pointer คืออะไรเหมือนผมในช่วงแรกของการเรียน Pointer เป็นตัวแปรชนิดหนึ่งที่ทำหน้าที่เก็บตำแหน่งที่อยู่ Address ของตัวที่ลงในหน่อวความจำ
รูปแบบของ Pointer type *variable-name
type หมายถึง ชนิดตัวแปร
* หมายถึง เป็นเครื่องที่แสดงว่า ตัวแปรที่ตามหลังเครื่องหมายนี้เป็นตัว Pointer
Variable-name หมายถึง ชื่อของตัวแปรที่ถูกประกาศให้เป็น Pointer
การประกาศตัวแปร Pointer
ต้องมีระบุตัวดำเนินการ (Operator) เพื่อบอกว่าตัวแปรดังกล่าวเป็นตัวแปรแบบตัวชี้ โดยตัวดำเนินการที่ใช้คือ * และ & เช่น จะประกาศตัวแปรชนิดPointer คือ int *countPtr; ในที่นี้หมายถึง ตัวแปร countPtr ถูกประกาศให้เป็นตัวแปรชนิด Pointer และทำหน้าที่ชี้ (เก็บ Address) ไปยังตำแหน่งที่เก็บค่าจำนวนเต็ม (เป็นชนิดเดียวกับที่เราประกาศไว้ ในที่นี้คือ Integer)
ตัวอย่าง
Char *prt;
หมายความว่าประกาศตัวแปร prt เป็นตัวแปร Pointer ที่ใช้เก็บตำแหน่งเริ่มต้นที่จะเก็บ Character
Int *a;
หมายความว่า ประกาศว่าตัวแปร a เป็นตัวแปร Pointer ที่ใช้เก็บตำแหน่งเริ่มต้นที่จะใช้เก็บ integer

เครื่องหมายที่ใช้ใน Pointer
1. เครื่องหมาย & เป็นเครื่องหมายที่ใช้เมื่อต้องการให้เอาค่าตำแหน่งที่อยู่ของตัวแปรที่เก็บไว้ในหน่วยความจำออกมาใช้
2. เครื่องหมาย * มีการใช้งานเป็น 2 ลักษณะ คือ ประการแรก ใช้ประกาศตัวแปร Parameter ว่าเป็นตัวแปร Pointer ประการที่สอง ใช้เป็น dereferencing operator จะใช้งานเมื่อต้องการนำค่าที่อยู่ในต่ำแหน่งที่ตัวแปร Pointer นั้นชี้อยู่ออกมาแสดง

แบบฝึกหัดท้ายบท บทที่ 2

แบบฝึกหัดท้ายบท

บทที่ 2

1.ให้นักศึกษากำหนดค่าของ Array 1 มิติและ Array 2 มิติ
ตอบ Array คือกลุ่มของข้อมูล ที่มีชนิดของข้อมูลเป็นชนิดเดียวกัน การอ้างถึงกลุ่มของชุดข้อมูลนี้จะอ้างด้วยชื่อของตัวแปรเดียวกัน ในการกำหนดค่าของ Array จะต้องกำหนอชื่อ Array พร้อม Subscript ซึ่งเป็นตัวกำหนดขอบเขตของ Array มีได้มากกว่า 1 จำนวน Subscript จะเป็นตัวบอกมิติของ Array นั้นๆว่ามีกี่ มิติ

ตัวอย่างการเขียนโปรแกรม Array 1 มิติ
เป็นการเขียนโปรแกรมรับตัว เลขที่เป็นจำนวนเต็ม 5 จำนวนจากผู้ใช้ และแสดงผล

#include
#include
void main()
{int i, j, array1Record[5];
clrscr();
for (i=0; i<5;> ",i);
scanf("%d",&array1Record[i]);
}
printf("\n");
for (j=0; j<5;> %d ", j, array1Record[j]);
}
getch();
}





ตัวอย่างการเขียนโปรแกรม Array 2 มิติ
เป็นการเขียนโปรแกรมรับตัวรับค่าอักขระ แล้วนำไปเก็บในตัวแปรชุดแบบ 2 มิติ มีขนาด 3 แถว 2 คอลัมน์ และแสดงผล

#include
#include
void main()
{ int i, j, k, l;
char array2Record[3][2];
clrscr();
for (i=0; i<3; j="0;"> ", i, j);
flushall();
scanf("%c",&array2Record[i][j]);
}
}
printf("\n");
for (k=0; k<4; l="0;">%c ", k, l, array_2dim[k][l]);
}
}
getch();
}




2. ให้นักศึกษาหาค่าของ A[2], A[6] จากค่า A={2,8,16,24,9,7,3,8}
ตอบ ค่าของ A[2] = 16
ค่าของ A[6] = 3

3. จากค่าของ int a[2][3] = {{6,5,4},{3,2,1}}; ให้นักศึกษาหาค่าของ a[1][0] และ a[0][2]
ตอบ ค่าของ A [1][0] = 3
ค่าของ A [0][2] = 4

4. ให้นักศึกษากำหนด Structure ที่มีค่าของข้อมูลจากน้อย 6 Record
ตอบ เป็นโครงสร้างของร้านขายกางเกง ยีนต์ ยี้ห้อ Nudie ที่ต้องกรอกรายละเอียดสินค้าและรหัสบัตรเครดิต ชื่อ นามสกุล เบอร์โทรศัพท์มือถือ E-mail เพื่อใช้ยืนยันตัวตนในการซื้อสินค้า

#include"stdio.h"
struct data
{
int day;
int month;
int year;
};
struct nudie
{
int id;
int nudie2;
char name[40];
char last[40];
char nudie[100];
char tel[12];
char mail[100];
char nudie1[100];
struct data shop;
}nu;
void input_data()
{
printf("Wellcome to Nudie Jeans Co Shop\n\n");
printf(".:'*':. Product in Shop .:'*':.\n\n");
printf("1. Tight Long John Price 5800 ß\n");
printf("2. Thin Finn Price 5400 ß\n");
printf("3. Slim Jim Price 5800 ß\n");
printf("4. Grim Tim Price 6000 ß\n");
printf("5. Super Slim Kim Price 5000 ß\n");


printf("\nProduct is your select:");
scanf("%s",&nu.nudie1);
printf("Price of jeans:");
scanf("%d",&nu.nudie2);


printf("\n----Data customer----\n");
printf("\nID Credit card :");
scanf("%d",&nu.id);
printf("name of customer:");
scanf("%s",&nu.name);
printf("lastname of customer:");
scanf("%s",&nu.last);
printf("Number cell phone of customer:");
scanf("%s",&nu.tel);
printf("E-Mail of customer:");
scanf("%s",&nu.mail);
printf("\ndate:");
scanf("%d-%d-%d",&nu.shop.day,&nu.shop.month,&nu.shop.year);


}
void show_data()
{
printf("\n+++Data customer+++\n");
printf("\nDisplay Date : %d-%d-%d\n",nu.shop.day,nu.shop.month,nu.shop.year);
printf("ID of credit card :%d\n",nu.id);
printf("Name and Lastname of Member:%s %s\n",nu.name,nu.last);
printf("cell phone Number of Customer :%s\n",nu.tel);
printf("E-mail of Customer :%s\n",nu.mail);
printf("Jeans is your coice :%s %d ß\n",nu.nudie1,nu.nudie2);
}
main()
{
input_data();
show_data();
return 0;
}


5. ให้นักศึกษาบอกความแตกต่างของการกำหนดตัวแปรชนิด Array กับตัวแปร Pointer ในสภาพของการกำที่อยู่ของข้อมูล
ตอบ ตัวแปร Pointer คือตัวแปรที่เก็บตำแหน่งของหน่วยความจำซึ่งตำแหน่งของหน่วยความจำนี้จะเป็นที่อยู่ของสิ่งอื่น ๆ ในหน่วยความจำ
Array คือกลุ่มของข้อมูล ที่มีชนิดของข้อมูลเป็นชนิดเดียวกัน การอ้างถึงกลุ่มของชุดข้อมูลนี้จะอ้างด้วยชื่อของตัวแปรเดียวกัน
ความแตกต่างระหว่างตัวแปร Array และ Pointer คือตัวแปรตารางอาเรย์จะเก็บเฉพาะค่าต่างๆ ที่เป็นชนิดกันเดียวกับตัวแปรอาเรย์แต่ ตัวแปรพอยเตอร์จะเก็บเฉพาะค่าตำแหน่ง Address ตัวแปรเท่านั้น