双端队列 ADT接口 数组实现
程序员文章站
2022-07-14 14:19:14
...
Deque ADT接口 DEQUEUE.h
#include <stdlib.h>
#include "Item.h"
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
#include "DEQUEUE.h"
static Item *q;
static int N,head,tail;
void DEQUEUEinit(int maxN)
{
q=malloc(maxN*sizeof(Item));
if(q==NULL)
DEQUEUEerror();
head=0;
tail=0;
N=maxN;
}
void DEQUEUEerror(void)
{
printf("\n空间可能已满或为空");
exit(1);
}
Item DEQUEUEheadget(void)
{
if(DEQUEUEisEmpty())
DEQUEUEerror();
Item temp=q[head];
head=(head+1)%N;
return temp;
}
Item DEQUEUEtailget(void)
{
if(DEQUEUEisEmpty())
DEQUEUEerror();
tail=(tail-1+N)%N;
return q[tail];
}
void DEQUEUEheadput(Item ch)
{
if(DEQUEUEisFull())
DEQUEUEerror();
head=(head-1+N)%N;
q[head]=ch;
}
void DEQUEUEtailput(Item ch)
{
if(DEQUEUEisFull())
DEQUEUEerror();
q[tail]=ch;
tail=(tail+1)%N;
}
int DEQUEUEisEmpty(void)
{
if(head==tail)
return 1;
return 0;
}
int DEQUEUEisFull(void)
{
if(((tail+1)%N)==head)
return 1;
return 0;
}
Item.h
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>64&&N<91)
DEQUEUEheadput(N);
else
DEQUEUEtailput(N);
}
}
return 0;
}