严蔚敏关于栈的代码

  1 * 栈基本操作 
  2 * 08/25/2010 
  3 * 参考自严蔚敏等《数据结构(C语言版)》清华大学出版社 
  4 */ 
  5 #include <iostream> 
  6 #include <stdlib.h> 
  7 #include <assert.h> 
  8 using namespace std; 
  9 
 10 // constant definition 
 11 static const int STACK_INIT_SIZE = 10; // the size of initial 
 12 static const int STACK_INCREMENT = 10; // the size of each increase 
 13 
 14 // describe the stack 
 15 typedef struct _STACK{ 
 16 int *bottom; 
 17 int *top; 
 18 int size; 
 19 }STACK, *PSTACK; 
 20 
 21 // construct an empty stack 
 22 void stack_init(STACK &stack) 
 23 { 
 24 stack.bottom = (int *) malloc(STACK_INIT_SIZE * sizeof(int)); 
 25 assert(stack.bottom != NULL); 
 26 stack.top = stack.bottom; 
 27 stack.size = STACK_INIT_SIZE; 
 28 } 
 29 
 30 // push an element in the stack as the new top 
 31 void stack_push(STACK &stack, int element) 
 32 { 
 33 if((stack.top - stack.bottom) >= stack.size) 
 34 { 
 35 // stack is full, allocate more memory 
 36 stack.bottom = (int *) realloc(stack.bottom, (STACK_INIT_SIZE + 
 37 STACK_INCREMENT) * sizeof(int)); 
 38 assert(stack.bottom != NULL); 
 39 stack.top = stack.bottom + stack.size; 
 40 stack.size += STACK_INCREMENT; 
 41 } 
 42 
 43 *stack.top++ = element; 
 44 cout << "push " << element << endl; 
 45 } 
 46 
 47 // pop the top element in stack if the stack is not empty 
 48 void stack_pop(STACK &stack, int &element) 
 49 { 
 50 if(stack.top == stack.bottom) 
 51 { 
 52 // stack is empty, can not pop stack 
 53 cout << "ERROR - pop: stack is empty" << endl; 
 54 return ; 
 55 } 
 56 
 57 element = *(--stack.top); 
 58 cout << "pop " << element << endl; 
 59 } 
 60 // get the top element if stack is not empty 
 61 void stack_top(const STACK stack, int &element) 
 62 { 
 63 if(stack.top == stack.bottom) 
 64 { 
 65 cout << "ERROR - top: stack is empty" << endl; 
 66 element = -1; 
 67 return; 
 68 } 
 69 
 70 element = *(stack.top - 1); 
 71 cout << "top " << element << endl; 
 72 } 
 73 
 74 // retrieve the number of elements in stack 
 75 int stack_length(const STACK stack) 
 76 { 
 77 return (int)(stack.top - stack.bottom); 
 78 } 
 79 
 80 // determine whether the stack is empty 
 81 bool stack_is_empty(const STACK stack) 
 82 { 
 83 return (stack.top - stack.bottom) ? false : true; 
 84 } 
 85 // destroy the stack and the stack is not exist in memory any more 
 86 void stack_destroy(STACK &stack) 
 87 { 
 88 if(stack.bottom) free(stack.bottom); 
 89 stack.bottom = stack.top = NULL; 
 90 cout << "destroy ok" << endl; 
 91 } 
 92 
 93 // clear all elements in stack 
 94 void stack_clear(STACK &stack) 
 95 { 
 96 stack.top = stack.bottom; 
 97 } 
 98 
 99 // traverse the stack and print all elements from top to bottom 
100 void stack_print(const STACK stack) 
101 { if(stack_is_empty(stack)) 
102 { 
103 cout << "stack is empty" << endl; 
104 return ; 
105 } 
106 cout << "(top) "; 
107 int *p = stack.top; 
108 while(p != stack.bottom) 
109 { 
110 cout << *(--p) << " "; 
111 } 
112 cout << *p << " (bottom)" << endl; 
113 } 
114 // start from here 
115 int main() 
116 { 
117 STACK stack; 
118 stack_init(stack); 
119 
120 int i, j; 
121 for(i=0; i<15; i++) 
122 stack_push(stack, i); 
123 stack_print(stack); 
124 cout << "length " << stack_length(stack) << endl; 
125 for(j=0; j<16; j++) 
126 stack_pop(stack, i); 
127 stack_print(stack); 
128 
129 if(stack_is_empty(stack)) cout << "stack is empty" << endl; 
130 else cout << "stack is not empty" << endl; 
131 
132 stack_clear(stack); 
133 stack_destroy(stack); 
134 
135 system("PAUSE"); 
136 return 0; 
137 }