第3章 栈和队列要求：
1、掌握栈与队列的逻辑结构；
2、栈和队列的顺序存储和链式存储表示，即顺序栈、链栈如何表示；链队列与循环队列如何表示；
3、不同存储方式下操作算法。
教材习题参考解答：
3.1 (1)有5种：123、321、132、213、231
(2)能得到135426，不能得到435612。
3.2 A
3.3
一、顺序栈
#define MAXSIZE 100
typedef struct
{
ElemType elem[MAXSIZE];
int top;
}SeqStack;
int IsEmpty(SeqStack *pS)
{
return (pS->top==-1? 1,0);
}
int IsFull(SeqStack *pS)
{
return (pS->top == MAXSIZE-1? 1,0);
}
二、链栈
typedef struct next
{
ElemType data;
struct node * next;
}NODE,*LinkStack;
int IsEmpty(LinkStack S)
{
return (S->next == NULL? 1,0);
}
3.4 参考教材P59～60
3.5 //此程序为判断一个字符串是否为回文。字符串以'@'结尾，
//中间以'&'分隔
//程序的实现通过一个栈和一个队列来实现，首先将'&'以前的所有字符压入栈
//然后将'&'后的字符加入队列，再分别进行出栈和出队处理，比较栈顶和队头的字符
#include <stdio.h>
#include <stdlib.h>
//栈和队列均用链表实现，队列用循环队列
typedef struct node
{
char data;
struct node *next;
}NODE,*LinkStack,*LinkQueue;
//初始化栈，创建一个头结点
void InitStack(LinkStack *pS)
{
LinkStack p;
p = (LinkStack)malloc(sizeof(NODE));
p->next = NULL;
*pS = p;
}
//入栈算法
int Push(LinkStack S,char e)
{
LinkStack p;
p = (LinkStack)malloc(sizeof(NODE));
if(!p) //若创建结点不成功则返回0
return 0;
//将新创建结点插入头结点之后
p->data = e;
p->next = S->next;
S->next = p;
return 1;
}
//出栈算法
int Pop(LinkStack S,char *pe)
{
LinkStack p;
if(S->next == NULL) //若栈为空，则不能出栈，返回0
return 0;
p = S->next;
S->next = p->next;
*pe = p->data;
free(p);
return 1;
}
//初始化队列算法
void InitQueue(LinkQueue *pQ)
{
LinkQueue p;
p = (LinkStack)malloc(sizeof(NODE));
p->next = p; //形成一个环形链表
p->data = 0;
*pQ = p;
}
//进队算法，pQ为指向队尾结点的指针的指针
int EnQueue(LinkQueue *pQ,char e)
{
LinkQueue p,Q;
Q = *pQ; //让Q指向队尾
p = (LinkStack)malloc(sizeof(NODE));
if(!p) //如果创建结点不成功
return 0;
//将p结点插入pQ之后
p->data = e;
p->next = Q->next;
Q->next = p;
*pQ = p;
return 1;
}
//出队算法
int DeQueue(LinkQueue *pQ,char *pe)
{
LinkQueue p,Q;
Q = *pQ;
Q = *pQ; //让Q指向队尾
Q = Q->next; //让Q指向头结点
if( Q == *pQ ) //如果仅有头结点，则说明队列为空
return 0;
//如果不为空队，则进行出队处理
//先让p指向头结点的后继结点，再将p结点删除
p = Q->next;
*pe = p->data;
Q->next = p->next;
free(p);
//如果出队后为空队，则原队尾指针的值要改变，即指向头节点
if( Q->next == Q)
*pQ = Q;
return 1;
}
void main()
{
char str[80],ch1,ch2,*p;
int z=0,sf=1;
LinkStack S;
LinkQueue Q;
InitStack(&S);
InitQueue(&Q);
printf("请输入一个待判断是否为回文的字符串，以'@'结尾，中间为'&'：\n");
gets(str);
p = str;
//分别对'&'前面的字符入栈，对后面的字符进队
while(*p)
{
if( (z==0) && (*p != '&') && (*p !='@') )
Push(S,*p);
if( (z==1) && (*p != '&') && (*p !='@') )
EnQueue(&Q,*p);
if( *p == '&' )
z = 1;
if( *p == '@')
break;
p++;
}
while( Pop(S,&ch1) && DeQueue(&Q,&ch2))
{
if(ch1 != ch2)
{
printf("不是回文！\n");
sf = 0;
break;
}
}
if(sf==1 && !Pop(S,&ch1) && !DeQueue(&Q,&ch2))
printf("是回文！\n");
else
if(sf==1)
printf("不是回文！\n");
}
解法二：//利用栈实现回文判断
#include <stdio.h>
#include <stdlib.h>
#define MAX 80
//定义顺序栈结构
typedef struct
{
char elem[MAX];
int top;
}STACK;
void Init_Stack(STACK *pS)
{
pS->top = -1; //top为栈顶元素在数组elem中的下标，由于开始没有元素，则为－1
}
int Push(STACK *pS,char e)
{
if(pS->top >= MAX-1)
return 0;
pS->top++; //改变栈顶位置
pS->elem[pS->top] = e;
return 1;
}
int Pop(STACK *pS,char *pe)
{
if(pS->top == -1)
return 0;
*pe = pS->elem[pS->top];
pS->top--;
return 1;
}
void main()
{
char str[80],c1,c2,*p;
STACK S;
Init_Stack(&S);
printf("请输入一串以'@'结尾中间为'&'字符的字符串：");
gets(str);
p = str;
//将'&'前面的字符依次入栈
while(*p != '&' && *p != '\0')
{
if(!Push(&S,*p))
{
printf("栈空间溢出！");
exit(0);
}
p++;
}
p++; //跳过'&'字符
//依次取出'&'后面的字符，每取一个字符就和从栈中弹出的一个字符比较，如果相等
//则继续取下一个。
while(*p != '@' && *p != '\0')
{
c1 = *p;
if(!Pop(&S,&c2))
{
printf("栈已为空，不是回文，'&'前面的字符少！\n");
exit(0);
}
if( c1 != c2)
{
printf("对应字符不相等，不是回文！\n");
exit(0);
}
p++;
}
if(Pop(&S,&c2))
{
printf("'&'前的字符比后面多，栈内还有字符，不是回文！\n");
exit(0);
}
else
printf("是回文！\n");
}
3.6 逆波兰式就是运算符在两个运算数后面的运算式，方法与表达式求值类似。
3.7 //仅用队尾指针指向环行链表表示队列的三个算法
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data; //设队列的元素为整数类型
struct node *next;
}Node;
typedef struct
{
Node *front; //指向队头的指针
Node *rear; //指向队尾的指针
}LinkQueue;
void Init(LinkQueue *pQ)
{
Node *p;
p = (Node *)malloc(sizeof(Node));
p->next = p; //形成一个环链
pQ->rear = p; //队尾指针指向环链
}
void EnQueue(LinkQueue *pQ,int e)
{
Node *p,*q;
p = (Node *)malloc(sizeof(Node));
q = pQ->rear; //让q指向队尾结点
p->next = q->next;//以下两个语句将p所指结点插到q所指结点的后面
q->next = p;
p->data = e;
pQ->rear = p; //p所指结点成为新的队尾
}
int DeQueue(LinkQueue *pQ,int *pe)
{
Node *p,*q;
q = pQ->rear->next; //让q指向链的头结点
if(q->next == q) //队为空则不能出队
return (0);
p = q->next; //p指向队头结点
q->next = p->next; //将p所指结点从链中断开
if(pQ->rear == p) //若p所指结点又是队尾结点，则删除p后成为空队
pQ->rear = q;
free(p);
return(1);
}
void Print(LinkQueue *pQ)
{
Node *p,*q;
q = pQ->rear->next; //q指向头结点
p = q->next; //p指向队头结点
while(p != q)
{
printf("%d\t",p->data);
p = p->next;
}
printf("\n");
}
void main()
{
int i;
LinkQueue Q;
Init(&Q);
EnQueue(&Q,10);
EnQueue(&Q,20);
Print(&Q);
EnQueue(&Q,30);
DeQueue(&Q,&i);
Print(&Q);
}
3.8 //p77习题3.8
#include <stdio.h>
#define MAXSIZE 20
typedef struct
{
int element[MAXSIZE];
int front;
int rear;
int flag; //flag为 0 表示队列不满，为 1 表示队列满
}SeqQueue;
void Init(SeqQueue *pQ)
{
pQ->flag = 0;
pQ->rear = 0;
pQ->front = 0;
}
int EnQueue(SeqQueue *pQ,int e)
{
if(pQ->flag == 0)
{
pQ->element[pQ->rear] = e;
pQ->rear = (pQ->rear + 1) % MAXSIZE;
if(pQ->rear == pQ->front) //若进队后rear与front相等，则队列满
pQ->flag = 1;
return(1);
}
else
return(0);
}
int DeQueue(SeqQueue *pQ,int *pe)
{
if((pQ->flag == 0)&&(pQ->front == pQ->rear))
return (0);
*pe = pQ->element[pQ->front];
pQ->front = (pQ->front + 1) % MAXSIZE;
if(pQ->flag == 1) //若原来是满队列，则出队一个后变为不满
pQ->flag = 0;
return(1);
}
void main()
{
SeqQueue Q;
int e,i;
Init(&Q);
EnQueue(&Q,10);
EnQueue(&Q,20);
EnQueue(&Q,30);
DeQueue(&Q,&e);
printf("出队的元素是：%d \n",e);
printf("队列中剩下的的元素是：");
for(i = Q.front; i != Q.rear; i = (i + 1)%MAXSIZE)
printf("%d\t",Q.element[i]);
}
3.9 (1)将栈S中元素逆置
(2)将栈S中元素e删除
(3)将队列Q中元素逆置
补充练习：
1、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，则当做出栈处理时，top变化为 。
A) top不变 B) top=0 C) top-- D) top++
2、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为 。
A) rear%n=front B) front%n+1=rear C) rear%n=front D)rear%n+1=front
3、一个中缀算术表达式为1+(3-x)*y，则其对应的后缀算术表达式为 。
A) 1 3 +x –y* B) 1 3 x +-y * C)1 3 x –y *+ D) 1 3 x y -+*
4、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入*s结点的操作应执行 。
A) front->next=s; front=s; B)s->next=rear; rear=s;
C) rear->next=s; rear=s; D)s->next=front; front=s;
5、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作应执行 。
A) front=front->next; B)rear=rear->next;
C) rear=front->next; D)front=rear->next;
6、写出下列程序段的输出结果（其中栈的元素类型SElemType为char）
void main()
{ Stack S; char x,y;
InitStack(S);
x=’c’; y=’k’;
Push(S,x); Push(S,’a’); Push(S,y); Pop(S,x);
Push(S,’t’); Push(S,x); Pop(S,x); Push(S,’s’);
while(!StackEmpty(S)){Pop(S,y); printf(y); };
printf(x);
}
7、写出以下程序段的输出结果（队列中的元素类型QElemType为char）。
void main()
{ Queue Q; char x=’e’,y=’c’;
InitQueue(Q);
EnQueue(Q,’h’); EnQueue(Q,’r’); EnQueue(Q,y); DeQueue(Q,x);
EnQueue(Q,x); DeQueue(Q,x); EnQueue(Q,’a’);
while(!QueueEmpty(Q)){ DeQueue(Q,y); printf(y);}
printf(x);
}
8、若栈用顺序存储表示，其栈的元素类型为整型，类型定义如下：
#define MAXSIZE 1000
typedef struct{
int elem[MAXSIZE]; //用来存放栈元素的数组，下标从0开始
int top; //指向栈顶位置的域，栈底为位置0
}Stack;
请补全以下栈操作函数：（用C语言）
（1）判断栈S是否为空栈：若为空，则返回1，不为空则返回0
int StackEmpty(Stack S){
if( )return (1);
else;
}
（2）入栈操作：若栈满，则返回0，不满，则入栈，返回1
int Push(Stack *p,int e){ //p为指向栈的指针，e为待入栈的元素
if( )return(0);//栈满，则返回0
=e; //入栈
p->top+=1; //栈顶位置变化
return(1);
}
9、简述栈、队列和线性表的差别和联系。
参考解答：1、C 2、D 3、C 4、C 5、A 6、stack 7、char
8、S.top==0或!(S.top) return(0) p->top>=MAXSIZE-1 p->elem[p->top]
1、掌握栈与队列的逻辑结构；
2、栈和队列的顺序存储和链式存储表示，即顺序栈、链栈如何表示；链队列与循环队列如何表示；
3、不同存储方式下操作算法。
教材习题参考解答：
3.1 (1)有5种：123、321、132、213、231
(2)能得到135426，不能得到435612。
3.2 A
3.3
一、顺序栈
#define MAXSIZE 100
typedef struct
{
ElemType elem[MAXSIZE];
int top;
}SeqStack;
int IsEmpty(SeqStack *pS)
{
return (pS->top==-1? 1,0);
}
int IsFull(SeqStack *pS)
{
return (pS->top == MAXSIZE-1? 1,0);
}
二、链栈
typedef struct next
{
ElemType data;
struct node * next;
}NODE,*LinkStack;
int IsEmpty(LinkStack S)
{
return (S->next == NULL? 1,0);
}
3.4 参考教材P59～60
3.5 //此程序为判断一个字符串是否为回文。字符串以'@'结尾，
//中间以'&'分隔
//程序的实现通过一个栈和一个队列来实现，首先将'&'以前的所有字符压入栈
//然后将'&'后的字符加入队列，再分别进行出栈和出队处理，比较栈顶和队头的字符
#include <stdio.h>
#include <stdlib.h>
//栈和队列均用链表实现，队列用循环队列
typedef struct node
{
char data;
struct node *next;
}NODE,*LinkStack,*LinkQueue;
//初始化栈，创建一个头结点
void InitStack(LinkStack *pS)
{
LinkStack p;
p = (LinkStack)malloc(sizeof(NODE));
p->next = NULL;
*pS = p;
}
//入栈算法
int Push(LinkStack S,char e)
{
LinkStack p;
p = (LinkStack)malloc(sizeof(NODE));
if(!p) //若创建结点不成功则返回0
return 0;
//将新创建结点插入头结点之后
p->data = e;
p->next = S->next;
S->next = p;
return 1;
}
//出栈算法
int Pop(LinkStack S,char *pe)
{
LinkStack p;
if(S->next == NULL) //若栈为空，则不能出栈，返回0
return 0;
p = S->next;
S->next = p->next;
*pe = p->data;
free(p);
return 1;
}
//初始化队列算法
void InitQueue(LinkQueue *pQ)
{
LinkQueue p;
p = (LinkStack)malloc(sizeof(NODE));
p->next = p; //形成一个环形链表
p->data = 0;
*pQ = p;
}
//进队算法，pQ为指向队尾结点的指针的指针
int EnQueue(LinkQueue *pQ,char e)
{
LinkQueue p,Q;
Q = *pQ; //让Q指向队尾
p = (LinkStack)malloc(sizeof(NODE));
if(!p) //如果创建结点不成功
return 0;
//将p结点插入pQ之后
p->data = e;
p->next = Q->next;
Q->next = p;
*pQ = p;
return 1;
}
//出队算法
int DeQueue(LinkQueue *pQ,char *pe)
{
LinkQueue p,Q;
Q = *pQ;
Q = *pQ; //让Q指向队尾
Q = Q->next; //让Q指向头结点
if( Q == *pQ ) //如果仅有头结点，则说明队列为空
return 0;
//如果不为空队，则进行出队处理
//先让p指向头结点的后继结点，再将p结点删除
p = Q->next;
*pe = p->data;
Q->next = p->next;
free(p);
//如果出队后为空队，则原队尾指针的值要改变，即指向头节点
if( Q->next == Q)
*pQ = Q;
return 1;
}
void main()
{
char str[80],ch1,ch2,*p;
int z=0,sf=1;
LinkStack S;
LinkQueue Q;
InitStack(&S);
InitQueue(&Q);
printf("请输入一个待判断是否为回文的字符串，以'@'结尾，中间为'&'：\n");
gets(str);
p = str;
//分别对'&'前面的字符入栈，对后面的字符进队
while(*p)
{
if( (z==0) && (*p != '&') && (*p !='@') )
Push(S,*p);
if( (z==1) && (*p != '&') && (*p !='@') )
EnQueue(&Q,*p);
if( *p == '&' )
z = 1;
if( *p == '@')
break;
p++;
}
while( Pop(S,&ch1) && DeQueue(&Q,&ch2))
{
if(ch1 != ch2)
{
printf("不是回文！\n");
sf = 0;
break;
}
}
if(sf==1 && !Pop(S,&ch1) && !DeQueue(&Q,&ch2))
printf("是回文！\n");
else
if(sf==1)
printf("不是回文！\n");
}
解法二：//利用栈实现回文判断
#include <stdio.h>
#include <stdlib.h>
#define MAX 80
//定义顺序栈结构
typedef struct
{
char elem[MAX];
int top;
}STACK;
void Init_Stack(STACK *pS)
{
pS->top = -1; //top为栈顶元素在数组elem中的下标，由于开始没有元素，则为－1
}
int Push(STACK *pS,char e)
{
if(pS->top >= MAX-1)
return 0;
pS->top++; //改变栈顶位置
pS->elem[pS->top] = e;
return 1;
}
int Pop(STACK *pS,char *pe)
{
if(pS->top == -1)
return 0;
*pe = pS->elem[pS->top];
pS->top--;
return 1;
}
void main()
{
char str[80],c1,c2,*p;
STACK S;
Init_Stack(&S);
printf("请输入一串以'@'结尾中间为'&'字符的字符串：");
gets(str);
p = str;
//将'&'前面的字符依次入栈
while(*p != '&' && *p != '\0')
{
if(!Push(&S,*p))
{
printf("栈空间溢出！");
exit(0);
}
p++;
}
p++; //跳过'&'字符
//依次取出'&'后面的字符，每取一个字符就和从栈中弹出的一个字符比较，如果相等
//则继续取下一个。
while(*p != '@' && *p != '\0')
{
c1 = *p;
if(!Pop(&S,&c2))
{
printf("栈已为空，不是回文，'&'前面的字符少！\n");
exit(0);
}
if( c1 != c2)
{
printf("对应字符不相等，不是回文！\n");
exit(0);
}
p++;
}
if(Pop(&S,&c2))
{
printf("'&'前的字符比后面多，栈内还有字符，不是回文！\n");
exit(0);
}
else
printf("是回文！\n");
}
3.6 逆波兰式就是运算符在两个运算数后面的运算式，方法与表达式求值类似。
3.7 //仅用队尾指针指向环行链表表示队列的三个算法
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data; //设队列的元素为整数类型
struct node *next;
}Node;
typedef struct
{
Node *front; //指向队头的指针
Node *rear; //指向队尾的指针
}LinkQueue;
void Init(LinkQueue *pQ)
{
Node *p;
p = (Node *)malloc(sizeof(Node));
p->next = p; //形成一个环链
pQ->rear = p; //队尾指针指向环链
}
void EnQueue(LinkQueue *pQ,int e)
{
Node *p,*q;
p = (Node *)malloc(sizeof(Node));
q = pQ->rear; //让q指向队尾结点
p->next = q->next;//以下两个语句将p所指结点插到q所指结点的后面
q->next = p;
p->data = e;
pQ->rear = p; //p所指结点成为新的队尾
}
int DeQueue(LinkQueue *pQ,int *pe)
{
Node *p,*q;
q = pQ->rear->next; //让q指向链的头结点
if(q->next == q) //队为空则不能出队
return (0);
p = q->next; //p指向队头结点
q->next = p->next; //将p所指结点从链中断开
if(pQ->rear == p) //若p所指结点又是队尾结点，则删除p后成为空队
pQ->rear = q;
free(p);
return(1);
}
void Print(LinkQueue *pQ)
{
Node *p,*q;
q = pQ->rear->next; //q指向头结点
p = q->next; //p指向队头结点
while(p != q)
{
printf("%d\t",p->data);
p = p->next;
}
printf("\n");
}
void main()
{
int i;
LinkQueue Q;
Init(&Q);
EnQueue(&Q,10);
EnQueue(&Q,20);
Print(&Q);
EnQueue(&Q,30);
DeQueue(&Q,&i);
Print(&Q);
}
3.8 //p77习题3.8
#include <stdio.h>
#define MAXSIZE 20
typedef struct
{
int element[MAXSIZE];
int front;
int rear;
int flag; //flag为 0 表示队列不满，为 1 表示队列满
}SeqQueue;
void Init(SeqQueue *pQ)
{
pQ->flag = 0;
pQ->rear = 0;
pQ->front = 0;
}
int EnQueue(SeqQueue *pQ,int e)
{
if(pQ->flag == 0)
{
pQ->element[pQ->rear] = e;
pQ->rear = (pQ->rear + 1) % MAXSIZE;
if(pQ->rear == pQ->front) //若进队后rear与front相等，则队列满
pQ->flag = 1;
return(1);
}
else
return(0);
}
int DeQueue(SeqQueue *pQ,int *pe)
{
if((pQ->flag == 0)&&(pQ->front == pQ->rear))
return (0);
*pe = pQ->element[pQ->front];
pQ->front = (pQ->front + 1) % MAXSIZE;
if(pQ->flag == 1) //若原来是满队列，则出队一个后变为不满
pQ->flag = 0;
return(1);
}
void main()
{
SeqQueue Q;
int e,i;
Init(&Q);
EnQueue(&Q,10);
EnQueue(&Q,20);
EnQueue(&Q,30);
DeQueue(&Q,&e);
printf("出队的元素是：%d \n",e);
printf("队列中剩下的的元素是：");
for(i = Q.front; i != Q.rear; i = (i + 1)%MAXSIZE)
printf("%d\t",Q.element[i]);
}
3.9 (1)将栈S中元素逆置
(2)将栈S中元素e删除
(3)将队列Q中元素逆置
补充练习：
1、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，则当做出栈处理时，top变化为 。
A) top不变 B) top=0 C) top-- D) top++
2、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为 。
A) rear%n=front B) front%n+1=rear C) rear%n=front D)rear%n+1=front
3、一个中缀算术表达式为1+(3-x)*y，则其对应的后缀算术表达式为 。
A) 1 3 +x –y* B) 1 3 x +-y * C)1 3 x –y *+ D) 1 3 x y -+*
4、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入*s结点的操作应执行 。
A) front->next=s; front=s; B)s->next=rear; rear=s;
C) rear->next=s; rear=s; D)s->next=front; front=s;
5、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作应执行 。
A) front=front->next; B)rear=rear->next;
C) rear=front->next; D)front=rear->next;
6、写出下列程序段的输出结果（其中栈的元素类型SElemType为char）
void main()
{ Stack S; char x,y;
InitStack(S);
x=’c’; y=’k’;
Push(S,x); Push(S,’a’); Push(S,y); Pop(S,x);
Push(S,’t’); Push(S,x); Pop(S,x); Push(S,’s’);
while(!StackEmpty(S)){Pop(S,y); printf(y); };
printf(x);
}
7、写出以下程序段的输出结果（队列中的元素类型QElemType为char）。
void main()
{ Queue Q; char x=’e’,y=’c’;
InitQueue(Q);
EnQueue(Q,’h’); EnQueue(Q,’r’); EnQueue(Q,y); DeQueue(Q,x);
EnQueue(Q,x); DeQueue(Q,x); EnQueue(Q,’a’);
while(!QueueEmpty(Q)){ DeQueue(Q,y); printf(y);}
printf(x);
}
8、若栈用顺序存储表示，其栈的元素类型为整型，类型定义如下：
#define MAXSIZE 1000
typedef struct{
int elem[MAXSIZE]; //用来存放栈元素的数组，下标从0开始
int top; //指向栈顶位置的域，栈底为位置0
}Stack;
请补全以下栈操作函数：（用C语言）
（1）判断栈S是否为空栈：若为空，则返回1，不为空则返回0
int StackEmpty(Stack S){
if( )return (1);
else;
}
（2）入栈操作：若栈满，则返回0，不满，则入栈，返回1
int Push(Stack *p,int e){ //p为指向栈的指针，e为待入栈的元素
if( )return(0);//栈满，则返回0
=e; //入栈
p->top+=1; //栈顶位置变化
return(1);
}
9、简述栈、队列和线性表的差别和联系。
参考解答：1、C 2、D 3、C 4、C 5、A 6、stack 7、char
8、S.top==0或!(S.top) return(0) p->top>=MAXSIZE-1 p->elem[p->top]
