Deque ADT接口 DEQUEUE.h:
#include <stdlib.h>
#include "Item.h" typedef struct DEQUEUEnode *link;
struct DEQUEUEnode
{
Item item;
link next;
link last;
}; void DEQUEUEinit(int);
void DEQUEUEerror(void);
Item DEQUEUEheadget(void);
Item DEQUEUEtailget(void);
void DEQUEUEheadput(Item);
void DEQUEUEtailput(Item);
int DEQUEUEisEmpty(void);
int DEQUEUEisFull(void);
Deque ADT接口实现 DEQUEUE.c:
static link head,tail;
static int N; //备用 void DEQUEUEinit(int maxN)
{
head=malloc(sizeof(*head));
tail=head;
tail->next=NULL;
tail->last=NULL;
head->next=NULL;
head->last=NULL;
N=maxN;
}
void DEQUEUEerror(void)
{
printf("节点为空或节点已满");
exit();
}
Item DEQUEUEheadget(void)
{
Item temp;
temp=head->item;
head=head->next;
free(head->last);
head->last=NULL;
return temp;
}
Item DEQUEUEtailget(void)
{
Item temp;
tail=tail->last;
temp=tail->item;
free(tail->next);
tail->next=NULL;
return temp;
}
void DEQUEUEheadput(Item value)
{
head->last=malloc(sizeof(*head));
if(DEQUEUEisFull())
DEQUEUEerror();
head->last->next=head;
head=head->last;
head->item=value;
head->last=NULL;
}
void DEQUEUEtailput(Item value)
{
tail->item=value;
tail->next=malloc(sizeof(*head));
if(DEQUEUEisFull())
DEQUEUEerror();
tail->next->last=tail;
tail=tail->next;
tail->next=NULL;
}
int DEQUEUEisEmpty(void)
{
if(head==NULL&&tail==NULL)
return ;
return ;
}
int DEQUEUEisFull(void)
{
if((head==NULL&&tail!=NULL)||(head!=NULL&&tail==NULL))
return ;
return ;
}
Item.h:
1 typedef char Item;
主程序 main.c：
#include <stdio.h> int main(void)
{
int N; printf("输入需要申请内存大小:");
if(scanf("%d", &N))
DEQUEUEinit(N);
else
DEQUEUEerror();
getchar();
printf("输入%d个字符",N);
printf("('+'从队头get '*'从队尾get '大写字母'"
"从队头put '小写字母'从队尾put):\n"); while((N=getchar())!='\n')
{
switch(N)
{
case '+':
putchar(DEQUEUEheadget());
break;
case '*':
putchar(DEQUEUEtailget());
break;
default:
if(N>&&N<)
DEQUEUEheadput(N);
else
DEQUEUEtailput(N);
}
} return ;
}