栈和队列的基本操作

栈与队的操作
一、实验目的：
1）掌握栈和队的顺序与链接存储结构；
2）掌握栈和队的操作特性；
3) 掌握顺序栈和链队列的基本操作的实现方法。
二、实验内容及要求：
1）分别建立一个空的顺序栈和空的链队列；
2）对已建立的顺序栈和链队列实现插入、删除、取栈顶元素、
取队头元素及输出等基本操作。
1.程序清单
#define null 0
struct node
{int data;
struct node *next;
};
struct node *rear;
struct node *creat(void)
{struct node *p,*front;
int i,n;
scanf("%d",&n);
front=(struct node *)malloc(2);
front->next=null;
for (i=1;i<=n;i++)
{ p=(struct node *)malloc(2);
scanf("%d",&p->data);
p->next=front->next;
front->next=p;
}
rear=front;
while (rear->next!=null)
rear=rear->next;
return(front);
}
struct node *makenull(struct node *front)
{ rear=front;
front->next=null;
return(front);
}
int get(struct node *front)
{ int x;
x=front->next->data;
return(x);
}
struct node *enqueue(struct node *front ,int x)
{struct node *s;
s=(struct node *)malloc(2);
s->data=x;
s->next=rear->next;
rear->next=s ;
rear=s;
return(front);
}
struct node *dequeue(struct node *front)
{struct node *q;
q=front->next;
front->next=front->next->next;
free(q);
return(front);
}
int empty(struct node *front)
{if (front==rear)
return(1);
else
return(0);
}
void print(struct node *front)
{ struct node *p;
p=front;
while(p->next!=null)
{p=p->next;printf("%d",p->data);}
}
main()
{int x,e,y;
struct node *front;
front=creat();
print(front);
e=get(front);
printf(“%d”,e);
scanf("%d",&x);
front=enqueue(front,x);
print(front);
front=dequeue(front);
print(front);
y=empty(front);
printf("%d",y);
makenull(front);
y=empty(front);
printf("%d",y);
}

2、程序清单：
#include
#include
#include
#include
#define MAX 20
#define False 0
#define True 1
typedef struct
{char elem[MAX];
int top;
}SqStack;
char ch;
SqStack S;
void Initial(void)
{S.top=-1;
}

int Push(char ch)
{
if(S.top>=MAX-1) return False;
else {S.top++;
S.elem[S.top]=ch;
return True;
}
}

int Pop(void)
{
if(S.top<=-1) return False;
else {S.top--;
ch=S.elem[S.top+1];
return True;
}
}

int Gettop(void)
{
if(S.top<=-1)
return False;
else {ch=S.elem[S.top];
return True;
}
}

void SqStackPrint(void)
{
int i;
if(S.top<=-1) printf("stack empty!\n");
else {printf("stack all elem is:\n");
for(i=0;i<=S.top;i++)
printf("%c ",S.elem[i]);
printf("\n");
}
}

void main()
{
int j,flag=1;

int temp;
textbackground(3);
textcolor(15);
clrscr();

printf("本程序实现顺序结构的堆栈的操作。\n");
printf("可以进行入栈，出栈，取栈顶元素等操作。\n");

Initial();
while(flag)
{ printf("pleate slect:\n");
printf("1.disp stack all elem \n");
printf("2.push \n");
printf("3.pop \n");
printf("4.read top \n");
printf("5.exit \n");
scanf("%d",&j);
switch(j)
{case 1:SqStackPrint();
break;
case 2:printf("pleate input push stack elem(a char):");
scanf(" %c",&ch);
temp=Push(ch);
if(temp==False) printf("stack full! error!\n");
else {printf("PUSH OK!\n");
SqStackPrint();
}
break;
case 3:temp=Pop();
if(temp==False) printf("stack empty!\n");
else {printf("POP OK:%c\n",ch);
SqStackPrint();
}
break;
case 4:temp=Gettop();
if(temp==False) printf("stack empty!\n");
else printf("stack top elem is:%c\n",ch);
break;
default:flag=0;printf("exit !\n");
}
}
getchar();
}