栈笔记及代码实现(数据结构)

1.一般线性表可以做线性表的任意位置操作2.对线性表进行一些约束 只允许在同一端进行插入和删除中间位置不允许操作构成了栈。允许操作的一端栈顶不允许操作的一端栈底3.性质先进后出---后进先出 stack(堆叠) eg.碗的堆叠只能从最上面开始拿走碗和放碗4.应用场景 基于性质1函数的实现基于栈的递归 eg.main()函数里有insert()函数insert()里有find() ,find()先返回然后insertmain2倒着走的逻辑 撤销3物理上的堆栈内存中有一块区域堆栈栈 提升效率5.操作空栈栈中没有数据操作初始化一个空栈 入栈 插入 出栈(删除) 判满 判空 得到栈顶元素(访问)基于顺序存储结构实现的栈顺序栈----数组 int data[maxsize] 0~maxsize-1size记录个数 不用用top初始化一个栈 data[]栈顶指针 int top; 不需要栈底指针b(本来就不用动)空栈时top0此时栈顶指针应该指向栈顶的下一个位置入栈a[top]k; top;出栈top--; 判满topmaxsize 判空top0得到栈顶数据 return data[top-1]模拟遍历while (L-top 0)栈顶指针指向1时结束{cout Get(L) ;Pop(L); //自带top--功能不需要再for循环}空栈时top-1 top就是栈顶数据的下标此时栈顶指针指向栈顶入栈: top,data[top]k; 出栈top-- 得到栈顶元素:data[top]判满 topmaxsize-1 ----上溢出判空top-1代码演示//提示这段代码初始化栈顶指针为0实现 // 且数组和和结构体都采用动态内存分配形式而不直接定义全局或局部变量 // 指针的本质是“地址变量”int* data本身只存一个内存地址并不直接包含数组空间。它需要指向一块有效的内存才能存储数据 #includeiostream #define maxsize 5 using namespace std; typedef struct SStack //顺序栈 { int* data;//模拟动态数组 //int data[maxsize]; int top; }SStack; //初始化栈 SStack* InitSStack() { SStack* p(SStack*)new SStack; p-top 0; // p-datanew int[p-top1]; 我觉得这才叫动态内存分配 p-data new int[maxsize];//是用多少给多少还是一次性给maxsize return p; } //入栈 void Push(SStack*p,int k) {//我把指针传进去就不需要返回值了 //入栈之前判断是否满栈 if (p-top maxsize) { cout 满了\n; return; } p-data[p-top] k; p-top; } //判空 bool Empty(SStack* p) { if (p-top 0)return 1; return 0; } //出栈 void Pop(SStack* p) { //判断是否空栈 if (Empty(p)) { cout 空的\n; return; } p-top--; } //获取栈顶元素 int Get(SStack* p) { return p-data[p-top - 1]; } int main() { SStack* s InitSStack(); Push(s,10); Push(s, 20); Push(s, 30); Push(s, 40); Push(s, 50); Push(s, 60); SStack* L s; while (L-top 0)//模拟遍历 栈顶指针指向1时结束 { cout Get(L) ; Pop(L); //自带top--功能不需要再for循环 } }基于链式存储结构实现的栈链式栈----自带头结点的单链表由于栈的特点后入栈的数据永远排在先入栈的数据的前面而单链表头插法新插入的数据(eg.3)会插入到原来插入数据的前面然后删除首元结点出栈综上分析初始化空栈 栈顶指针头指针 入栈头插法 出栈删除首元结点得到栈顶元素 : 判空top→nextnullptr 不需要判满存在下溢出代码演示//栈的链式存储结构 #includeiostream using namespace std; typedef struct StackNode { int data; struct StackNode* next; }StackNode,*LinkListStack; //1.链栈的初始化 LinkListStack InitStack() { StackNode* p (StackNode*) new StackNode; p-next nullptr; return p; } //2.入栈 void Push(LinkListStack s,int k) { //重点如果不改变指针本身的指向是不需要传s的指针的 //不需要判满 StackNode* temp (StackNode*) new StackNode; temp-data k; temp-next s-next; s-next temp; } //3.判空 bool Empty(LinkListStack s) { if (s-next nullptr) return 1; return 0; } //4.出栈 int Pop(LinkListStack s) { //需要判空 if (Empty(s)) { cout空的\n; return -1; } auto temp s-next; int k temp-data; s-next s-next-next; delete temp; temp NULL; return k; } //5.获取栈顶元素 int Get(StackNode* s) { return s-next-data; } int main() { LinkListStack s InitStack(); Push(s, 1); Push(s, 10); Push(s, 5); Push(s, 6); Push(s, 11); cout Pop(s); cout Get(s); }补充算法实现将正数N转换为对应的d进制的数据输出void reverse(int N, int d) { LinkListStack s InitStack(); while (N 0) { Push(s, N % d); N / d; } while (!Empty(s)) { cout Pop(s); } cout \n; delete s; }判断字符串str是否回文bool check1(char str[]) { LinkListStack s InitStack(); int len strlen(str); for (int i 0; i len; i) { Push(s, str[i]); } for (int i 0; i len; i) { if (Pop(s) ! str[i]) { delete s; return 0; // 不是回文 } } delete s; return 1; // 是回文 }判断字符串str中括号是否匹配bool check2(char* str) { LinkListStack s InitStack(); int len strlen(str); for (int i 0; i len; i) { if (str[i] ( || str[i] { || str[i] [) { Push(s, str[i]); } else if (str[i] ) || str[i] } || str[i] ]) { if (Empty(s)) { delete s; return 0; // 不匹配没有左括号的情况 } int top Pop(s); if ((str[i] ) top ! () || (str[i] } top ! {) || (str[i] ] top ! [)) { delete s; return 0; // 不匹配交叉的情况 } } } if (!Empty(s)) { delete s; return 0; // 不匹配,栈内还有括号未全部匹配的情况 } delete s; return 1; // 匹配 }如果笔记或代码有误也欢迎指出哦