文档介绍：数据结构栈和队列
第1页，共54页，编辑于2022年，星期六
栈
栈的基本概念
1 栈的概念
栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last oc((S. STACKINCREMENT+STACK_SIZE) *sizeof(ElemType)); /* 栈满，追加存储空间 */
if (! ) return ERROR;
=+S. stacksize ;
S. stacksize+=STACKINCREMENT ;
}
*=e; ++ ; /* 栈顶指针加1，e成为新的栈顶 */
return OK;
}
第9页，共54页，编辑于2022年，星期六
4 弹栈(元素出栈)
Status pop( SqStack S, ElemType *e )
/*弹出栈顶元素*/
{ if ( == )
return ERROR ; /* 栈空，返回失败标志 */
-- ; e=*S. top ;
return OK ;
}
第10页，共54页，编辑于2022年，星期六
采用静态一维数组来存储栈。
栈底固定不变的，而栈顶则随着进栈和退栈操作变化的，
◆ 栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整型变量top(称为栈顶指针)来指示当前栈顶位置。
◆ 用top=0表示栈空的初始状态，每次top指向栈顶在数组中的存储位置。
◆ 结点进栈：首先执行top加1，使top指向新的栈顶位置，然后将数据元素保存到栈顶(top所指的当前位置)。
栈的静态顺序存储表示(简略)
第11页，共54页，编辑于2022年，星期六
◆ 结点出栈：首先把top指向的栈顶元素取出，然后执行top减1，使top指向新的栈顶位置。
若栈的数组有Maxsize个元素，则top=Maxsize-1时栈满。图3-3是一个大小为5的栈的变化示意图。
图3-3 静态堆栈变化示意图
空栈
bottom
top
Top=1
1个元素进栈
bottom
top
a
Top=3
3个元素进栈
bottom
top
a
b
c
Top=4
栈满
bottom
top
a
b
e
d
Top=2
元素c进栈
bottom
top
a
b
第12页，共54页，编辑于2022年，星期六
基本操作的实现
1 栈的类型定义
# define MAX_STACK_SIZE 100 /* 栈向量大小 */
# typedef int ElemType ;
typedef struct sqstack
{ ElemType stack_array[MAX_STACK_SIZE] ;
int top;
}SqStack ;
第13页，共54页，编辑于2022年，星期六
2 栈的初始化
SqStack Init_Stack(void)
{ SqStack S ;
==0 ; return(S) ;
}
第14页，共54页，编辑于2022年，星期六
3 压栈(元素进栈)
Status push(SqStack S , ElemType e)
/* 使数据元素e进栈成为新的栈顶 */
{ if (==MAX_STACK_SIZE-1)
return ERROR; /* 栈满，返回错误标志 */
++ ; /* 栈顶指针加1 */
[]=e ; /* e成为新的栈顶 */
return OK; /* 压栈成功 */
}
第15页，共54页，编辑于2022年，星期六
4 弹栈(元素出栈)
Status pop( SqStack S, ElemType *e )
/*弹出栈顶元素*/
{ if ( ==0 )
return ERROR ; /* 栈空，返回错误标志 */
*e=[] ;
-- ;
return OK ;
}
第16页，共54页，编辑于2022年，星期六
当栈满时做进栈运算必定产生空间溢出，简称“上溢”。上溢是一种出错状态，应设