สแตก (Stack) คือ ชุดของข้อมูลที่เรียงต่อกัน และจัดลำดับการเก็บข้อมูลแบบเข้าทีหลังและนำออกก่อน มักเรียกว่าไลโฟ (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>
// [3]p.151 ตัวอย่าง Definition typedef struct node { void* dataPrt; struct node* link; } STACK_NODE; typedef struct { int count; STACK_NODE* top; } STACK;
// 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 โดยใช้ 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
