2.3-2.4 栈和队列
1,栈 和 队列 都是 线性表 。
2,栈 和 队列 都是 操作受限 的线性表。
3、对栈和队列的基本操作进行限制的目的是：为了保证其数据元素 存取的特定顺序 。
即：栈可保证数据元素存取的 后进先出 顺序。
队列可保证数据元素存取的 先进先出 顺序。 。
一,栈的定义栈,限定只能在表的一端进行插入和删除的特殊的线性表 。
设栈 s=（ a1,a2,.,,,ai,.,,,an）,
其中 a1是栈底元素,an是栈顶元素 。
a1
a2
….
an栈顶栈底
2.3.1 栈的定义及基本操作栈顶 （ top)：允许插入和删除的一端；
top始终指向栈中最后一个元素所在的位置 。
栈底 （ bottom):不允许插入和删除的一端 。
思考,对栈的操作一旦进行了这样的限制,它和普通线性表会有怎样的区别？
2.3 栈一,栈的定义栈,限定只能在表的一端进行插入和删除的特殊的线性表 。
设栈 s=（ a1,a2,.,,,ai,.,,,an）,
其中 a1是栈底元素,an是栈顶元素 。
a1
a2
….
an栈顶栈底
a1
a2
….
an栈顶栈底栈的插入操作被称为进栈；
栈的删除操作被称为出栈。
进栈 出栈
栈的特点：后进栈的元素在出栈时较其它元素先。
因此栈被称为后进先出（ LIFO）的线性表。
二,栈的存储结构顺序栈,链栈
a2
a1a1
top
1.顺序栈：
用顺序存储结构表示的栈 。
顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素,一般用一维数组表示,设置一个简单变量 top指示栈顶位置,它始终指向栈中最后一个元素的位置 。
设数组 S是一个顺序栈,栈的最大容量 maxsize=4,初始状态 top=-1
10
25
30
S[4]
2
3
1
0
top
x=s[top]
top=top-1
10
S[4]
2
3
1
0
top=top+1
s[top]=x
top
10进栈
30出栈栈空
S[4]
2
3
1
0
top=-1 top
栈满
top=maxsize-1
10
25
30
40
S[4]
2
3
1
0
top=3
栈中的运算,1.设置空栈 ； 2,插入一个新的栈顶元素 (入栈 )
3,删除栈顶元素 (出栈 ） ； 4,读取栈顶元素 。
#define maxsize 100
typedef struct stacktype
{ datatype stack[maxsize];
int top;
}stacktype;
stacktype *s；
.
.
.
.
.
.
.
.
stack[0]
stack[1]
stack[98]
stack[99]
top
s
用 C语言对顺序栈类型进行的描述注意,datatype在此泛指栈中元素的类型，
实际应用时需按具体情况确定。例如：栈中元素为整型，则 stack应定义为整型数组。
三、顺序栈操作的算法描述（ C语言）
1 构造空栈
void initStack(stacktype *s)
{/*初始化栈 s，置为空栈 */
s->top = -1;
}
2 判断一个栈是否为空栈
int stackEmpty(stacktype *s)
{/* 判断 s是否为空栈，若为空栈，返回 1，否则返回 0 */
return s->top = = -1;
}
if(s->top==-1) return 1;
else return 0;
·进栈算法 （ 假定栈为整型 ）
#define maxsize 10
typedef struct stacktype
{ int stack[maxsize];
int top;
}stacktype;
void push(stacktype *s,int x)
{if(s->top= =maxsize-1)
{printf(“stackoverflow!”);
exit(1);}
else
{ s->top++; /*实际栈顶位置加 1 */
s->stack[s->top]=x;
}
}
a2
a3
a4
9
8
7
6
5
4
3
2
1
a10
top
topx
s->stack[++s->top]=x;
通过地址传递，用 s带回进栈操作后新栈的信息
int pop(stacktype *s)
{int y;
if(s->top= =-1)
{printf(“stack empty!\n”);
exit(1);
}
else
{ y=s->stack[s->top];
s->top--; /*栈顶位置下移 */
return(y); /*返回出栈元素 */
}
}
a2
a3
a4
9
8
7
6
5
4
3
2
1
a10
top
·出栈算法 （ 假定栈为整型 ）
topy=s->stack[s->top--]);
通过地址传递，
用 s带回出栈操作后新栈的信息读栈顶元素算法：
注意：此操作不改变栈顶的位置 。
int readtop(stacktype *s)
{
}
思考：此操作的算法如何编写。
提示：实现语句与出栈算法基本相同，唯一区别在不会改变栈顶的位置。
int y;
if(s->top= =0)
{printf(“stack empty!\n”);
exit(1);}
else
{ y=s->stack[s->top];
return(y); /*返回栈顶元素 */
}
an
an-1
a1 ∧
head
栈底
2.链栈用带头结点的单链表存储栈 。 栈的容量事先不能估计时采用这种存储结构较好 。
栈顶思考：
为什么栈的链式存储中要将栈顶位置作为链表的头，而将栈底位置作为链表的尾？倒过来行不行？
∧
head
进栈算法
void push(nodetype *head,int x)
{nodetype *q;
q=(nodetype*)malloc(sizeof(nodetype));
q->data=x;
q->next=head->next;
head->next=q;
}
头指针进栈元素 x
q
∧
head
进栈算法
void push(nodetype *head,int x)
{nodetype *q;
q=(nodetype*)malloc(sizeof(nodetype));
q->data=x;
q->next=head->next;
head->next=q;
}
xq
∧
head
进栈算法
void push(nodetype *head,int x)
{nodetype *q;
q=(nodetype*)malloc(sizeof(nodetype));
q->data=x;
q->next=head->next;
head->next=q;
}
xq
∧
head
进栈算法
void push(nodetype *head,int x)
{nodetype *q;
q=(nodetype*)malloc(sizeof(nodetype));
q->data=x;
q->next=head->next;
head->next=q;
}
xq
∧
head
进栈算法
void push(nodetype *head,int x)
{nodetype *q;
q=(nodetype*)malloc(sizeof(nodetype));
q->data=x;
q->next=head->next;
head->next=q;
}
x
∧
head
进栈算法
void push(nodetype *head,int x)
{nodetype *q;
q=(nodetype*)malloc(sizeof(nodetype));
q->data=x;
q->next=head->next;
head->next=q;
}
进栈操作结束
∧
head头指针出栈算法
int pop(nodetype *head)
{nodetype *p;
int y;
if (head->next==NULL)
{ printf(“栈空 ！ \n”);
exit(1);}
else
{p=head->next;
y=p->data;
head->next=p->next;
free(p);
return(y);
}
}
p
∧
head
出栈算法
int pop(nodetype *head)
{nodetype *p;
int y;
if (head->next==NULL)
{ printf(“栈空 ！ \n”);
exit(1);}
else
{p=head->next;
y=p->data;
head->next=p->next;
free(p);
return(y);
}
}
p
∧
head
出栈算法
int pop(nodetype *head)
{nodetype *p;
int y;
if (head->next==NULL)
{ printf(“栈空 ！ \n”);
exit(1);}
else
{p=head->next;
y=p->data;
head->next=p->next;
free(p);
return(y);
}
}
∧
head
出栈算法
int pop(nodetype *head)
{nodetype *p;
int y;
if (head->next==NULL)
{ printf(“栈空 ！ \n”);
exit(1);}
else
{p=head->next;
y=p->data;
head->next=p->next;
free(p);
return(y);
}
}
∧
head
出栈操作结束出栈算法
int pop(nodetype *head)
{nodetype *p;
int y;
if (head->next==NULL)
{ printf(“栈空 ！ \n”);
exit(1);}
else
{p=head->next;
y=p->data;
head->next=p->next;
free(p);
return(y);
}
}
r
主函数
s
rr
r
s
子函数
1 r
s
t
子函数
2 rs
t 子函数
3
三,栈的应用
1,函数的嵌套
2,表达式中左,右括号的匹配问题 。
（
（
（
具体实现策略：
遇到左括号，将其入栈；遇到右括号，
进行出栈操作。若直至表达式结束时，栈的状态一直正常。（出栈操作每次均能正常进行，表达式结束正好栈为空）
小结
1.栈的定义（ 理解 ）
关键点,特殊（操作受限）的线性表栈：限定插入和删除操作仅能在栈顶进行引入原因：实现数据的特殊存取顺序（ 后进先出 ）
2.栈的存储顺序存储（ 掌握 ） 链式存储（ 理解 ）
关键点,与线性表的存储方式类似，但需记下允许操作的特殊位置（ 栈顶）
3.栈的基本操作
（ 1）顺序存储方式（ 掌握 ）算法思想 +程序实现入栈、出栈
（ 2）链式存储方式（ 理解 ）算法思想入栈、出栈
1,栈 和 队列 都是 线性表 。
2,栈 和 队列 都是 操作受限 的线性表。
3、对栈和队列的基本操作进行限制的目的是：为了保证其数据元素 存取的特定顺序 。
即：栈可保证数据元素存取的 后进先出 顺序。
队列可保证数据元素存取的 先进先出 顺序。 。
一,栈的定义栈,限定只能在表的一端进行插入和删除的特殊的线性表 。
设栈 s=（ a1,a2,.,,,ai,.,,,an）,
其中 a1是栈底元素,an是栈顶元素 。
a1
a2
….
an栈顶栈底
2.3.1 栈的定义及基本操作栈顶 （ top)：允许插入和删除的一端；
top始终指向栈中最后一个元素所在的位置 。
栈底 （ bottom):不允许插入和删除的一端 。
思考,对栈的操作一旦进行了这样的限制,它和普通线性表会有怎样的区别？
2.3 栈一,栈的定义栈,限定只能在表的一端进行插入和删除的特殊的线性表 。
设栈 s=（ a1,a2,.,,,ai,.,,,an）,
其中 a1是栈底元素,an是栈顶元素 。
a1
a2
….
an栈顶栈底
a1
a2
….
an栈顶栈底栈的插入操作被称为进栈；
栈的删除操作被称为出栈。
进栈 出栈
栈的特点：后进栈的元素在出栈时较其它元素先。
因此栈被称为后进先出（ LIFO）的线性表。
二,栈的存储结构顺序栈,链栈
a2
a1a1
top
1.顺序栈：
用顺序存储结构表示的栈 。
顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素,一般用一维数组表示,设置一个简单变量 top指示栈顶位置,它始终指向栈中最后一个元素的位置 。
设数组 S是一个顺序栈,栈的最大容量 maxsize=4,初始状态 top=-1
10
25
30
S[4]
2
3
1
0
top
x=s[top]
top=top-1
10
S[4]
2
3
1
0
top=top+1
s[top]=x
top
10进栈
30出栈栈空
S[4]
2
3
1
0
top=-1 top
栈满
top=maxsize-1
10
25
30
40
S[4]
2
3
1
0
top=3
栈中的运算,1.设置空栈 ； 2,插入一个新的栈顶元素 (入栈 )
3,删除栈顶元素 (出栈 ） ； 4,读取栈顶元素 。
#define maxsize 100
typedef struct stacktype
{ datatype stack[maxsize];
int top;
}stacktype;
stacktype *s；
.
.
.
.
.
.
.
.
stack[0]
stack[1]
stack[98]
stack[99]
top
s
用 C语言对顺序栈类型进行的描述注意,datatype在此泛指栈中元素的类型，
实际应用时需按具体情况确定。例如：栈中元素为整型，则 stack应定义为整型数组。
三、顺序栈操作的算法描述（ C语言）
1 构造空栈
void initStack(stacktype *s)
{/*初始化栈 s，置为空栈 */
s->top = -1;
}
2 判断一个栈是否为空栈
int stackEmpty(stacktype *s)
{/* 判断 s是否为空栈，若为空栈，返回 1，否则返回 0 */
return s->top = = -1;
}
if(s->top==-1) return 1;
else return 0;
·进栈算法 （ 假定栈为整型 ）
#define maxsize 10
typedef struct stacktype
{ int stack[maxsize];
int top;
}stacktype;
void push(stacktype *s,int x)
{if(s->top= =maxsize-1)
{printf(“stackoverflow!”);
exit(1);}
else
{ s->top++; /*实际栈顶位置加 1 */
s->stack[s->top]=x;
}
}
a2
a3
a4
9
8
7
6
5
4
3
2
1
a10
top
topx
s->stack[++s->top]=x;
通过地址传递，用 s带回进栈操作后新栈的信息
int pop(stacktype *s)
{int y;
if(s->top= =-1)
{printf(“stack empty!\n”);
exit(1);
}
else
{ y=s->stack[s->top];
s->top--; /*栈顶位置下移 */
return(y); /*返回出栈元素 */
}
}
a2
a3
a4
9
8
7
6
5
4
3
2
1
a10
top
·出栈算法 （ 假定栈为整型 ）
topy=s->stack[s->top--]);
通过地址传递，
用 s带回出栈操作后新栈的信息读栈顶元素算法：
注意：此操作不改变栈顶的位置 。
int readtop(stacktype *s)
{
}
思考：此操作的算法如何编写。
提示：实现语句与出栈算法基本相同，唯一区别在不会改变栈顶的位置。
int y;
if(s->top= =0)
{printf(“stack empty!\n”);
exit(1);}
else
{ y=s->stack[s->top];
return(y); /*返回栈顶元素 */
}
an
an-1
a1 ∧
head
栈底
2.链栈用带头结点的单链表存储栈 。 栈的容量事先不能估计时采用这种存储结构较好 。
栈顶思考：
为什么栈的链式存储中要将栈顶位置作为链表的头，而将栈底位置作为链表的尾？倒过来行不行？
∧
head
进栈算法
void push(nodetype *head,int x)
{nodetype *q;
q=(nodetype*)malloc(sizeof(nodetype));
q->data=x;
q->next=head->next;
head->next=q;
}
头指针进栈元素 x
q
∧
head
进栈算法
void push(nodetype *head,int x)
{nodetype *q;
q=(nodetype*)malloc(sizeof(nodetype));
q->data=x;
q->next=head->next;
head->next=q;
}
xq
∧
head
进栈算法
void push(nodetype *head,int x)
{nodetype *q;
q=(nodetype*)malloc(sizeof(nodetype));
q->data=x;
q->next=head->next;
head->next=q;
}
xq
∧
head
进栈算法
void push(nodetype *head,int x)
{nodetype *q;
q=(nodetype*)malloc(sizeof(nodetype));
q->data=x;
q->next=head->next;
head->next=q;
}
xq
∧
head
进栈算法
void push(nodetype *head,int x)
{nodetype *q;
q=(nodetype*)malloc(sizeof(nodetype));
q->data=x;
q->next=head->next;
head->next=q;
}
x
∧
head
进栈算法
void push(nodetype *head,int x)
{nodetype *q;
q=(nodetype*)malloc(sizeof(nodetype));
q->data=x;
q->next=head->next;
head->next=q;
}
进栈操作结束
∧
head头指针出栈算法
int pop(nodetype *head)
{nodetype *p;
int y;
if (head->next==NULL)
{ printf(“栈空 ！ \n”);
exit(1);}
else
{p=head->next;
y=p->data;
head->next=p->next;
free(p);
return(y);
}
}
p
∧
head
出栈算法
int pop(nodetype *head)
{nodetype *p;
int y;
if (head->next==NULL)
{ printf(“栈空 ！ \n”);
exit(1);}
else
{p=head->next;
y=p->data;
head->next=p->next;
free(p);
return(y);
}
}
p
∧
head
出栈算法
int pop(nodetype *head)
{nodetype *p;
int y;
if (head->next==NULL)
{ printf(“栈空 ！ \n”);
exit(1);}
else
{p=head->next;
y=p->data;
head->next=p->next;
free(p);
return(y);
}
}
∧
head
出栈算法
int pop(nodetype *head)
{nodetype *p;
int y;
if (head->next==NULL)
{ printf(“栈空 ！ \n”);
exit(1);}
else
{p=head->next;
y=p->data;
head->next=p->next;
free(p);
return(y);
}
}
∧
head
出栈操作结束出栈算法
int pop(nodetype *head)
{nodetype *p;
int y;
if (head->next==NULL)
{ printf(“栈空 ！ \n”);
exit(1);}
else
{p=head->next;
y=p->data;
head->next=p->next;
free(p);
return(y);
}
}
r
主函数
s
rr
r
s
子函数
1 r
s
t
子函数
2 rs
t 子函数
3
三,栈的应用
1,函数的嵌套
2,表达式中左,右括号的匹配问题 。
（
（
（
具体实现策略：
遇到左括号，将其入栈；遇到右括号，
进行出栈操作。若直至表达式结束时，栈的状态一直正常。（出栈操作每次均能正常进行，表达式结束正好栈为空）
小结
1.栈的定义（ 理解 ）
关键点,特殊（操作受限）的线性表栈：限定插入和删除操作仅能在栈顶进行引入原因：实现数据的特殊存取顺序（ 后进先出 ）
2.栈的存储顺序存储（ 掌握 ） 链式存储（ 理解 ）
关键点,与线性表的存储方式类似，但需记下允许操作的特殊位置（ 栈顶）
3.栈的基本操作
（ 1）顺序存储方式（ 掌握 ）算法思想 +程序实现入栈、出栈
（ 2）链式存储方式（ 理解 ）算法思想入栈、出栈
