สแตก (Stack)
สแตก (Stack)

สแตก (Stack) คือ ชุดของข้อมูลที่เรียงต่อกัน และจัดลำดับการเก็บข้อมูลแบบเข้าทีหลังและนำออกก่อน มักเรียกว่าไลโฟ (LiFo = Last in First out) อาจมองว่าข้อมูลเข้าใหม่จะมาเรียงต่ออยู่ด้านบน หากเรียกใช้ก็นำด้านบนสุดออกไปก่อน ดังนั้นข้อมูลที่เข้ามานานที่สุด จะอยู่ล่างสุด และจะอยู่ในสแตกนานที่สุด


ฟังก์ชัน Push คือ เพิ่มข้อมูลลงสแตก [3]p.137
ฟังก์ชัน Pop คือ นำข้อมูลบนสุดไปใช้ และลบออกจากสแตก
ฟังก์ชัน Stack Top คือ นำข้อมูลบนสุดไปใช้ แต่ไม่ลบออกจากสแตก
Infix คือ นิพจน์ทางคณิตศาสตร์ทั่วไปที่เราใช้กัน [3]p.159
Postfix คือ นิพจน์ที่โอเปอเรเตอร์อยู่หลังโอเปอแรนต์ เช่น AB+
Prefix คือ นิพจน์ที่โอเปอเรเตอร์อยู่หน้าโอเปอแรนต์ เช่น +AB
+ http://i-programmer.info



แนะนำเว็บไซต์
+ Stack ภาษาไทย มีอัลกอริทึม 8 ฟังก์ชัน ***
+ C Online Compiler (on browser)
+ คลิ๊ปบรรยาย infix prefix postfix ของ Carleton Moore
+ ตัวอย่าง binary tree ด้วย javascript
+ DS materials in C language
+ ภาพการทำงานกับ stack
ความหมาย - สแตก(Stack) คือ โครงสร้างข้อมูลจัดเรียงข้อมูลแบบลิเนียร์ลิสต์ (Linear List) เน้นจัดการกับข้อมูลที่สวนบนสุด แบบ LiFo (Last in First out)
<script>
var stack=new Array();
stack.push("A");
stack.push("B");
stack.push("C");
document.write(stack.pop()); // C
document.write(stack.pop()); // B
document.write(stack.pop()); // A
document.write(stack.pop()); // undefined

function stack() {
 this.stac=new Array();
 this.pop=function(){
  return this.stac.pop();
 }
 this.push=function(item){
  this.stac.push(item);
 }
}
</script>
อัลกอริทึมการแปลง Infix เป็น Postfix
กัญญา ส้ม สนินัด
https://www.gotoknow.org/posts/180195
Stack ทำงานแบบ LIFO มีอัลกอริทึมในการแปลงนิพจน์ ดังนี้
1. ถ้าข้อมูลเข้า ( input) เป็นตัวถูกดำเนินการ ( operand - A B C ) ให้นำออกไปเป็นผลลัพธ์ ( output)
2. ถ้าข้อมูลเข้าเป็นตัวดำเนินการ ( operator - + * % ) ให้ดำเนินการดังนี้
2.1 ถ้าสแตคว่าง ให้ push operator ลงในสแตค
2.2 ถ้าสแตคไม่ว่าง ให้เปรียบเทียบ operator ที่เข้ามากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตค
2.2.1 ถ้า operator ที่เข้ามามีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตคให้ push ลงสแตค
2.2.2 ถ้า operator ที่เข้ามามีความสำคัญน้อยกว่าหรือเท่ากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตค ให้ pop สแตคออกไปเป็นผลลัพธ์ แล้วทำการเปรียบเทียบ operator ที่เข้ามากับ operator ที่ตำแหน่ง TOP ต่อไป จะหยุดจนกว่า operator ที่เข้ามาจะมีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตค แล้วจึง push operator ที่เข้ามานั้นลงสแตค
3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตค
4. ถ้าข้อมูลเข้าเป็นวงเล็บปิด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์จนกว่าจะถึงวงเล็บ เปิด จากนั้นทิ้งวงเล็บเปิดและปิดทิ้งไป
5. ถ้าข้อมูลเข้าหมด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์จนกว่าสแตคจะว่าง
ให้ฝึกแปลงนิพจน์ Infix เป็นนิพจน์ Postfix เช่น นิพจน์ A + B * C
ตัวอย่างฟังก์ชัน
ตัวอย่างฟังก์ชัน และอัลกอริทึม 8 ฟังก์ชันที่ทำงานกับ stack [3]p.143
1. ฟังก์ชัน Create Stack คือ สร้าง
2. ฟังก์ชัน Push Stack คือ เพิ่ม
3. ฟังก์ชัน Pop Stack คือ อ่านแล้วลบ
4. ฟังก์ชัน Stack Top คือ อ่านอย่างเดียว
5. ฟังก์ชัน Empty Stack คือ ตรวจว่าว่างหรือไม่
6. ฟังก์ชัน Full Stack คือ ตรวจว่าเต็มหรือไม่ ป้องกัน Stack overflow
7. ฟังก์ชัน Stack count คือ นับจำนวนสมาชิก
8. ฟังก์ชัน Destroy Stack คือ ลบข้อมูลทั้งหมด
ความเข้าใจหน้าที่ของแต่ละฟังก์ชันเป็นเรื่องสำคัญ
มีตัวอย่างฟังก์ชันทำงานกับ Array of Character ภาษา C ให้ศึกษา ประกอบด้วย strcmp, strcpy, strcat, strlen
// [3]p.151 ตัวอย่าง Definition
typedef struct node {
  void* dataPrt;
  struct node* link;
} STACK_NODE;
typedef struct {
  int count;
  STACK_NODE* top;
} STACK;
+ ตัวอย่าง Source code : stack.c และ stack.h ที่ https://gist.github.com/RenatoUtsch/4162787
+ ตัวอย่าง Source code ทั้ง pascal และ c อย่างสั้น ที่ http://wiki.gis.com/wiki/index.php/Stack_(data_structure)
ตัวอย่าง 8 ฟังก์ชันของ stack ด้วยภาษา C Source code จาก https://block.withcs.net/page/clone_solution.php?sid1=110729&sid2=110837&uid=jhlee01s&pid=4293
ทดสอบที่ https://www.jdoodle.com/c-online-compiler แบบเปิด interactive mode
//  main.c
//  withcsWEEK4
//
//  Created by JihwanLEE on 2017. 5. 9..
//  Copyright ? 2017? jihwanlee. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
typedef struct node {
	double        dataPtr;
	struct node* link;
} STACK_NODE;
	typedef struct {
	int         count;
	STACK_NODE* top;
} STACK;
STACK*  createStack     (void);
bool    pushStack       (STACK* stack, double dataInPtr);
double   popStack        (STACK* stack);
double   stackTop        (STACK* stack);
bool    emptyStack      (STACK* stack);
bool    fullStack       (STACK* stack);
int     stackCount      (STACK* stack);
STACK*  destroyStack    (STACK* stack);
// 
STACK* createStack (void) {
	STACK* stack;
	stack = (STACK*) malloc (sizeof(STACK));
	if(stack) {
		stack->count = 0;
		stack->top   = NULL;
	}
	printf("Address of stack: %p on createStack\n", &stack);
	return stack;
}
//
bool pushStack (STACK* stack, double dataInPtr) {
	STACK_NODE* newPtr;
	// memory allocation
	newPtr = (STACK_NODE*) malloc (sizeof(STACK_NODE));
	if(!newPtr) return false;
	newPtr->dataPtr = dataInPtr;
	newPtr->link    = stack->top;
	stack->top      = newPtr;
	(stack->count)++;
	return true;
}
//
double popStack (STACK* stack) {
	double       dataOutPtr;
	STACK_NODE* temp;
	if(stack->count == 0) {
		dataOutPtr = -1;
		printf("stack empty : POP\n");
	}
	else {
		temp        = stack->top;
		dataOutPtr  = stack->top->dataPtr;
		stack->top  = stack->top->link;
		free(temp);
		stack->count--;
	}
	return dataOutPtr;
}
//
double stackTop (STACK* stack) {
	if(stack->count == 0) {
		printf("stack empty: stackTOP\n");
		return -1;
	}
	else
		return stack->top->dataPtr;
}
//
bool emptyStack (STACK* stack) {
	return (stack->count == 0);
}
//
bool fullStack (STACK* stack) {
	STACK_NODE* temp;
	printf("Address of temp (New Node): %p\n", &temp);
	printf("Address of stacktop: %p\n", &(stack->top));
	if((temp = (STACK_NODE*) malloc (sizeof(*(stack->top))))) {
		free(temp);
		return false;
	}
	return true;
}
//
int stackCount (STACK* stack) {
	return stack->count;
}
//
STACK* destroyStack (STACK* stack) {
	STACK_NODE* temp;
	if(stack) {
		while(stack->top != NULL) {
			temp       = stack->top;
			stack->top = stack->top->link;
			free(temp);
		}
		free(stack);
	}
	return NULL;
}
//
int main() {
	STACK* stack = createStack();
	char string[100];
	string[0]='h';
	string[1]='e';
	string[2]='l';
	string[3]='l';
	string[4]='o';
	printf("string have %zu chars \n",strlen(string)); // 5
	printf("stackCount = %i \n",stackCount(stack)); // 0
	pushStack(stack,string[0]); // h
	printf("stackCount = %i \n",stackCount(stack)); // 1 = h
	for(int i=0; i<strlen(string); i++) pushStack(stack,string[i]);
	pushStack(stack,string[0]); // hhelloh
	printf("stackCount = %i \n",stackCount(stack)); // 7
	printf("stackTop = %.0f \n",stackTop(stack)); // 104 = h
	printf("%.0f \n",popStack(stack)); // 104 = h
	printf("%.0f \n",popStack(stack)); // 111 = o
	printf("%.0f \n",popStack(stack)); // 108 = l
	printf("%.0f \n",popStack(stack)); // 108 = l
	if(!emptyStack(stack)) printf("emptyStack = false \n"); // false
	if(!fullStack(stack)) printf("fullStack = false \n"); // false
	printf("%.0f \n",popStack(stack)); // 101 = e
	printf("%.0f \n",popStack(stack)); // 104 = h
	printf("%.0f \n",popStack(stack)); // 104 = h
	printf("%.0f \n",popStack(stack)); // stack empty : POP and -1
    printf("sizeof int = %zu bytes\n", sizeof (int)); // 4 bytes
    printf("sizeof string[100] = %zu bytes\n", sizeof string); // 100 bytes
    destroyStack(stack);
    printf("stackCount = %i \n",stackCount(stack)); // -1587399272 
	return 0;
}
ตัวอย่างการแปลง infix เป็น postfix
Slides : Stack

niit : Azhar Maqsood

graceland : rsmith

up : wattanapong

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

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

Bruno R. Preiss

Mark Allen Weiss

William H. Ford

DB: พัฒณืรพี

Michael Mcmillan
งานมอบหมาย (Assignment)
โจทย์ให้ฝึกแปลงจาก infix เป็น postfix โดยใช้ stack ตามตัวอย่าง
1. a + b - c * d / e - f + g * h 
2. a * b - c * d + e - f + g * h 
3. a + b * c * d / (e * f) * g + h 
4. a + b - (c * d) - e - f + g - h 
5. a + (b + c) * d / e + f / g * h 
6. a / b * c * d * (e - f) + g ^ h 
7. (a ^ b) / c * d / e - f + g + h 
8. a * b ^ c * ((d - e) - f) * g - h 
9. a + b - c ^ ((d - e) - f) * (g - h) 
10. a / (b + c) * (d + (e + f)) ^ g + h 
เอกสารอ้างอิง (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.

http://goo.gl/72BPC