2.3栈和队列 栈和队列是两种特殊的线性表,它们是运算时要 受到某些限制的线性表,故也称为限定性的数据 结构
2.3 栈和队列 栈和队列是两种特殊的线性表，它们是运算时要 受到某些限制的线性表，故也称为限定性的数据 结构
2.3.1栈 2.3.1.1栈的定义 栈:限定只能在表的一端进行插入和删除的特殊的线性表 设栈s=(a1a2, g ais 其中a1是栈底元素,an是栈顶元素 进栈出栈 栈顶 栈底
２.3.1 栈 2.3.1.1栈的定义 栈：限定只能在表的一端进行插入和删除的特殊的线性表 设栈s=（a1，a2，. . . ,ai，. . . ，an）， 其中a1是栈底元素， an是栈顶元素。 a1 a2 …. an 进栈 出栈 栈顶 栈底
2.3.1栈 2.3.1.1栈的定义 栈:限定只能在表的一端进行插入和删除的特殊的线性表 设栈s=(a1a2, g ais 其中a1是栈底元素,an是栈顶元素 进栈出栈 栈顶(top):允许插入和删除的一端; 约定top始终指向新数据元素将存放的位置。栈顶an 栈底( bottom):不允许插入和删除的一端。 栈底
２.3.1 栈 2.3.1.1栈的定义 栈：限定只能在表的一端进行插入和删除的特殊的线性表 设栈s=（a1，a2，. . . ,ai，. . . ，an）， 其中a1是栈底元素， an是栈顶元素。 栈顶（top)：允许插入和删除的一端； 约定top始终指向新数据元素将存放的位置。 栈底（bottom):不允许插入和删除的一端。 a1 a2 …. an 进栈 出栈 栈顶 栈底
機數鲍顔算个顺槍戋的最大簪捶 stacks的婚态top=0 3,删除栈顶元素4读取栈项元素 S[4] 栈空 S[4」 10进栈 3 2 2 op 0 op 10 bas Top=0 stopEX e top=top+. S(41 S[4 top=4 3 op 340 2 30 30出栈230 栈满 25 25 0 10 ←bas 0 top=top-1 e 10 as x=s[top] top=stacksizee
栈中的运算：1.设置空栈 ； 2. 插入一个新的栈顶元素 3. 删除栈顶元素； 4. 读取栈顶元素 。 设数组S是一个顺序栈，栈的最大容量stacksize=4，初始状态top=0 10 S[4] 2 3 1 0 bas s[top]=x e top=top+1 top 10 25 30 S[4] 2 3 1 0 top bas top=top-1 e x=s[top] 栈空 10进栈 30出栈 S[4] 2 3 1 0 Top=0 top 栈满 top=stacksize 10 25 30 40 S[4] 2 3 1 0 top=4 bas e
2.3.1.2栈的存储结构 顺序栈、链栈 (1顺序栈: 用顺序存储结构表示的栈。 顺序栈用一组连续的存储单元存 放自栈底到栈顶的数据元素,一 般用一维数组表示,设置一个简 单变量top指示栈顶位置,称为栈 顶指针,它始终指向待插入元素 op 的位置
2.3.1.2栈的存储结构 顺序栈、链栈 a2 a1 a2 top (1)顺序栈： 用顺序存储结构表示的栈。 顺序栈用一组连续的存储单元存 放自栈底到栈顶的数据元素，一 般用一维数组表示，设置一个简 单变量top指示栈顶位置，称为栈 顶指针，它始终指向待插入元素 的位置
进栈算法 通过地址传递,用 #define statcksize 100 op带回实际栈顶指 int push(int s[l, int x, int*ptop) nt top; top=ptop; if(top= =stacksize) 98765432 top printf("overflow); return);] a4 else s[top]=x; a *ptop=+top;/*实际栈顶指针加1*/ 1 a2 return(1):] 0a1
·进栈算法 #define statcksize 100 int push(int s[ ], int x, int *ptop) { int top; top=*ptop; if(top= =stacksize) {printf(“overflow”); return (0); } else { s[top]=x; *ptop=++top; /*实际栈顶指针加1*/ return (1) ; } } 通过地址传递，用 ptop带回实际栈顶指 针 a2 a3 a4 9 8 7 6 5 4 3 2 1 0 a1 top
出栈算法: 通过地址传递,用 ptop带回实际栈顶指 int pop(int s[ l, int ptop, int*py) Int top; 栈 top="ptop 通过指针变量py 带回出栈元素 if(top==0) i printf( "stack empty"); return (O); 1 top else(--top a *py=s[top]/*返回出栈元素*/ a ptop=top; 9876543210 a 2 return (1); a1
出栈算法： int pop(int s[ ], int *ptop, int *py) { int top; top=*ptop; if(top= =0) { printf(“stack empty”); return( 0); } else { - -top; *py=s[top]; /*返回出栈元素*/ *ptop=top; return(1); } } 通过地址传递，用 ptop带回实际栈顶指 针 通过指针变量py 带回出栈元素 栈 s a2 a3 a4 9 8 7 6 5 4 3 2 1 0 a1 top
(2)鲢栈 用指针来实现的栈叫链栈。栈的容量事先不能 估计时采用这种存储结构。 链栈的类型说明如下: Typedef struct Inode topx 栈底 int data struct Inode * next: iNode,*Stack
x ∧ top 栈底 （2）链栈 用指针来实现的栈叫链栈。栈的容量事先不能 估计时采用这种存储结构。 链栈的类型说明如下： Typedef struct lnode{ int data； struct lnode next； }lnode，Lstack；
进栈算法 int Push(Stack s, int e 进栈元素e 栈s p=(Lstack malloc(sizeof(node) p->data=e p->next=s S-p return(1; ∧bas
进栈算法 int lpush(Lstack s, int e) { p=(Lstack)malloc(sizeof(lnode)); p->data=e; p->next=s; s=p; return (1); } ∧ bas e S 栈 s 进栈元素e
进栈算法 int Push(Stack s, int e p=(Stack)malloc(sizeof(Inode)); p->data=e p->next=s S-p return(1; ∧|bas
进栈算法 int lpush(Lstack s, int e) { p=(Lstack)malloc(sizeof(lnode)); p->data=e; p->next=s; s=p; return (1); } ∧ P bas e S