考研408数据结构(栈与队列)

目录顺序栈基本概念核心特性代码实现共享栈基本概念核心特性代码实现链栈基本概念链栈的核心特性代码实现带头结点的链栈不带头结点的链栈顺序栈基本概念顺序栈是一种基于数组实现的栈结构利用连续的内存空间存储数据遵循“后进先出”LIFO原则。栈顶指针通常为top动态指向当前栈顶元素的位置支持压栈push和弹栈pop操作。核心特性存储结构通过数组实现需预先分配固定大小的内存空间。栈顶指针初始值为-1空栈插入元素时top递增删除时递减。时间复杂度压栈和弹栈操作的时间复杂度均为O(1)。代码实现#include stdio.h // 考研标准栈的最大容量可根据题目修改 #define MaxSize 50 // 顺序栈结构体定义考研必考写法 typedef struct { // 静态数组存放栈元素 int data[MaxSize]; // 栈顶指针指向栈顶元素考研最常用定义方式 int top; } SqStack; // 1. 初始化栈核心 void InitStack(SqStack *S) { // 栈顶指针置为-1表示空栈 S-top -1; } // 2. 判断栈是否为空 int StackEmpty(SqStack S) { // 栈顶为-1 → 空栈返回1否则返回0 return S.top -1; } // 3. 判断栈是否为满 int StackFull(SqStack S) { // 栈顶指向最后一个元素 → 栈满返回1 return S.top MaxSize - 1; } // 4. 入栈操作进栈 int Push(SqStack *S, int e) { // 栈满入栈失败 if (StackFull(*S)) return 0; // 栈顶指针先1再赋值 S-data[S-top] e; // 入栈成功 return 1; } // 5. 出栈操作删除栈顶元素用e返回值 int Pop(SqStack *S, int *e) { // 栈空出栈失败 if (StackEmpty(*S)) return 0; // 先取栈顶元素栈顶指针再-1 *e S-data[S-top--]; // 出栈成功 return 1; } // 6. 取栈顶元素不删除 int GetTop(SqStack S, int *e) { // 栈空取元素失败 if (StackEmpty(S)) return 0; *e S.data[S.top]; // 取元素成功 return 1; } // 7. 销毁栈静态栈无需free仅重置指针即可 void DestroyStack(SqStack *S) { S-top -1; } // 主函数测试栈的所有操作考研答题可写可不写建议写上 int main() { // 定义一个栈 SqStack S; // 初始化栈 InitStack(S); // 测试入栈 Push(S, 10); Push(S, 20); Push(S, 30); printf(入栈元素10,20,30\n); // 测试取栈顶 int topElem; GetTop(S, topElem); printf(当前栈顶元素%d\n, topElem); // 测试出栈 int e; Pop(S, e); printf(出栈元素%d\n, e); GetTop(S, topElem); printf(出栈后栈顶元素%d\n, topElem); // 测试判空 if (StackEmpty(S)) printf(栈为空\n); else printf(栈不为空\n); // 销毁栈 DestroyStack(S); return 0; }共享栈基本概念共享栈是一种利用同一块内存空间实现两个栈的数据结构。两个栈的栈底分别位于共享内存空间的两端栈顶向中间生长。当两个栈顶相遇时表示栈空间已满。核心特性空间高效利用共享栈通过让两个栈共享同一块内存区域避免了单独分配两块内存可能导致的浪费。尤其当两个栈的实际使用空间动态变化时能更灵活地利用内存。双向生长两个栈的栈顶分别从数组的两端向中间延伸。栈A从下标0开始向高位生长栈B从下标n-1开始向低位生长。溢出条件共享栈的溢出条件为两个栈顶相遇即top1 1 top2。此时无论向哪个栈压入元素都会导致栈满。代码实现#include stdio.h #include stdlib.h // 共享栈最大容量可根据需求修改 #define MaxSize 10 // 共享栈结构体定义408标准写法 typedef struct { // 共享存储空间 int data[MaxSize]; // 栈1栈顶指针 int top1; // 栈2栈顶指针 int top2; } ShareStack; // 基本操作 // // 1. 初始化共享栈 void InitStack(ShareStack *S) { // 栈1空栈状态 S-top1 -1; // 栈2空栈状态 S-top2 MaxSize; } // 2. 判断共享栈是否为空 // flag1 判栈1空flag2 判栈2空 int StackEmpty(ShareStack S, int flag) { if (flag 1) { // 栈1空返回1 return S.top1 -1; } else if (flag 2) { // 栈2空返回1 return S.top2 MaxSize; } // 非法标记 return -1; } // 3. 判断共享栈是否满 int StackFull(ShareStack S) { // 标准判满条件 return S.top1 1 S.top2; } // 4. 入栈操作 // flag1 入栈1flag2 入栈2 int Push(ShareStack *S, int flag, int e) { // 栈满入栈失败 if (StackFull(*S)) { printf(共享栈已满入栈失败\n); return 0; } if (flag 1) { // 栈1先移动指针再入栈 S-data[S-top1] e; } else if (flag 2) { // 栈2先移动指针再入栈 S-data[--S-top2] e; } else { printf(栈编号错误\n); return 0; } return 1; } // 5. 出栈操作 // flag1 出栈1flag2 出栈2e保存出栈元素 int Pop(ShareStack *S, int flag, int *e) { if (flag 1) { // 栈1空 if (S-top1 -1) { printf(栈1为空出栈失败\n); return 0; } // 先出栈再移动指针 *e S-data[S-top1--]; } else if (flag 2) { // 栈2空 if (S-top2 MaxSize) { printf(栈2为空出栈失败\n); return 0; } // 先出栈再移动指针 *e S-data[S-top2]; } else { printf(栈编号错误\n); return 0; } return 1; } // 6. 获取栈顶元素不删除 int GetTop(ShareStack S, int flag, int *e) { if (flag 1) { if (S.top1 -1) return 0; *e S.data[S.top1]; } else if (flag 2) { if (S.top2 MaxSize) return 0; *e S.data[S.top2]; } else return 0; return 1; } // 测试主函数 // int main() { ShareStack S; // 初始化 InitStack(S); int e; // 栈1入栈 Push(S, 1, 10); Push(S, 1, 20); Push(S, 1, 30); // 栈2入栈 Push(S, 2, 100); Push(S, 2, 200); // 栈1出栈 Pop(S, 1, e); printf(栈1出栈元素%d\n, e); // 栈2出栈 Pop(S, 2, e); printf(栈2出栈元素%d\n, e); // 获取栈顶 GetTop(S, 1, e); printf(栈1栈顶元素%d\n, e); GetTop(S, 2, e); printf(栈2栈顶元素%d\n, e); return 0; }链栈基本概念链栈是一种基于链表实现的栈结构采用动态内存分配方式存储数据。与顺序栈不同链栈无需预先定义固定容量通过节点间的指针链接实现元素的入栈和出栈操作。链栈的栈顶通常为链表的头节点操作均在链表头部完成保证时间复杂度为O(1)。链栈的核心特性动态扩展性链栈的存储空间随需求动态分配无需担心栈满问题除非内存耗尽。高效操作入栈和出栈仅需修改头节点指针无需移动其他元素操作效率稳定。内存灵活性每个节点独立分配内存可分散存储但需额外空间存储指针。实现关键栈顶指针指向链表头节点。空栈时栈顶指针为NULL。节点结构包含数据域和指向下一节点的指针域。代码实现带头结点的链栈#include stdio.h #include stdlib.h // 链栈结点类型定义 typedef struct StackNode { int data; struct StackNode *next; } StackNode, *StackPtr; // 链栈仅需栈顶指针指向头结点 typedef struct { StackPtr top; // 栈顶指针指向头结点 } LinkStack; // 1. 初始化带头结点的链栈 int InitStack(LinkStack *S) { // 创建头结点 S-top (StackPtr)malloc(sizeof(StackNode)); if (S-top NULL) return 0; // 内存分配失败 S-top-next NULL; // 头结点后继为空 return 1; } // 2. 判断栈空 int StackEmpty(LinkStack S) { // 头结点后无元素即为空 return S.top-next NULL; } // 3. 入栈头插法 int Push(LinkStack *S, int e) { StackPtr p (StackPtr)malloc(sizeof(StackNode)); if (p NULL) return 0; p-data e; p-next S-top-next; // 新结点指向原第一个元素 S-top-next p; // 头结点指向新结点 return 1; } // 4. 出栈 int Pop(LinkStack *S, int *e) { if (StackEmpty(*S)) return 0; // 栈空 StackPtr p S-top-next; // p指向待删除结点 *e p-data; S-top-next p-next; // 摘链 free(p); return 1; } // 5. 取栈顶元素不删除 int GetTop(LinkStack S, int *e) { if (StackEmpty(S)) return 0; *e S.top-next-data; return 1; } // 6. 销毁栈 int DestroyStack(LinkStack *S) { StackPtr p, q; p S-top; while (p ! NULL) { q p-next; free(p); p q; } S-top NULL; return 1; } // 测试主函数 int main() { LinkStack S; int e; InitStack(S); Push(S, 10); Push(S, 20); Push(S, 30); GetTop(S, e); printf(栈顶元素%d\n, e); Pop(S, e); printf(出栈元素%d\n, e); GetTop(S, e); printf(新栈顶%d\n, e); printf(栈是否为空%s\n, StackEmpty(S) ? 是 : 否); DestroyStack(S); return 0; }不带头结点的链栈#include stdio.h #include stdlib.h typedef struct StackNode { int data; struct StackNode *next; } StackNode, *StackPtr; typedef struct { StackPtr top; } LinkStack; // 初始化 void InitStack(LinkStack *S) { S-top NULL; } // 判空 int StackEmpty(LinkStack S) { return S.top NULL; } // 入栈 int Push(LinkStack *S, int e) { StackPtr p (StackPtr)malloc(sizeof(StackNode)); if (!p) return 0; p-data e; p-next S-top; S-top p; return 1; } // 出栈 int Pop(LinkStack *S, int *e) { if (StackEmpty(*S)) return 0; StackPtr p S-top; *e p-data; S-top p-next; free(p); return 1; } // 取栈顶 int GetTop(LinkStack S, int *e) { if (StackEmpty(S)) return 0; *e S.top-data; return 1; } // 销毁栈 void DestroyStack(LinkStack *S) { StackPtr p, q; p S-top; while (p ! NULL) { q p-next; free(p); p q; } S-top NULL; // 销毁后置空避免野指针 } // 测试 int main() { LinkStack S; int e; InitStack(S); Push(S, 10); Push(S, 20); Push(S, 30); GetTop(S, e); printf(栈顶%d\n, e); Pop(S, e); printf(出栈%d\n, e); DestroyStack(S); // 用完销毁 return 0; }