数据结构之栈

Bertha 。 2022-05-16 14:29 229阅读 0赞

# 什么是栈 #

从栈的操作特性上来看，栈是一种 “操作受限”的线性表，只允许在一端插入和删除数据，且满足先进后出、后进先出的特性。

# 实现一个栈 #

栈可以用数组或链表来实现，数组实现的叫顺序栈，链表实现的叫链式栈。

# 栈的时间复杂度 #

入栈与出栈的时间复杂度均为O(1)

# 动态扩容的顺序栈 #

与数组动态扩容类似，用数组实现的栈也可以动态扩容。申请一个扩容后的内存区域将数组迁移过去。

# 栈的应用 #

1.  函数调用存储局部变量
2.  表达式的求值
3.  括号匹配
4.  浏览器前进后退

# 栈的实现（使用c语言数组实现） #

#include<stdbool.h>
    #define maxsize 100
    typedef int datatype;
    
    typedef struct { 
     datatype s[maxsize];
     int index;
    } Stack;
    
    Stack stack;
    
    void initStack() { 
     stack.index = -1;
    }
    
    bool empty() { 
     if(stack.index == -1){ 
      printf("empty\n");
      return true;
     }else{ 
      return false;
     }
    }
    
    bool full(){ 
     if(stack.index == maxsize-1){ 
      printf("full\n");
      return true;
     }else{ 
      return false;
     }
    }
    
    bool push(datatype data){ 
     if(stack.index == maxsize-1){ 
      printf("full\n");
      return false;
     }else{ 
      stack.index++;
      stack.s[index] = data;
      return true;
     }
    }
    
    bool pop(){ 
     if(stack.index == -1){ 
      printf("empty\n");
      return false;
     }else{ 
      stack.index--;
      return true;
    }
    
    datatype popValue(){ 
     if(stack.index == -1){ 
      printf("empty\n");
     }else{ 
      return stack.s[stack.index];
     }
    }

# 栈的实现（使用c语言链表实现） #

#include<stdbool.h>
    
    typedef int datatype
    
    struct stack { 
            datatype data;
            struct stack *next;
    }
    
    struct stack *s;
    #include<stdbool.h>
    
    typedef int datatype;
    
    struct stack { 
            datatype data;
            struct stack *next;
    };
    
    struct stack *s;
    
    void initStack() { 
            s=NULL;
    }
    
    bool empty() { 
            if(s == NULL) { 
                    printf("empty\n");
                    return true;
            } else { 
                    return false;
            }
    }
    
    bool empty() { 
            if(s == NULL) { 
    }
    }
    
    bool empty() { 
            if(s == NULL) { 
                    printf("empty\n");
                    return true;
            } else { 
                    return false;
            }
    }
    
    void push(datatype newData) { 
            (struct stack *newNode) = (struct stack *) malloc(sizeof(struct stack));
            newNode->data = newData;
            newNode->next = s;
            s = newNode
    }
    
    void pop() { 
            if(!empty()) { 
                    s = s->next;
            } else { 
                    printf("pop failed!\n");
            }
    }
    
    datatype popValue() { 
            if(!empty()) { 
                    return s->data;
            } else { 
                    printf("popValue failed!\n");
            }
    }