数据结构与算法—栈

1. 栈的定义

栈，也叫堆栈，是最常用也是最重要的数据结构之一。
栈(Stack)是限定仅在表的一端进行插入或删除操作的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。
栈操作的特点：后进先出，先进后出。
因此，栈称为后进先出表（LIFO, Last In First Out）。

示意图：

2. 栈的基本运算

初始化栈InitStack(*S)
压栈Push(*S,x) ——在栈顶插入元素
出栈Pop(*S,x) ——在栈顶删除元素
取栈顶元素GetTop(S,x)
判栈空Empty(S)

栈的几种状态（最大长度MaxSize为4）：栈空、压栈、栈满、出栈

3. 栈的存储结构

栈有两种表示方法: 顺序存储 和 链式存储

3.1 顺序栈

采用顺序存储结构的栈简称为顺序栈。是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设整型变量top指示栈顶元素在顺序栈中的位置。

    // 顺序栈数据类型的C语言描述如下：
    #define MaxSize 100
    typedef int DataType;
    typedef struct {
              DataType data[MaxSize];
              int top;
    }Stack;
    
    // top:栈顶指针。取值范围为0～MaxSize-1。
    // top==-1表示栈空，top==MaxSize-1表示栈满。

    // 初始化栈InitStack(S)
     int InitStack(Stack *S) 
     { 
         S->top=-1; 
         return 1;
     } 
    
    // 压栈Push(S,x)
    int Push(Stack *S,DataType x)
    {
        if(S->top==MaxSize-1)
        {
             printf("\n Stack is full!"); 
            return 0;
        }
          S->top++;
          S->data[S->top]=x;
          return 1; 
    }
    
    // 判栈空EmptyStack(S)
    int EmptyStack(Stack *S)
    { 
        return (S->top==-1?1:0);
    }
    
    // 出栈Pop(S,x)
    int Pop(Stack *S,DataType *x)     
    { 
        if(EmptyStack(S))
        {   
              printf("\n Stack is free!"); 
               return 0;
        }
       *x=S->data[S->top];//记住要删除的元素值
           S->top--;
           return 1;
    }
    
    // 取栈顶元素GetTopStack(S)
    DataType GetTop(STACK *S)   
    {  
        DataType x;
        if(EmptyStack(S))
        {   
              printf("\n Stack is free!"); 
            exit(1);
        }
           x=S->data[S->top];
           return x;
    }

View Code

3.1 链栈：栈的链式存储结构

链栈结构示意图：

top栈顶指针，惟一的确定一个链栈。链栈通常带有一个表头结点，所以top->next才指示栈顶元素。

    //  链栈的C语言描述如下：

    typedef struct node
    {
        ElemType data;
        struct node *next;
    }Stack;

    Stack * InitStack() 
    {
        Stack *top;
        top=(Stack *)malloc(sizeof(Stack));
        top->next=NULL;
        return top;
    }
    //进栈
    int Push(Stack *top,Pos x) 
    {
        Stack *s;
        s=(Stack *)malloc(sizeof(Stack));
        if(!s) //当s==NULL return 0
            return 0;
        s->data=x; 
        s->next=top->next; //新申请空间的指针域保存上一个结点的地址
        top->next=s;  //头指针域保存新结点地址
        return 1;
    }
    //判断栈空
    int EmptyStack(Stack *top) 
    {
        if(top->next==NULL)
            return 1;
        else
            return 0;
    }
    //出栈
    int Pop(Stack *top,Pos *e) 
    {
        Stack *s;
        if(EmptyStack(top))
            return 0;
        s=top->next;  //取第一个结点的地址
        *e=s->data;   //返第一结点数据
        top->next=s->next; //头结点指针域存第二结点地址
        free(s);
        return 1;
    }
    
    //取栈顶元素
    int GetTopStack(Stack *top,Pos *e)
    {
        Stack *s;
        if(EmptyStack(top))
            return 0;
        s=top->next;
        *e=s->data;
        return 1;
    }

View Code

Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。

它的内容包括：

大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw

目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：

想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询

同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】即可免费领取。

阅读全文