栈(stack)--c实现(使用双链表)

  1 #include 
  2 
  3 
  4 typedef struct node
  5 {
  6     int data;
  7     struct node* next;
  8     struct node* pre;
  9 }Node;
 10 
 11 //Stack 一直指向栈顶
 12 typedef Node* Stack;
 13 
 14 void InitStack(Stack* stack);
 15 void DeleteStack(Stack* stack);
 16 int TopStack(Stack*);
 17 void PushStack(Stack* stack, int elem);
 18 int PopStack(Stack *stack);
 19 int IsNull(Stack*);
 20 void PrintStack(Stack *);
 21 
 22 void PrintStack(Stack *stack)
 23 {
 24     Node* preNode = *stack;
 25     while((preNode->pre != NULL)
 26           &&preNode)
 27     {
 28         printf("%d", preNode->data);
 29         preNode = preNode->pre;
 30         if(preNode->pre != NULL){
 31             printf("<==");
 32         }
 33     }
 34     printf("\n");
 35 
 36 }
 37 //1 means NULL
 38 //stack-->node-->datamem
 39 //这个地方第一次写传的是Stack stack，为什么报错？因为穿的是值，就是一个copy，pre不能确定一定是NULL
 40 int IsNull(Stack *stack)
 41 {
 42      return ((*stack)->pre == NULL);
 43 }
 44 
 45 int PopStack(Stack *stack)
 46 {
 47     if(IsNull(stack))
 48     {
 49         printf("empty stack.\n");
 50         return -1;
 51     }
 52     int popData = -1;
 53     popData = (*stack)->data;
 54     Node* popNode = NULL ;
 55     popNode = *stack;
 56     *stack = (*stack)->pre;
 57     (*stack)->pre = popNode->pre->pre;
 58     (*stack)->next = NULL;
 59 
 60     popNode->pre->pre->next = (*stack);
 61 
 62     free(popNode);//warning
 63 
 64     return popData;
 65 }
 66 void InitStack(Stack* stack)
 67 {
 68     (*stack)->next = NULL;
 69     (*stack)->pre = NULL;
 70     (*stack)->data = -1;
 71     return ;
 72 }
 73 
 74 int TopStack(Stack *stack)
 75 {
 76     return (*stack)->data;
 77 }
 78 
 79 void PushStack(Stack *stack, int elem)
 80 {
 81     //Node *pushNode = (Node*)malloc(sizeof(Node));
 82     Node *pushNode = (Node*) malloc(sizeof(Node));//warning
 83     if(pushNode == NULL)
 84      {
 85          printf("malloc error at line %d.", __LINE__);
 86          return;
 87      }
 88 
 89     pushNode->data = elem;
 90     pushNode->next = NULL;
 91     pushNode->pre = *stack;
 92     (*stack)->next = pushNode;
 93     *stack = (*stack)->next;
 94 
 95 }
 96 
 97 void DeleteStack(Stack* stack)
 98 {
 99 
100     Node* preNode = stack;
101     while((*stack)->pre != NULL)
102     {
103         PopStack(stack);
104 
105     }
106     free(*stack);
107 
108     return ;
109 }
110 
111 
112 int main(void)
113 {
114     printf("Hello World!\n");
115     Stack *stack =NULL;
116     stack = (Stack*)malloc(sizeof(stack));//warning
117     *stack = (Node*)malloc(sizeof(Node));
118     InitStack(stack);
119     IsNull(stack);
120     printf("isNull=[%d]\n", IsNull(stack));
121     printf("the top ele is [%d]\n", (*stack)->data);
122     printf("push elem  1, 2, 3, 4, 3\n");
123     PushStack(stack, 1);
124     PrintStack(stack);
125     PushStack(stack, 2);
126     PushStack(stack, 3);
127     PushStack(stack, 4);
128     PushStack(stack, 3);
129     printf("print the curr stack.\n");
130     PrintStack(stack);
131     printf("Pop the stack and print the curr stack.\n");
132     PopStack(stack);
133     PrintStack(stack);
134 
135     printf("the top elem is %d\n", TopStack(stack));
136 
137 
138     return 0;
139 }