数据结构------栈

?个人主页：我的主页
?小白一枚，欢迎指教?

• 注：数据结构三要素----逻辑结构，数据的运算，存储结构（物理结构）存储结构不同，运算的实现方式就不同

一、栈的定义：

栈（stack）是只允许在一端进行插入或删除操作的线性表。是一种特殊的线性表，但是只能在某一端进行插入或删除操作。

1、重要的术语

• 栈顶(Top)：线性表只允许进行插入和删除的那一端

• 栈底(Bottom)：固定的，不允许进行插入和删除的另一端

• 空栈：不含任何元素的空表

  

（上图元素等进栈顺序为：a1->a2->a3->a4->a5）

（出栈顺序为：a5->a4->a3->a2->a1）

• TIP:特点是后进先出 Last In First Out (LIFO)

2、栈的基本操作：

3、栈的常考题型：

• 有哪些合法的出栈顺序？

例如：a->b->c->d->e。有哪些合法的出栈顺序？

1. e、d、c、b、a 所有的元素都进栈以后再出
2. 一边进栈，一边出栈

4、总结：

二、顺序栈

1、顺序栈的定义：

 #define MaxSize 10. //定义栈中元素的最大个数
  typedef struct{
     ElemType data[MaxSize];  //静态数组存放栈中的元素
      int top;       //栈顶指针
  } SqStack;      //sq->代表sequence 顺序
 
void testStack(){
  SqStack S; //声明一个顺序栈，分配空间
  //...后续操作..
}

2、初始化操作：

3、进栈操作：（插入）

4、出栈（删除）：

5、读栈顶元素：

（注意与出栈操作的区别）

三、共享栈：（两个栈共享同一片空间）

• 判断栈满 ：top0+1==top1

• 回收：