提供网站制作公司哪家好,凡科建站登录界面,wordpress新闻站自动采集器,微信公众号管理平台官网一.栈的概念
栈是一种常见的数据结构#xff0c;它遵循后进先出的原则。栈可以看作是一种容器#xff0c;其中的元素按照一种特定的顺序进行插入和删除操作。
压栈#xff1a;栈的插入操作叫做进栈/压栈/入栈#xff0c;入数据在栈顶。 出栈#xff1a;栈的删除操作叫做…
一.栈的概念
栈是一种常见的数据结构它遵循后进先出的原则。栈可以看作是一种容器其中的元素按照一种特定的顺序进行插入和删除操作。
压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 1.栈的特点 1.元素的插入和删除操作只能在栈的一端进行该端被称为栈顶。 2.最后插入的元素是第一个被删除的元素因此称为后进先出。 3.栈中的元素没有编号或索引只有栈顶指针来指示栈的当前位置。
2.栈的优点 简单高效栈的操作是基于后进先出LIFO的原则入栈和出栈操作都只涉及栈顶元素因此操作的时间复杂度都是O(1)使得栈的操作非常高效。 空间效率高栈的底层实现可以使用数组或链表无论是使用静态数组还是动态链表都可以根据实际需要灵活分配内存因此在空间利用上比较高效。 递归和回溯栈在递归和回溯算法中扮演着重要的角色。递归函数调用时会将当前函数的状态包括局部变量、返回地址等压入栈中当递归函数返回时栈顶的状态会被弹出恢复到上一层递归函数的状态。 撤销操作栈可以用于实现撤销操作比如文本编辑器中的撤销功能。每当执行一个操作时将操作的状态存储在栈中当需要撤销时只需从栈中弹出最近的状态。
3.栈的缺点 容量限制栈的容量是有限的无论是基于数组还是链表实现的栈都会受到内存大小的限制。当栈的元素个数超过容量时会发生栈上溢stack overflow的错误。 无随机访问栈的特点是只能在栈顶进行插入和删除操作没有提供随机访问的能力。如果需要访问或修改栈中的其他元素必须先将栈顶的元素弹出直到达到目标位置。 不灵活栈的特性决定了它的使用场景受到一定的限制。对于需要随机访问、频繁插入和删除的场景栈可能不是最佳选择。
二.栈的功能
栈作为一种数据结构具有以下几个主要的功能 入栈将元素添加到栈的顶部栈顶。新元素成为栈顶原有的栈顶元素依次向下移动。入栈操作可以用于将数据添加到栈中。 出栈从栈的顶部栈顶移除元素。被移除的元素是最后一个入栈的元素即栈顶元素。出栈操作会改变栈的结构并返回被移除的元素。 获取栈顶元素获取栈顶的元素但不对栈进行修改。这个操作可以让我们查看栈顶的元素而不改变栈的结构。 判断栈是否为空检查栈是否不包含任何元素。如果栈中没有元素即栈为空该函数返回真否则返回假。 判断栈是否已满检查栈是否已达到其容量上限。对于基于数组实现的栈如果数组已满即栈已满该函数返回真否则返回假。
三.栈的实现 1.创建栈
创建一个结构体里面的成员是数组以及指针。在这里为了大家能够方便理解用静态的顺序表来实现
#include stdio.h
#define MAX_SIZE 100typedef struct {int data[MAX_SIZE]; // 用于存储栈中的元素int top; // 栈顶指针指向栈顶元素的索引
} Stack;
2.初始化栈
将栈顶的指针初始化为-1表示此栈为空。
// 初始化栈
void initStack(Stack* stack) {stack-top -1; // 栈顶指针初始化为-1表示栈为空
}
3.判断栈是否为空
判断栈是否为空。如果栈顶指针top等于-1表示栈为空返回1否则返回0。
// 判断栈是否为空
int isEmpty(Stack* stack) {return stack-top -1; // 栈为空时栈顶指针为-1
}
4. 判断是否已满
判断栈是否已满。如果栈顶指针top等于数组最大索引MAX_SIZE - 1表示栈已满返回1否则返回0。
// 判断栈是否已满
int isFull(Stack* stack) {
return stack-top MAX_SIZE - 1; // 栈满时栈顶指针等于数组最大索引
}
5.入栈 入栈操作。首先使用isFull函数检查栈是否已满如果已满则打印错误信息并返回否则将栈顶指针top加1并将元素item放入栈顶位置data[top]。
// 入栈
void push(Stack* stack, int item) {
if (isFull(stack)) {
printf(Stack overflow!\n); // 栈已满无法入栈
return;
}
stack-data[stack-top] item; // 栈顶指针加1并将元素放入栈顶
} 6.出栈
出栈操作。首先使用isEmpty函数检查栈是否为空如果为空则打印错误信息并返回-1否则返回栈顶元素data[top]并将栈顶指针top减1。
// 出栈
int pop(Stack* stack) {
if (isEmpty(stack)) {
printf(Stack underflow!\n); // 栈为空无法出栈
return -1;
}
return stack-data[stack-top--]; // 返回栈顶元素并将栈顶指针减1
} 7.获取栈顶元素
获取栈顶元素。首先使用isEmpty函数检查栈是否为空如果为空则打印错误信息并返回-1否则返回栈顶元素data[top]但不修改栈的结构。
/ 获取栈顶元素
int peek(Stack* stack) {
if (isEmpty(stack)) {
printf(Stack is empty!\n); // 栈为空无栈顶元素
return -1;
}
return stack-data[stack-top]; // 返回栈顶元素不修改栈的结构
}
8.打印栈中元素 打印栈中的元素。首先使用isEmpty函数检查栈是否为空如果为空则打印提示信息否则使用循环从栈底到栈顶依次打印栈中的元素。
/ 打印栈中的元素用于调试
void printStack(Stack* stack) {
if (isEmpty(stack)) {
printf(Stack is empty!\n);
return;
}
printf(Stack: );
for (int i 0; i stack-top; i) {
printf(%d , stack-data[i]);
}
printf(\n);
}
四.栈的源码呈现 #include stdio.h
#define MAX_SIZE 100typedef struct {int data[MAX_SIZE]; // 用于存储栈中的元素int top; // 栈顶指针指向栈顶元素的索引
} Stack;// 初始化栈
void initStack(Stack* stack) {stack-top -1; // 栈顶指针初始化为-1表示栈为空
}// 判断栈是否为空
int isEmpty(Stack* stack) {return stack-top -1; // 栈为空时栈顶指针为-1
}// 判断栈是否已满
int isFull(Stack* stack) {return stack-top MAX_SIZE - 1; // 栈满时栈顶指针等于数组最大索引
}// 入栈
void push(Stack* stack, int item) {if (isFull(stack)) {printf(Stack overflow!\n); // 栈已满无法入栈return;}stack-data[stack-top] item; // 栈顶指针加1并将元素放入栈顶
}// 出栈
int pop(Stack* stack) {if (isEmpty(stack)) {printf(Stack underflow!\n); // 栈为空无法出栈return -1;}return stack-data[stack-top--]; // 返回栈顶元素并将栈顶指针减1
}// 获取栈顶元素
int peek(Stack* stack) {if (isEmpty(stack)) {printf(Stack is empty!\n); // 栈为空无栈顶元素return -1;}return stack-data[stack-top]; // 返回栈顶元素不修改栈的结构
}// 打印栈中的元素用于调试
void printStack(Stack* stack) {if (isEmpty(stack)) {printf(Stack is empty!\n);return;}printf(Stack: );for (int i 0; i stack-top; i) {printf(%d , stack-data[i]);}printf(\n);
}// 主函数用于测试栈的功能
int main() {Stack stack;initStack(stack); // 初始化栈push(stack, 10);push(stack, 20);push(stack, 30);printStack(stack); // 打印栈中的元素printf(Top element: %d\n, peek(stack)); // 获取栈顶元素while (!isEmpty(stack)) {printf(Popped element: %d\n, pop(stack)); // 依次出栈并输出元素}return 0;
}
