一、栈的基本概念
①栈的定义
②栈的基本操作
③常考题型
④小结
二、栈的顺序存储实现
①顺序栈的定义
②初始化操作
③进栈操作
④出栈操作
⑤读栈顶元素操作
⑥共享栈
⑦小结
三、栈的链式存储实现
①链栈的定义
②小结
#include <stdio.h> #include <stdlib.h> // 链栈的结点结构 typedef struct LinkNode { int data; // 数据域 struct LinkNode *next; // 指针域 } LinkNode; // 链栈结构（不带头结点，栈顶指针直接指向栈顶元素） typedef struct { LinkNode *top; // 栈顶指针 } LinkStack; // 1. 初始化链栈 void InitStack(LinkStack &S) { S.top = NULL; // 空栈时栈顶指针为NULL } // 2. 判断栈是否为空 bool StackEmpty(LinkStack S) { return S.top == NULL; } // 3. 进栈操作（增） bool Push(LinkStack &S, int x) { // 生成新结点 LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode)); if (p == NULL) return false; // 内存分配失败 p->data = x; p->next = S.top; // 新结点的next指向原栈顶 S.top = p; // 更新栈顶指针 return true; } // 4. 出栈操作（删） bool Pop(LinkStack &S, int &x) { if (StackEmpty(S)) return false; // 栈空，出栈失败 LinkNode *p = S.top; // 指向栈顶结点 x = p->data; // 获取栈顶元素 S.top = S.top->next; // 栈顶指针下移 free(p); // 释放原栈顶结点 return true; } // 5. 获取栈顶元素（查） bool GetTop(LinkStack S, int &x) { if (StackEmpty(S)) return false; // 栈空，获取失败 x = S.top->data; return true; } // 测试函数 int main() { LinkStack S; InitStack(S); // 进栈 Push(S, 1); Push(S, 2); Push(S, 3); // 获取栈顶 int topVal; if (GetTop(S, topVal)) { printf("栈顶元素：%d\n", topVal); } // 出栈 int popVal; while (Pop(S, popVal)) { printf("出栈元素：%d\n", popVal); } // 判空 if (StackEmpty(S)) { printf("栈已为空\n"); } return 0; }
