133顺序存储的栈和队列.doc

1．3．3顺序存储的栈和队列
栈的定义
栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：

a0a1a2…an-1插入和删除端
进行插入和删除的一端是浮动端，通常被称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，通常被称为栈底。我们经常将栈用下图的形式描述

an-1an-2..a1a0进栈出栈
top

结论：后进先出（LastInFirstOut），简称为LIFO线性表。

举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。
举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。
请同学自己举例，生活中哪些现象可以用栈原理？
下面我们先给出栈结构的基本操作：
（1）初始化栈InitStack(chara[MAX])
（2）入栈Push(chara[MAX],charx)
（3）出栈Pop(chara[MAX],char*p_n)
（4）获取栈顶元素内容GetTop(chara[MAX],char*p_n)
（5）判断栈是否为空StackEmpty(a[MAX])
表示方法一：
空栈：不能出栈

。。。///////////MAXN-1

1
0
top
-1

MAXN-1….32C0B1A-1

MAXN-1MAXN-22C1B0A-1MAXN-1ZMAXN-22C1B0A-1
top

top

栈中有3个结点栈满
C语言表示栈初始化
#defineMAXN26;
charscack[MAXN];
inttop=-1;

进栈：初值top=-1;
条件：栈满否？（top>=MAXN-1）?
执行语句：stack[++top]=x;

出栈：
条件：栈为空？（top<0）?
执行语句：*p_y=stack[top--]

表示方法二：

MAXN-1210

栈空
top

MAXN-1top
2c1b0aMAXNMAXN-1210top

非满非空栈满
请写出进栈：语句，栈满条件
请写出出栈：语句，栈空条件

#defineMAXN26;
charstack[MAXN];
inttop=0;
intpush(x)
charx;
{if(top>=MAXN)
return(1);
stack[top++]=x;
return(0);
}

intpop(p_y)
char*p_y;
{if(top==0)
return(1);
*p_y=stack[--top];
return(0);
}
简单应用：
【举例1】将从键盘输入的字符序列逆置输出
比如，从键盘上输入：tsetasisihT；算法将输出：Thisisatest
下面我们给出解决这个问题的完整算法。

#defineMAXN100
charstack[MAXN];//定义一个栈结构stack[]
inttop=0;//初始化栈
voidreverseread()
{
charch;
char*p;
while((ch=getchar())!=’\n’)//从键盘输入字符，直到输入换行符为止

push(ch);//将输入的每个字符入栈
while(top>=0){//依次退栈并输出退出的字符
pop(p);
putchar(*p);
}
putchar(‘\n’);
}
【举例2】十进制数值转换成二进制
使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。
比如：(692)10=(1010110100)2，其展转相除的过程如图所示：

下面给出解决这个问题的完整算法。
voidDecimal_Binary()
{
STACKS;//定义栈结构S

InitStack(&S);//初始化栈S
scanf(“%d”,data);//输入十进制正整数

while(data){
Push(&S,data%2);//余数入栈
data/=2;
//被除数data整除以2，得到新的被除数
}
while(!StackEmpty(S)){
//依次从栈中弹出每一个余数，并输出之
Pop(&S,&data);
printf(“%d”,data);
}
}
1．3．2队列及其基本运算
队列的定义
队列特殊性在于限定插入在线性表的一端进行，删除在线性表的另外一端进行。如图所示：
a0a1a2…an-1
演示程序：zhan.c

队头指针(head、front) 队尾指针(tail、rear)
出队位置