数据结构的概念大合集03（栈）

1、栈

1.1 栈的定义和特点

       栈是一种只能在一端进行插入或删除操作的线性表。在栈中，允许插入和删除操作的一端称为栈顶，另一端称为栈底。当栈为空时，称为空栈。栈的插入操作称为进栈或入栈，删除操作称为出栈退栈。

       栈的特点是“后进先出”，即后进栈的元素先出栈，英文表示为“last in first out，即LIFO”

1.2 栈的基础操作

函数名	函数作用
InitStack(&s)	初识化线性表，构造一个空列表
DestroyStack(&s)	销毁线性表，释放为线性表L分配的内存空间
StackEmpty(s)	判断线性表是否为空表，若L为空表，则返回true，否则返回false
Push(&s,e)	进栈，将元素e插入栈中作为栈顶元素
Pop(&s,&e)	出栈，从栈s中删除栈顶元素，并将其赋值给e
GetTop(s,&e)	取栈顶元素，返回当前的栈顶元素，并将其赋值给e。

1.3 栈的顺序存储

1.3.1 顺序栈

       同线性表一样，栈里面的元素也可以采用顺序存储结构，即分配一块连续的存储空间来存放栈中的元素，并用一个变量（例如top）指向当前的栈顶元素，以反映栈中元素的变化。这种采用顺序结构的栈称为顺序栈。

1.3.2 栈空，栈满，进栈，出栈的基本思想

• 栈空：s->top == -1。
• 栈满：s->top == MaxSize - 1 (data数组的最大下标)。
• 进栈：先将栈顶指针top增1，然后将元素e放在栈顶指针处。
• 出栈：现将栈顶指针top处元素取出放在e中，然后将栈顶指针减1.
  

1.3.3 共享栈

       顺序栈的一种特殊表现形式，将两个类型相同的栈结合起来，这样可以避免栈溢出或内存浪费的情况。
       在设计共享栈的时候，由于一个数组（大小为MaxSize）有两端点，两个栈有两个栈底，让一个栈的栈底为数组的是始端，即下表为0处，另一个栈的栈底的为数组的末端，即下表为MaxSize-1处，这样，在两个栈中进栈元素时，栈顶向中间伸展。

1.3.3.1 共享栈的4要素

• 栈空：栈1为空top == -1;栈2为空top2 == MaxSize。
• 栈满：top1 == top2-1。
• 进栈：栈1进栈top1++ ; data[top1] = x; ==> data[++top1] = x;
             栈2进栈top-- ; data[top2] = x; ==> data[–top] = x;
• 出栈：栈1出栈x = data[top1];top-- ; ==> x = data[top1–];
             栈2出栈x = data[top2] ; top2++; ==> x = data[top2++];

1.4 栈的链式存储

       即采用链式存储的栈称为链栈，但是与链表不同的是，链栈只有单链栈，不存在双链栈，所以将单链栈也直接称为链栈。

1.4.1 链栈的实现

       采用带头结点的单链表来实现栈链

1.4.2 链栈的4个要素

• 栈空：s->next == NULL;
• 栈满：因为是链栈，只有在内存溢出的情况下，才会出现满栈的情况，所以一般情况不考虑；
• 进栈：新建一个结点存放元素e（由p指向它），将结点p插入头结点之后。
• 出栈：取出首结点的data值并将其删除

注：
本文将主要探讨栈的概念，其中提及的各个函数操作将在后续的文章中详细展示，敬请读者期待。
上一篇文章
数据结构的概念大合集02（线性表）
下一篇文章
数据结构的概念大合集04（队列）