/ * ========================================== Author: rerli: 2003 -12-03 (revised draft) Purpose: To learn the stack by an example.
Stack application details:
The implementation of the stack can be used in arrays, or you can use a list. Hereinafter, these two detailed procedures for implementing stack structures are taken separately: Use a stack change to return to non-recursion, calculate ackermann function a (n, x, y). =================================================== * /
/ * ============================================ first: array It can be seen that the following program does not really use the array to implement, but use the pointer. Use a pointer to operate more flexible than arrays. The following implementation you will experience.
The bottom of the stack is the first address of Stack after initialization; the top of the stack is the last address of the last stack element. The top pointer is the address pointer. =================================================== * /
#include
Typedef struct node {int n; double x; double y;} node;
#define len sizeof (node)
/ * Stack Requires Variable * / TypeDef Enum; / * Defining Bool Type * / Static Node * P_Stack = NULL; / * Defining Stack Pointer Variable * / Static Node * Stack = NULL; / * Define a definition Stack * / static unsigned int stack_size = 0; / * Stack size * /
/ * ================================================================================================================================================================ ========= Stack empty | || _____ || _____ || _____ | null <--- p_stack out of the stack | || ________ || __0__ |
After the stack | || _____ || __1__ | <--- p_stack | __0__ |
From the above figure, you can see: 1. Before the stack, the top pointer does not point to any element; 2, after the stack, the stack top pointer points to the first address of the stack element. 3, this array (or pointer) stack description obviously a bit of a stack definition, ie the top pointer is not true to the top of the stack (it is a bit difficult, but can be realized from the figure). 4. Obviously, if we use the POP () stack to take the value, use * p_stack, it will inevitably get the value of POP (). ============================================================================================================================================================================================================= ========= * /
/ * ======================== function: the size of the initial stack returns: true or false ============= =========== * / bool initstack (unsigned int size) {stack = (node *) malloc (size * len); / * open space * / if (stack == null) / * open The space failed, then returned false * / {return false;} stack_size = size; / * Save the stack space size * / p_stack = stack; / * Stack top finger push assignment * / return true; / * Initialization success, return TRUE * /}
/ * ====================== function: Release the stack memory return: void ================= ===== * / void freeESTACK () {free (stack); / * Note: This is important. FREE () does not set Stack to Null, so we must do it yourself. This prevents the "wild pointer", ie, an address uncertain pointer. * / Stack = NULL;} / * ========================== function: The judgment stack is full of returns: true or false === =================================================================00 At this point, the stack is full * / return (p_stack-stack)> = stack_size;}
/ * =========================== function: The judgment stack is empty back: true or false ========= =================== * / BOOL EMPTY () {/ * Top pointer is equal to the initial address of the stack, then the stack is empty * / return (p_stack == stack) }
/ * ======================== function: into the stack returns: true or false =============== ========= * / BOOL PUSH (Node P) {if (! full ()) / * stack is dissatisfied, then it is stack; the top pointer is to shift * / {* p_stack = p; p_stack ; Return True;} else {printf ("stack is overflow! / n"); return false;}}
/ * =================== function: out of the stack returns: out of the stack element =================== * / Node Pop () {if (! EMPTY ()) / * Stack is not available, then the stack; the top pointer is moved down * / {RETURN * (- p_stack);} else {Printf ("stack is empty! / N ");}} / * ========================================== ========== Function: Use a stack change to the non-recursion, calculate the ackermann function a (n, x, y). Returns: double calculation results ================================================ ====== * / double ackermann {double b; node tnode; if (! full ()) {push (node);} while (! EMPTY ()) {TNODE = Pop (); while (tnode.n! = 0 && tnode.y! = 0) / * Replenishment, the calculation parameter plug * / {/ * Modify the field value of the top node of the stack, if you are not understanding, you can refer to the icon above. * / P_stack-> n-; p_stack-> y = p_stack-> x; p_stack-> x = -1.0; / * Indicates that the X value is not determined * / / * new node value into the stack * / tnode. Y - = 1.0; if (! push (tnode)) / * will be in the next step * / {return -1.0;}}}}}}}}}}}}} = Pop ();} if (tnode.n == 0) {b = tnode.x 1.0;} else if (tnode.n == 1) {b = tnode.x;} else if (tnode.n == 2) {b = 0.0;} else if (TNODE.N == 3) {b = 1.0;} else {b = 2.0;}
if (! EMPTY ()) {p_stack-> x = b; / * Stack is not empty, then the X value of the top node is changed to b * /}} return b;} void main (void) {node node1 = { 3, 1, 2}; if (! INitStack (50)) / * Initialization is unsuccessful, exit * / {exit (0);} printf ("ackermann (% D,% D,% D) =% .2f / "Node1.n, (int )node1.x ,(int )Node1.y ,ackermann (Node1)); FreeStack (); / * Release Stack Memory when you quit * /
Printf ("/ n"); system ("pause");}
