【C语言/数据结构】栈：从概念到两种存储结构的实现

---

目录

一、栈的概念

二、栈的两种实现方式

1.顺序表实现栈

2.链表实现栈

三、栈的顺序存储结构及其实现

1.栈的声明

2.栈的初始化

3.栈的销毁

4.栈的压栈

5.栈的弹栈

6.栈的判空

7.返回栈顶元素

8.返回栈的长度

四、栈的链式存储结构及其实现

1.栈的声明

2.栈的初始化

3.栈的销毁

4.栈的压栈

5.栈的弹栈

6.栈的判空

7.返回栈顶元素

8.返回栈的长度

---

一、栈的概念

• 栈的定义：栈是一种特殊的线性表；但在概念上又有一些规定，栈只允许在一端进行数据的插入与删除的操作，被称为栈顶，而另一端则被称为栈底
• 出栈（弹栈）：在栈顶进行数据的删除
• 入栈（压栈）：在栈底进行数据的插入      
• LIFO原则：栈中的index.php/tags-301.html" >数据服从后进先出原则（last in first out）

  二、栈的两种实现方式

  1.顺序表实现栈

  • 设计思路：将数组下标为0的位置作为栈底，而数组的最大下标（即长度减一）作为栈顶元素可能存在的位置；用top指向栈顶元素下一位置的索引
  • 压栈：栈的压栈操作，即为顺序表的尾插
  • 弹栈：栈的弹栈操作，即为顺序表的尾删
  • 设计优势：避免了数组增加删除数据时候需要移动数据；压栈与弹栈的时间复杂度为O(1)
  • 自身优势：缓冲区的利用率高；用一段连续的物理地址来存储数据
  • 缺点：动态顺序表实现的栈需要扩容，而扩容会导致空间浪费或性能消耗

    2.链表实现栈

    • 设计思路：将单链表的尾部作为栈底，将链表的头部作为栈顶；链表的头指针指针栈顶元素的位置
    • 压栈：栈的压栈操作，即为链表的头插
    • 弹栈：栈的弹栈操作，即为链表的头删
    • 设计优势：避免了链表删除数据结点的时候，需要找到该结点的前一个结点；压栈与弹栈的时间复杂度为O(1)
    • 自身优势：没有扩容所带来的空间的浪费与性能的消耗
    • 缺点：缓存利用率不如顺序表高

      三、栈的顺序存储结构及其实现

      1.栈的声明

      #pragma once#include#include#include#include#include#define STDateType int typedef struct Stack{STDateType* date;int top;int capacity;}ST;void STInit(ST* st);void STDestory(ST* st);void STPush(ST* st, STDateType x);void STPop(ST* st);STDateType STTop(ST* st);bool STEmpty(ST* st);int STSize(ST* st);

      2.栈的初始化

      void STInit(ST* st){assert(st);st->date = NULL;st->capacity = st->top = 0;}

      3.栈的销毁

      void STDestory(ST* st){assert(st);free(st->date);st->date = NULL;st->top = 0;st->capacity = 0;}

      4.栈的压栈

      void STPush(ST* st, STDateType x){assert(st);if (st->top == st->capacity){size_t newcapacity = (st->capacity == 0 ? 4 : 2 * st->capacity);STDateType* tmp = (STDateType*)realloc(st->date, sizeof(STDateType) * newcapacity);if (tmp != NULL){st->date = tmp;st->capacity = newcapacity;}}st->date[st->top++] = x;}

      5.栈的弹栈

      void STPop(ST* st){assert(st);assert(st->top > 0);st->top--;}

      6.栈的判空

      bool STEmpty(ST* st){assert(st);return st->top == 0;}

      7.返回栈顶元素

      STDateType STTop(ST* st){assert(st);assert(st->top > 0);return st->date[st->top - 1];}

      8.返回栈的长度

      int STSize(ST* st){assert(st);return st->top;}

      四、栈的链式存储结构及其实现

      1.栈的声明

      #pragma once#include#include#include#include#includetypedef int StDateType;typedef struct StackNode{StDateType date;struct StackNode* next;}StackNode;typedef struct Stack{StackNode* top;size_t size;}Stack;void StackInit(Stack* st);//初始化void StackDestory(Stack* st);//销毁void StackPush(Stack* st, StDateType x);//压栈void StackPop(Stack* st);//弹栈StDateType StackTop(Stack* st);//读取栈顶元素bool StackEmpty(Stack* st);//判空size_t StackSize(Stack* st);//返回栈的长度

      2.栈的初始化

      void StackInit(Stack* st){assert(st);st->top = NULL;st->size = 0;}

      3.栈的销毁

      void StackDestory(Stack* st){assert(st);while (st->size > 0)StackPop(st);}

      4.栈的压栈

      void StackPush(Stack* st, StDateType x){assert(st);StackNode* Node = (StackNode*)malloc(sizeof(StackNode));if (!Node){perror("malloc mistake");exit(-1);}Node->date = x;Node->next = NULL;Node->next = st->top;st->top = Node;st->size++;}

      5.栈的弹栈

      void StackPop(Stack* st){assert(st);assert(st->top);    StackNode* tmp = st->top;      st->top = st->top->next;      free(tmp);      st->size--;  }

      6.栈的判空

      bool StackEmpty(Stack* st){assert(st);return st->top == NULL;}

      7.返回栈顶元素

      StDateType StackTop(Stack* st){assert(st);return st->top->date;}

      8.返回栈的长度

      size_t StackSize(Stack* st){    assert(st);    assert(st->top);return st->size;}