博客

下边的实现，默认在链栈中设置一个头结点，用于指向栈的第一个元素

链栈结构体定义

typedef char DataType;
typedef struct node{
    DataType data;
    struct node *next;        
}LStackNode,*LinkStack;
 
 

• 1
• 2
• 3
• 4
• 5

• 1
• 2
• 3
• 4
• 5

链栈算法实现

void InitStack(LinkStack *top){
     // 为头结点分配存储单元
     if((*top=(LinkStack)malloc(sizeof(LStackNode)))==NULL){
         exit(-1);  
     }
     // 将头结点的指针域置为空
     (*top)->next = NULL;
}
// 判断栈是否为空
int StackEmpty(LinkStack top){
    if(top->next == NULL){
         return 1;
    }else{
         return 0;      
    }
}
// 将元素入栈：需要为入栈的结点分配内存
int PushStack(LinkStack top,DataType e){
    LStackNode *p;
    if((p=(LStackNode*)malloc(sizeof(LStackNode)))==NULL){
         printf("内存分配失败\n");
         return 0;
    }
    p->data = e;
    p->next = top->next;
    top->next = p;
    return 1;
}
// 将元素出栈：需要释放结点空间
int PopStack(LinkStack top,DataType *e){
    LStackNode *p;
    p = top->next;
    if(!p){
         printf("栈已空\n");
         return 0; 
    }
    top->next = p->next;
    *e = p->data;
    free(p);
    return 1;
}
// 取栈顶元素：需要对边界做判断（栈是否为空）
int GetTop(LinkStack top,DataType *e){
    LStackNode *p;
    p = top->next;
    if(!p){
         printf("栈已空\n");
         return 0; 
    }
    *e = p->data;
    return 1;
}
// 获取栈长度：因为需要头结点，依次寻找下一个结点，所以时间复杂度为：O(n)
int StackLength(LinkStack top){
    int i=0;
    LStackNode *p;
    p = top;
    if(p->next!=NULL){
         p = p->next;             
         i++;
    }
    return i;
}
// 销毁链栈：需要释放动态分配的结点空间
void DestoryStack(LinkStack top){
     LStackNode *p,*q;
     p = top;
     while(!p){
          q = p;
          p = p->next;
          free(q);
     }
}
 
 

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73

应用

1 进制转换：例如十进制转八进制，不断除以8，保存余数，直到商为0，从下往上取余数。可以使用栈保存余数，再依次取出


2 括号配对：假如是括号的左边，就入栈；当遇到括号的右边，就出栈一个元素，比较是否配对；配对就继续上一步，不配对就退出