/ * ================================================================================================================================================================ ================= author: rerli time: 2003-12-03 (revised) Objective: To study the stack by one 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). ============================================================================================================================================================================================================= ================= * /
/ * ================================================================================================================================================================ ================== second: The stack of the linked list is referred to as a link. It is clear that the link is not said to be said, it is from the people who don't refuse! The top of the stack is the first element of the linked list; the bottom of the stack is the last element of the linked list; the head pointer of the linked list is the top pointer of the stack. ============================================================================================================================================================================================================= ================= * /
#include
Typedef struct node {int N; double x; double y;} node; type; structure; ster;
#define len sizeof (Lnode)
/ * Stack Requires Variable * / TypeDef Enum {False, True} Bool; / * Defines BOOL Type * / Static Lnode * P_Stack = NULL; / * Defining Stack Pointer Variables * /
/ * ================================================================================================================================================================ ================== 空 | || _____ || _____ || _____ | null <--- p_stack
Before the stack | || _____ || __1__ | <--- p_stack | __0__ |
After the stack | || _____ || __1__ || __0__ | <--- p_stack
From the above figure, it is known: 1, before the stack, the top pointer points to the address of the top element; 2. After the stack, the top pointer points to the address of the original set of top elements. 3, this link stack clearly more in line with the definition of the stack. In contrast, it is more likely to understand more than array (or pointers). 4, obviously if we use the POP () stack to take the value with * p_stack, the value does not have the value of the value of POP (). 5. Note that 4 of the 4 and front arrays (or pointer) stacks above the stack is different depending on the value of the top finger needle, which leads us that we can use array (or pointers) stacks to easily implement the Ackermann function. A (N, X, Y), and the link stack does not implement unless we changed the structure. ============================================================================================================================================================================================================= ==================== * /
/ * ================================================================================================================================================================ ====================== Notice the link stack ratio of the array (or pointer) stacks less than a few functions, the above variables are small. ============================================================================================================================================================================================================= ==================== * // * ========================================================================================================================================== ==== Function: The judgment stack returns: true or false ======================================= * / bool empty () {/ * Stack top pointer is equal to NULL, then the stack is empty * / return (p_stack == null);
/ * ============================== function: into the stack returns: true or false ========== ====================== * / BOOL PUSH (Node P) {static lnode * stack = null; stack = (lnode *) malloc (len); / * Open a space of a node * /
IF (stack! = null) {stack-> DATA = P; / * Add Stack * / stack-> next = p_stack; / * NEXT of the new node point to the original stack top * / p_stack = stack; / * Stack top pointer points New node * /
Free (stack); / * Release the stack of memory * / stack = null; return true;} else {returnaf false;}}
/ * ============================== function: out of the stack returns: out of the stack element ========= ============================== * / Node Pop () {Node P;
IF (! EMPTY ()) {p = p_stack-> data; / * Find element * / p_stack = p_stack-> next; / * Change the stack top pointer * / return p;} else {printf ("stack is empty! / n ");}}
Void main (void) {node node1 = {3, 1, 2}; push (node1); Printf ("n =% D, x =%. 2F, y =%. 2f / n", (p_stack-> data ) .n, (p_stack-> data) .x, (p_stack-> data) .y);
POP (); / * According to the following statement results, we can judge whether the above-implemented stacks are correct: 1 correct, other errors. * / Printf ("% D", p_stack == null); Printf ("/ n"); system ("pause");}
