2023考研408数据结构备考知识点：栈（上）

今天小编为大家整理了2023考研408数据结构知识点之栈的相关介绍，从栈的定义、栈的核心问题、对顶栈等方面为大家做详细的介绍，助力大家更好地备考，提高备考效率，顺利进入理想院校。

1：栈的定义

栈：只允许存表的一端(栈项)进行插入或删除的线性表。栈的操作特性为后进先出(LIFO)，故又称后进先出的线性表

2：栈的出栈情形计算

给定n个元素依次进栈，虽然进栈顺序是一定的，但是出栈顺序不确定，因为在进栈后，可以随时做出栈操作，出栈的顺序一共有多少种呢?对应的公式, 给定n个元素，出栈的顺序的情形满足卡特兰数，计算公式是：

3：顺序栈的进栈和出栈的表达式

一般我们讨论是，都是用A[0,…,n-1]的数组进行存储，且初始时top = bottom = 0;

进栈：

出栈：

4：栈的核心问题

一般我们讨论是，都是用A[0,…,n-1]的数组进行存储，且初始时top = bottom = 0;

(1)什么时候栈空? top = bottom;

(2)如何进栈?

(3)如何出栈?

(4)栈底指针指向哪里?bottom始终指向0的位置;

(5)栈顶指针指向哪里?top始终指向栈顶元素的下一个空位置;

(6)什么时候栈满? top-bottom >= n;

(7)栈中元素有几个? top个;

5：对顶栈

假如有两个顺序栈，我们可以让两个栈共享同一片存储空间，将两个栈的栈底在这片存储空间的两端，当元素入栈时，两个栈的栈顶指针相向而行，这样的栈叫做对顶栈。

当|t1-t2| == 1时，表示共享栈满,其中t1和t2表示两个栈的栈顶。

6：链栈的插入和删除

大家只需要理解并掌握一点，链栈是头出头插的单链表。具体实现上有两种情况：

(1)带头结点的单链表方式：假设头指针为top;工作指针是p

入栈：p-> next = top-> next ; top->next = p;

出栈：p = top-> next ; top->next = p ->next; return p;

(2)不带头结点的单链表方式: 假设头指针为top;工作指针是p

入栈：p - >next = top ; top = p;

出栈：p = top; top = top ->next; return p;