宁波网站推广服务,个人网站建设的步骤过程,网站进度条代码,wordpress 分隔符 sp栈 前言一、栈1.1栈的概念及结构1.2栈的实现1.3栈的面试题 二、栈的具体实现代码栈的初始化栈的销毁入栈出栈返回栈顶元素返回栈中的元素个数检测是否为空Stack.hStack.ctest.c 前言
栈#xff0c;作为一种后进先出#xff08;LIFO#xff09;的数据结构#xff0c;在计算… 栈 前言一、栈1.1栈的概念及结构1.2栈的实现1.3栈的面试题 二、栈的具体实现代码栈的初始化栈的销毁入栈出栈返回栈顶元素返回栈中的元素个数检测是否为空Stack.hStack.ctest.c 前言
栈作为一种后进先出LIFO的数据结构在计算机科学中扮演着重要的角色。它的特性使得它在处理函数调用、括号匹配、表达式求值等问题时具有得天独厚的优势。然而如果我们跳出传统思维的束缚会发现栈的用途远不止于此。
在现代软件开发中栈的概念被广泛应用在内存管理、并发控制等多个领域。以内存管理为例每个线程都有自己的栈空间用于存储局部变量和函数调用信息。这种隔离保证了线程之间的数据安全避免了数据混乱和意外覆盖。
同样在并发控制中栈也发挥着不可替代的作用。通过维护一个任务栈系统可以合理地调度和分配计算资源确保任务按照特定的顺序执行从而避免了并发访问导致的数据不一致问题。
不仅如此栈的思想还可以被借鉴到生活的方方面面。想象一下如果我们将日常生活比作一个栈那么每一天的生活就是一个新的元素被推入栈中。而当我们结束一天的生活这个元素就会被从栈中弹出成为我们宝贵的回忆。这种后进先出的特性使得我们能够更好地珍惜当下因为每一个现在都会成为过去而每一个过去都是无法替代的。
在这个意义上栈不仅仅是一种数据结构更是一种生活态度。它提醒我们珍惜每一个当下因为每一个现在都会成为我们未来回忆的一部分。同时它也告诉我们在面对困难和挑战时要敢于迎难而上因为只有这样我们才能不断成长和进步。 一、栈
1.1栈的概念及结构
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。
压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。
出栈栈的删除操作叫做出栈。出数据也在栈顶。 Push是入栈
Pop是出栈
1.2栈的实现
栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。 // 下面是定长的静态栈的结构实际中一般不实用所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 栈顶
}Stack;// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top; // 栈顶int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps); 1.3栈的面试题 括号匹配问题 一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈然后再依次出栈则元素出栈的顺序是 。 A. 12345ABCDE B. EDCBA54321 C. ABCDE12345 D. 54321EDCBA 若进栈序列为 1,2,3,4 进栈过程中可以出栈则下列不可能的一个出栈序列是 A 1,4,3,2 B 2,3,4,1 C 3,1,4,2 D 3,4,2,1
答案B C
二、栈的具体实现代码
有关栈虽然数组类型的栈类型结构更优但在实际写题目的过程中链表形式的栈更适用些接下来我将实现一下链栈
栈的初始化
void STInit(ST* ps);//栈的初始化void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top -1;//或者ps-top 0;具体区别在于先还是后
}栈的初始化是数据结构中栈操作的第一步它涉及为栈分配内存空间并设置其初始状态。栈是一种后进先出LIFO的数据结构这意味着最后一个被放入栈中的元素将是第一个被取出的元素。
在进行栈的初始化时我们需要考虑几个关键步骤。首先我们需要为栈定义一个合适的数据结构这通常是一个数组或链表。数组实现的栈在内存中使用连续空间而链表实现的栈则更为灵活但可能会占用更多的内存。
接下来我们需要为栈分配内存空间。对于数组实现的栈这通常意味着创建一个固定大小的数组来存储栈元素。对于链表实现的栈我们需要创建一个空的链表节点作为栈顶。
在分配了内存空间之后我们需要设置栈的初始状态。这通常意味着将栈顶指针或引用设置为一个表示栈为空的状态。对于数组实现的栈这通常是数组的第一个位置或最后一个位置的索引。对于链表实现的栈这通常是一个指向空链表节点的指针。
完成栈的初始化后我们就可以开始执行栈的基本操作如入栈push、出栈pop、查看栈顶元素top以及判断栈是否为空is_empty等。这些操作需要确保遵循栈的后进先出原则。
栈的销毁
void STDestroy(ST* ps);//栈的销毁void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity 0;ps-top -1;
}栈的销毁是栈生命周期中的最后一个阶段它标志着栈内所有数据元素的释放和栈结构本身的解除。在进行栈的销毁之前必须确保栈中没有任何数据元素否则可能会导致数据丢失或内存泄漏。
栈的销毁过程通常包括以下几个步骤
首先需要遍历栈内的所有元素并将它们逐一释放。这通常涉及到调用每个元素的析构函数如果是C等支持面向对象编程的语言或相应的清理函数如果是C等过程式编程语言以确保每个元素在被销毁前能够正确地完成其生命周期内的所有任务如关闭文件、释放内存等。
其次需要销毁栈本身的数据结构。这通常意味着释放栈所占用的内存空间。在大多数编程语言中这可以通过调用类似于freeC语言或deleteC这样的内存管理函数来完成。一旦栈的数据结构被销毁它就不再是一个有效的栈不能再执行入栈、出栈等操作。
最后为了确保栈确实已经被销毁可以在销毁后进行一些检查操作。例如可以尝试对栈执行一些操作如入栈或出栈并检查是否会引发错误或异常。如果程序能够正确地检测到栈已经被销毁并采取相应的错误处理措施那么这就可以作为栈销毁过程完成的一个标志。
总的来说栈的销毁是一个非常重要的过程它确保了栈在不再需要时能够正确地释放其占用的资源防止了内存泄漏和其他潜在的资源管理问题。同时通过销毁栈也可以为其他需要使用这些资源的操作提供空间从而提高了整个程序的效率和可靠性。
入栈
//入栈
void STPush(ST* ps,STDatatype x);void STPush(ST* ps,STDatatype x)
{assert(ps);ps-top;if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDatatype* p (STDatatype*)realloc(ps-a, sizeof(STDatatype)*newcapacity);if (p NULL){perror(p malloc : );return 0;}ps-a p;ps-capacity newcapacity;}ps-a[ps-top] x;
}“入栈”Push是栈Stack这种数据结构中的一个基本操作。栈是一种遵循后进先出Last In First Out简称LIFO原则的数据结构意味着最后放入栈中的元素将会是第一个被取出的。
“入栈”操作的具体含义是
添加元素将一个元素添加到栈的顶部。栈顶变化由于新元素被添加到栈顶所以栈顶指针或引用会更新指向这个新添加的元素。栈大小变化栈的大小或容量会增加因为多了一个元素。
例如假设我们有一个空的栈并且按照以下顺序执行入栈操作
入栈 A入栈 B入栈 C
那么栈的当前状态将是 C 在顶部B 在中间A 在底部。如果我们现在执行出栈Pop操作C 将被取出接着是 B最后是 A。
在实际应用中栈常用于保存函数调用过程中的局部变量、参数和返回地址实现递归调用以及进行深度优先搜索等。
入栈是每一个数据处理流程中不可或缺的一环。在信息技术的世界里数据就如同图书馆的藏书需要有序地存放和取用。而栈便是这个数字世界中的一个小巧精致的藏书阁它遵循着后进先出LIFO的规则每一份数据都像是一本书被轻轻放在栈顶等待着被取用或者再次被存放。
每当有新的数据需要处理时它就会被推入栈中。这个过程就像是图书馆里新到了一本畅销书图书管理员会将它放在最显眼的位置供读者最先取阅。同样栈顶的数据也是最先被处理的因为它是最后进栈的。这种有序的处理方式保证了数据处理的效率和准确性。
然而栈并非万能的。它的规则简单而明确但也因此有局限性。有时候我们需要按照不同的顺序来处理数据这时候就需要使用到队列等其他数据结构。但无论如何栈都是数据处理中不可或缺的一部分。
在软件开发的世界里栈的作用更是举足轻重。函数调用、递归算法、异常处理等都离不开栈的支持。每当一个函数被调用时它的相关信息就会被压入调用栈中等待函数执行完毕后弹出。这使得程序能够准确地跟踪函数的执行顺序保证程序的正确运行。
同时栈也是内存管理的重要手段。在编程中我们经常需要动态地分配和释放内存。而栈就是内存分配的一种方式。它会自动管理分配给每个函数的内存空间当函数执行完毕后这些内存空间就会被自动释放避免了内存泄漏等问题的发生。
总的来说入栈是数据处理和程序运行中的关键步骤。它保证了数据的有序性和程序的正确性是信息技术世界中不可或缺的一环。在未来的技术发展中栈的作用将更加重要我们也需要更加深入地理解和应用它。
出栈
//出栈
void STPop(ST* ps);void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps-top--;
}当元素从栈的顶部被移除时这个过程被称为“出栈”。栈是一种遵循后进先出LIFO原则的数据结构其中新元素总是被添加到栈顶而只有栈顶的元素可以被移除。出栈操作会减少栈的大小并返回被移除的元素。如果栈为空则无法进行出栈操作。
返回栈顶元素
STDatatype STTop(ST* ps);//返回栈顶元素STDatatype STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps-a[ps-top];
}返回栈中的元素个数
int STSize(ST* ps);//返回栈中的元素个数int STSize(ST* ps)
{assert(ps);return ps-top;
}检测是否为空
注意在使用VS2022编译器编译C语言需要用到布尔类型的时候需要添加头文件#include stdbool.h添加了这个头文件才能使用布尔类型
bool STEmpty(ST* ps);//检测是否为空bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}Stack.h
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h
typedef int STDatatype;
typedef struct Stack
{STDatatype* a;int top;int capacity;
}ST;void STInit(ST* ps);//栈的初始化
void STDestroy(ST* ps);//栈的销毁//入栈
void STPush(ST* ps,STDatatype x);
//出栈
void STPop(ST* ps);
STDatatype STTop(ST* ps);//返回栈顶元素
int STSize(ST* ps);//返回栈中的元素个数
bool STEmpty(ST* ps);//检测是否为空Stack.c
#include Stack.hvoid STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top -1;//或者ps-top 0;具体区别在于先还是后
}
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity 0;ps-top -1;
}
void STPush(ST* ps,STDatatype x)
{assert(ps);ps-top;if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDatatype* p (STDatatype*)realloc(ps-a, sizeof(STDatatype)*newcapacity);if (p NULL){perror(p malloc : );return 0;}ps-a p;ps-capacity newcapacity;}ps-a[ps-top] x;
}
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps-top--;
}bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}
STDatatype STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps-a[ps-top];
}
int STSize(ST* ps)
{assert(ps);return ps-top;
}test.c
#includeStack.hint main()
{ST s;STInit(s);STPush(s, 1);STPush(s, 2);STPush(s, 3);int top STTop(s);printf(%d , top);STPop(s);STPush(s, 4);STPush(s, 5);while (!STEmpty(s)){int top STTop(s);printf(%d , top);STPop(s);}STDestroy(s);return 0;
}
