怎么做网站排版,公司网站用服务器,广州我要做网站,个人主页模板图片导航栏1、基本概念
栈#xff1a;只允许在一端插入或删除操作的线性表栈底#xff08;buttom#xff09;#xff1a;固定的#xff0c;不允许进行插入和删除操作的另一端栈顶#xff08;top#xff09;#xff1a;线性表允许插入和删除的一段 栈是线性表#xff0c;只不过受…1、基本概念
栈只允许在一端插入或删除操作的线性表栈底buttom固定的不允许进行插入和删除操作的另一端栈顶top线性表允许插入和删除的一段 栈是线性表只不过受到限制了只允许在栈顶进行插入和删除操作所以先入栈的后出栈
2、顺序栈
栈是线性表的特例栈的顺序存储也是线性表顺序存储。栈的顺序存储结构叫做顺序栈由于栈是受到限制的只允许在栈顶进行插入和删除所以顺序栈需要在顺序表是基础上修改点
/*顺序栈的定义
*/
#define MaxSize 50 //定义栈中有多少个元素
typedef int ElemType;
typedef struct {ElemType data[MaxSize];//存放栈中元素int top; //栈顶指针
}SqStack;top值不能超过MaxSize空栈的判断条件top-1初始值也是这个值当没有元素时top指向buttom后一个元素满栈的判断条件topMaxSize-1
2.1 基本操作
2.1.1 判空
/*判断空
*/
bool StackEmpty(SqStack S) {if (S.top -1)return true;elsereturn false;
}2.1.2 进栈 栈不满时栈顶指针先加1再送值到栈顶元素
/*进栈
*/
bool Push(SqStack S, ElemType x) {if (S.top MaxSize - 1)return false;S.data[S.top] x;return true;
}2.1.3 出栈 先判断栈是否为空不为空取栈顶元素top减一
/*出栈
*/
bool Pop(SqStack S, ElemType x) {if (S.top -1)return false;x S.data[S.top];S.top--;return true;
}2.1.4 读取栈顶元素 栈顶不为空取栈顶元素
/*读取栈顶元素
*/
bool GetTop(SqStack S, ElemType x)
{if (S.top -1)return false;x S.data[S.top];return true;
}3、共享栈
栈底位置相对不变的可以让两个顺序栈共享一个一维数组将两个栈的栈底分别设置在共享栈的两端两个栈顶向共享空间的中间延伸当一个栈存放数据少一个栈存放数据多可以考虑共享栈
typedef struct {ElemType data[MaxSize]; //存放元素int top1; //栈1栈顶int top2; //栈2栈顶
}SqDoubleStack;初始状态top1-1top2MaxSize所以当top1-1时表示栈1空top2MaxSize时表示栈2空栈满当top1和top2相差1时栈满此时两个栈的栈顶紧挨着没有空间存放数据了出栈top2加1top1要减1入栈top1加1top2减1
3.1基本操作
3.1.1 进栈
/*进栈stackNum:栈的序号*/bool Push(SqDoubleStack S, ElemType x, int stackNum) {if (S.top1 1 S.top2)return false; //栈满if (stackNum 1)S.data[S.top1] x;if (stackNum 2)S.data[S.top2] x;return true;
}4、链式栈
采用链式存储的栈称为链栈链栈的优点是便于多个栈共享存储空间和提高其效率并且不存在栈满溢出的情况,通常采用单链表实现并规定所有操作都是在单链表的表头进行的 带头结点
typedef struct SNode {ElemType data; //数据域struct SNode* next; //指针域
} SNode,*SLink; //链栈的结点
typedef struct LinkStack {SLink top; //栈顶指针int count; //链栈结点数
}LinkStack; //链栈不带头结点
typedef struct SNode {ElemType data; //数据域struct SNode* next; //指针域
} SNode,*SLink; 注意不带头结点和带头结点的链栈在具体实现方面有所不同
可以将头指针当做栈顶空栈的判断条件定为topnull
4.1 基本操作
4.1.1 进栈
/*
进栈
*/
bool Push(LinkStack *S, ElemType x) {SLink p (SLink)malloc(sizeof(SNode));p-data x;p-next S-top;S-top p;S-count;return true;}4.1.2 出栈
/*出栈
*/
bool Pop(LinkStack* S, ElemType x) {if (S-top NULL)return false;x S-top-data;SLink p S-top;S-top S-top-next;free(p);S-count--;return true;
}
