当前位置：首页 > news >正文

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

news 2026/5/28 11:11:54

1.一般线性表：可以做线性表的任意位置操作

2.对线性表进行一些约束：只允许在同一端进行插入和删除中间位置不允许操作，构成了栈。

允许操作的一端：栈顶

不允许操作的一端：栈底

3.性质：先进后出---后进先出 stack(堆叠) ：eg.碗的堆叠，只能从最上面开始拿走碗和放碗

4.应用场景：基于性质

（1）函数的实现基于栈的（递归） eg.main()函数里有insert()函数，insert()里有find() ,find()先返回然后insert，main

（2）倒着走的逻辑：撤销

（3）物理上的堆栈：内存中有一块区域：堆栈（栈）提升效率

5.操作：

空栈：栈中没有数据

操作：初始化一个空栈入栈（插入）出栈(删除) 判满判空得到栈顶元素(访问)

基于顺序存储结构实现的栈：顺序栈----数组 int data[maxsize] 0~maxsize-1

size记录个数？不用，用top

初始化一个栈 data[]

栈顶指针： int top; 不需要栈底指针b(本来就不用动)

空栈时：top=0

此时栈顶指针应该指向栈顶的下一个位置

入栈：a[top]=k; top++;

出栈：top--; 判满：top==maxsize 判空：top==0

得到栈顶数据 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]

判满： top==maxsize-1 ----上溢出

判空：top==-1

代码演示

//提示：这段代码初始化栈顶指针为0实现 // 且数组和和结构体都采用动态内存分配形式，而不直接定义全局或局部变量 // 指针的本质是“地址变量”：int* data本身只存一个内存地址，并不直接包含数组空间。它需要指向一块有效的内存才能存储数据 #include<iostream> #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->data=new int[p->top+1]; 我觉得这才叫动态内存分配！！ 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→next=nullptr 不需要判满

存在下溢出

代码演示

//栈的链式存储结构 #include<iostream> 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; // 匹配 }

如果笔记或代码有误也欢迎指出哦

查看全文

http://www.jsqmd.com/news/597693/