wordpress 多域名多站点,做网站用什么框架,动漫网站设计论文,广告软文案例逻辑结构#xff1a;
栈#xff08;Stack#xff09;是一种遵循后进先出#xff08;LIFO, Last In First Out#xff09;原则的有序集合 #xff08;受限的线性表#xff09;。这种数据结构只允许在栈顶进行添加#xff08;push#xff09;或删除#xff08;pop
栈Stack是一种遵循后进先出LIFO, Last In First Out原则的有序集合 受限的线性表。这种数据结构只允许在栈顶进行添加push或删除pop元素的操作。栈是一种非常基础且重要的数据结构广泛应用于计算机科学和软件开发中。
栈顶插入和删除
栈底固定的 不允许插入和删除
空栈不含任何元素
栈的基本操作
push(element): 向栈顶添加一个元素。如果栈已满则可能无法进行此操作。pop(): 移除栈顶的元素并返回该元素。如果栈为空则可能无法进行此操作并可能返回一个错误或特殊值如null或undefined。peek() 或 top(): 返回栈顶元素的值但不从栈中移除它。如果栈为空则可能返回一个错误或特殊值。isEmpty(): 检查栈是否为空。size(): 返回栈中元素的数量。
栈的存储结构
栈可以通过多种方式实现包括使用数组或列表和链表。
顺序存储 基于数组的栈顺序栈在这种实现中数组的一端被用作栈顶。添加元素时新元素被添加到数组的末尾移除元素时数组的最后一个元素被移除。这种实现方式在大多数编程语言中都非常高效因为数组的末尾操作通常很快。
初始化
# define MaxSize 50
typedef struct
{Elemtype data[MaxSize];int top;//栈顶指针}SqStack;//iniiallize
void initStack(SqStack s){
s.top-1;
}
判断非空
//empty
bool StackEmpty(SqStack s){if(s.top-1)return true;elsereturn false;
} 进栈
//in
bool Push(SqStack s,Elemtype e){if(s.topMaxSize-1)return false;else{s.top;s.data[s.top]e;}return true;}
进栈和出栈的操作 根据s.top的初始值不同而不同 s.top-1先指针1再进栈先出栈再指针-1
s.top0先进栈再指针1先指针-1再出栈 出栈
bool Pop(SqStack s,Elemtype e){if(s.top-1)return false;es.data[s.top];s.top--;return true;
}
读取栈顶元素
//read
bool GetTop(SqStack s,Elemtype x){if(s.top-1)return false;xs.data[s.top];
return true;
} 链式存储 基于链表的栈下列代码规定没有头结点LHead指向栈顶元素链表的头部被用作栈顶。添加元素时新元素被添加到链表的头部移除元素时链表的第一个元素即头部元素被移除。虽然链表在随机访问方面不如数组高效但在某些情况下如动态内存分配链表可能更灵活。
//
typedef struct LinkNode
{Elemtype data;struct LinkNode *next;}LiStack; 栈的应用
栈的应用非常广泛包括但不限于 函数调用
在大多数编程语言中函数调用是通过栈来实现的。当函数被调用时其返回地址和局部变量被推入栈中当函数返回时这些信息从栈中弹出。 表达式求值
在编译器和解释器中栈用于计算表达式的值。例如在解析算术表达式时可以使用栈来跟踪操作符和操作数。
中缀转后缀
1加括号(( A ③( B *②( C -① D )))-©( E /④ F ))。
2运算符后移(( A ( B ( CD )-①)*②)③( EF )/④)-⑤。
3去除括号后得到后缀表达式 ABCD -①*②③ EF /④-⑤.
在计算机中中缀表达式转后缀表达式时需要借助一个栈用于保存暂时还不能确定运算顺序的运算符。从左到右依次扫描中缀表达式中的每一项具体转化过程如下 1遇到操作数。直接加入后缀表达式。 2遇到界限符。若为(则直接入栈若为)则依次弹出栈中的运算符并加入后缀表达式直到弹出(为止。注意(直接删除不加入后缀表达式。
3遇到运算符。若其优先级高于除(外的栈顶运算符则直接入栈。否则从栈顶开始依次弹出栈中优先级高于或等于当前运算符的所有运算符并加入后缀表达式直到遇到一个优先级低于它的运算符或遇到(时为止之后将当前运算符入栈。按上述方法扫描所有字符后将栈中剩余运算符依次弹出并加入后缀表达式。
转后缀图解例子 后缀表达式求值
通过后缀表示计算表达式值的过程从左往右依次扫描表达式的每一项若该项是操作数则将其压入栈中若该项是操作符 op 则从栈中退出两个操作数 Y 和 x 形成运算指令 X op y ,并将计算结果压入栈中。当所有项都扫描并处理完后栈顶存放的就是最后的计算结果。
后缀求值图解 括号匹配
栈可以用来检查括号如圆括号、方括号和花括号是否正确匹配。 回溯算法
在解决某些问题时如迷宫问题、八皇后问题等栈可以用来保存中间状态以便在需要时回溯到之前的状态。 页面访问历史
在Web浏览器中栈可以用来保存用户访问的页面历史以便用户可以通过“后退”按钮返回到之前的页面。
总之栈是一种简单但功能强大的数据结构其独特的后进先出原则使得它在许多应用场景中都非常有用。
