4.栈
定义
栈（Stack）是一种遵循后进先出（LIFO, Last In First Out）原则的数据结构。它只允许在栈顶进行添加 （push）或删除（pop）元素的操作。栈的实现可以通过数组或链表来完成。、
- 栈顶指的是栈中最后一个被添加（push）的元素所在的位置。在栈的操作中，所有的添加和 删除操作都发生在栈顶，这符合栈的后进先出（LIFO, Last In First Out）原则。
栈的实现可以通过数组或链表来完成。
栈并不特指某种具体某种数据结构，而是一种思想，只要具备先进后出，后进先出的思想的数据结构都 可称作为栈。
举个例子：弹夹
第一个子弹压入 最下面
第三个子弹压入 最上面
第三个子弹先发射 第一个子弹最后发射
1 顺序栈
使用数组实现，栈顶通常通过一个索引(栈顶元素的索引)（index）来标识，这个索引指向栈中最后一个元素的位置。
- 当栈为空时，栈顶索引的值通常是一个特定的值（如-1），表示没有元素在栈中。
- 当向栈中添加元素时，栈顶索引会增加，并将新元素放置在索引指向的位置。
- 当从栈中删除元素时，栈顶索引会减少，并移除索引指向的元素。
格式：
数组+整型数据的结构体（类）
struct 栈名
{
int top; // 栈顶元素的下标。
数据类型 数组名[长度]; // 栈元素存放的空间
};
注意：顺序栈在取元素的时候其实没有删除元素的，只是把下标移动了，在下一次增加元素就会覆盖原 来的元素
- 插入
- 删除
代码```
#include <iostream>
using namespace std;
#define MAX_SIZE 100
// 定义栈
typedef struct Stack
{
int top;// 栈顶元素的索引
int items[MAX_SIZE]; // 存储栈中元素的数组
}Stack;
// 初始化栈
void initStack(Stack*S)
{
S->top = -1;// 栈空时，栈顶索引为-1
}
// 判断栈是不是空
bool isEmpty(Stack*S)
{
return S->top == -1;
}
// 判断栈是不是满
bool isFull(Stack*S)
{
return S->top == MAX_SIZE - 1;
}
// 添加元素
bool push(Stack *S, int items)
{
// 栈满
if(S->top == MAX_SIZE - 1)
{
cout << "栈满了" << endl;
return false;
}
// 栈顶插入
else
{
// 栈顶索引+1 s->top ++
// 把元素放到新的索引处
S->items[++S->top] = items;
return true;
}
}
// 栈种删除元素，并且获取被删除的值
bool pop(Stack *S, int *items)//int *items：这是一个指针参数，用于将被弹出的值返回给调用者
// 过指针参数，你可以将值存储到调用者传递的地址中，从而实现返回值的效果。
{
// 栈空
if(S->top == -1 )
{
cout << "栈空" << endl;
return false;
}
// 获取值
*items = S->items[S->top--];
return true;
}
// 获取栈顶元素但是不删除
bool peek (Stack *S, int *items)
{
// 栈空
if(S->top == -1 )
{
cout << "栈空" << endl;
return false;
}
*items = S->items[S->top];
return true;
}
int main()
{
Stack s;
initStack(&s);
push(&s, 1);
push(&s, 2);
push(&s, 3);
int topElement = 0;
if(peek(&s, &topElement))
{
cout << "栈顶元素" << topElement << endl;
}
int popElement = 0;
if(pop(&s, &popElement))
{
cout << "栈顶元素" << popElement << endl;
}
if(isEmpty(&s))
{
cout << "栈是空的" << endl;
}
return 0;
}
2 链式栈
在链表实现的栈中，栈顶则通常指向链表的最后一个节点（即链表的尾部），因为链表的尾部在栈中扮 演了栈顶的角色。
- 插入
- 删除
#include <iostream>
using namespace std;
// 定义节点
typedef struct stackNode
{
int data;
struct stackNode *next;
}StackNode;
// 定义链表
typedef struct stack
{
StackNode *top ;
}Stack;
// 初始化栈
void initStack(Stack *s)
{
s->top = nullptr;
}
// 判断栈是不是空
bool isEmoty(Stack *s)
{
return s->top == nullptr;
}
// 栈添加元素
bool push(Stack *s, int item)
{
StackNode *newNode = new StackNode;
if(!newNode)
{
cout << "内存分配失败" << endl;
return false;
}
newNode->data = item;
newNode->next = s->top;
s->top = newNode;
return true;
}
// 栈删除元素
bool pop(Stack *s, int *item)
{
if(s->top == nullptr)
{
cout << "栈空" << endl;
return false;
}
//保存原栈顶元素
StackNode *oldNode = s->top;
//取出原栈顶元素
*item = oldNode->data;
// 更新栈顶指针
s->top = s->top->next;
//释放原栈顶节点的内存
delete oldNode;
return true;
}
// 获取栈顶元素
bool peek(Stack *s, int *item)
{
// 空栈
if(s->top == nullptr)
{
cout << "栈空" << endl;
return false;
}
*item = s->top->data;//直接访问栈顶元素
return true;
}
// 清空栈内存(不需要栈使用)
void freeStack(Stack *s)
{
StackNode *current = s->top;
while(current)
{
StackNode *p_next = current->next;
delete current;
current = p_next;
}
面向对象就是a对面向过程的封装