栈和队列都是特殊的线性表,因此定义栈和队列与之前的线性表异曲同工:
顺序栈
顺序栈的架构
顺序栈的特点
top=0 或top=base 表示空栈
base=NULL表示栈不存在
当插入新的栈顶元素时,指针top+1
删除栈顶元素时,指针top-1
当top>stacksize时,栈满,溢出
注意,此处的top栈顶指针是指向栈顶元素的下一个元素,也有一种说法是指向栈顶元素,两种都可,此处采用前者
1、创建栈
或
typedef int SElemType;
typedef struct{
SElemType data[MAXSIZE];
int top;//栈顶指针
}
或使用STL库的栈
头文件#include <stack>
关于入栈操作
Status Push(SqStack *S,SElemType e){
if(S->top == MAXSIZE-1){
return ERROR;
}
S->top++;
S->data[S->top]==e;
return ok;
}
或者
关于出栈操作
可以
Status Pop(SqStack *S, SElemType *e){
if(S->top==-1)
return ERROR;
*e=S->data[S->top];
S->top--;
return OK;
}
或者
亦或者
这里是先打印再弹出
判栈满的函数
用STL栈无法实现栈满的监测,因为STL栈没有栈满这个概念。
链栈
我们知道栈顶是一个栈做压入和弹出的地方,而链表形态下也拥有一个头指针,那么我们就可以利用头指针作为栈顶指针,对于链栈而言,因为栈顶是在链表头部,因此不存在栈满的情况(除非内存已满)
对于链栈而言,它和链表空的条件一样,就是头指针(栈顶指针)top==NULL
栈的应用【编程】递归
说到递归,著名的斐波拉契数列就是一个递归数列,而斐波拉契数就是指符合斐波拉契数列运算方式得来的数。
上图就是斐波拉契数列的原理,可以看到,除了0,1之外,斐波拉契数列的n项等于n-1和n-2项之和。直观实现特定位数的斐波拉契数列的程序在上面。但是不够简洁,不能提现斐波拉契的精髓
看看修改过的程序:
#include<iostream>
using namespace std;
int Feibo(int i){
if(i<2)
return i == 0?0:1;
return Feibo(i-1)+Feibo(i-2);
}
int main(){
int n=0;
cin>>n;
cout<<Feibo(n)<<endl;
return 0;
}
/Users/yuwenao/untitled12/cmake-build-debug-/untitled12
9
34
进程已结束,退出代码为 0
实现了,优美的递归运用,通过三行代码实现feibo。而递归是