欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

双端队列 ADT接口 链表实现

程序员文章站 2022-07-14 14:16:39
...

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(1);
}
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 1;
    return 0;
}
int DEQUEUEisFull(void)
{
    if((head==NULL&&tail!=NULL)||(head!=NULL&&tail==NULL))
        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;
}

 

相关标签: 双端队列