Data Structures Notes — Stack Data Structures Notes — Stack

1 栈和队的基本概念

1.1.1 栈的基本概念

1. 栈的定义

栈是一种线性数据结构，其数据的插入与删除操作仅能发生在特定的一端。该端被称为栈顶（top），通常由一个动态变化的指针来标识，称为栈顶指针。而线性表的另一端则被定义为栈底，其位置是固定的。数据的插入操作称为入栈，而数据的删除操作则被称为出栈。

2. 栈的特点

栈遵循先进后出的原则。这种特性类似于将盘子依次叠放成一列的情形，先放入的盘子位于底部，后放入的盘子处于顶部。在取出时，总是先取最顶端的那个盘子。

3. 栈的存储结构

根据存储方式的不同，栈可以采用顺序表或链表进行存储。因此，依据存储结构的区别，可将栈分为顺序栈与链式栈两种类型。

4. 栈的数学性质

当有n个元素按照某种顺序依次进入栈中，并且在任意时刻都可以进行出栈操作（前提是遵循先进后出的原则），那么最终可能得到的不同排列数目N恰好符合Catalan()函数所描述的结果。

1.2 栈的储存结构、算法和应用

1.2.1 栈的结构体定义

1. 顺序栈的定义

 typedef struct

    
 {
    
     int data[MaxSize]; //MaxSize为已被定义的const常量；
    
     int top； //栈顶指针
    
 }sqStack；