Deque

 

Deque(덱)은 양방향으로 데이터를 꺼내거나, 삽입 할 수 있는 자료구조를 의미한다.

출처:https://www.geeksforgeeks.org/difference-between-queue-and-deque-queue-vs-deque/

 

구현

 

덱의 구현은 양방향연결리스트의 소스를 참고하여 활용하면 비교적 간단하게 만들 수 있다.

 

헤더 

#ifndef _DQUE_H

#define _DQUE_H

typedef int data;

typedef struct _node{

    data data;

    struct _node* next;

    struct _node* pre;

   

}node;

typedef struct _Dque{

    node* head;

    node* tail;

    int size;

}Dque;

typedef Dque Deque;

void DequeInit(Deque* pq1);

int DQisEmpty(Deque* pq1);

void DQAddFirst(Deque* pq1,data data);

void DQAddLast(Deque* pq1,data data);

data DQRemoveFirst(Deque* pq1);

data DQRemoveLast(Deque* pq1);

data DQgetFirst(Deque* pq1);

data DQfetLast(Deque* pq1);

#endif

소스 

#include "Deque.h"

#include <stdio.h>

#include <stdlib.h>

void DequeInit(Deque* pq1){

    pq1->head = NULL;

    pq1->tail = NULL;

   

}

int DQisEmpty(Deque* pq1){

    if(pq1 -> head =NULL) return 1;

    else return 0;

}

void DQAddFirst(Deque* pq1,data data){

    node* newnode = (node*)malloc(sizeof(node));

    newnode->data = data;

   

    newnode -> next = pq1->head;

   

    if(DQisEmpty(pq1)){

        pq1->tail = newnode;

    }else{

        pq1->head->pre=newnode;

    }

    newnode->pre = NULL;

    pq1->head = newnode;

   

}

void DQAddLast(Deque* pq1,data data){

    node* newnode = (node*)malloc(sizeof(node));

    newnode -> data = data;

    newnode->next = NULL;

    newnode -> pre = pq1->tail;

    if(DQisEmpty(pq1)){

        pq1->head = newnode;

    }else{

        pq1->tail->next = newnode;

    }

   newnode->next = NULL;

    pq1->tail = newnode;

}

data DQRemoveFirst(Deque* pq1){

    if(DQisEmpty(pq1)){

        exit(-1);

    }

    node* renode = pq1->head;

    data Data = renode->data;

   

    pq1->head = pq1->head->next;

    free(renode);

   

    if(pq1->head == NULL)

    pq1->tail == NULL;

    else

    pq1->head->pre=NULL;

    return Data;

}

data DQRemoveLast(Deque* pq1){

    if(DQisEmpty){

        exit(-1);

    }

     node* renode = pq1->tail;

    data Data = renode->data;

   

    pq1->tail = pq1->tail->pre;

    free(renode);

    if(pq1->tail == NULL)

    pq1->head = NULL;

    else

    pq1->tail->next=NULL;

    return Data;

}

data DQgetFirst(Deque* pq1){

if(DQisEmpty){

    exit(-1);

}

return pq1->head->data;

}

data DQfetLast(Deque* pq1){

if(DQisEmpty){

    exit(-1);

}

return pq1->head->data;

}

자바

class MyDequeue<T>{

    private Node<T> head;
    private Node<T> tail;

    MyDequeue(){
        head =null;
        tail = null;
    }

    boolean isEmpty(){
        if(head == null) return true;
        return false;
    }

    void addFrount(T data){
        Node<T> newnode = new Node<>();
        newnode.data =data;
        newnode.next = head;
        newnode.pre = null;

        if(isEmpty()){
            tail = newnode;
        }else
            head.pre = newnode;


        head = newnode;
    }
    void addLast(T data){
        Node<T> newnode = new Node<>();
        newnode.data = data;
        newnode.pre = tail;
        newnode.next = null;

        if(isEmpty()){
            head = newnode;
        }else{
            tail.next = newnode;
        }
        tail = newnode;
    }

    T removeFrount(){
        if(isEmpty()){
            System.out.print("빈큐");
            System.exit(-1);
        }
        T redata = head.data;
        head = head.next;


        if(head == null) tail =null;
        else   head.pre = null;

        return redata;
    }

    T removeLast(){
        if(isEmpty()){
            System.out.print("빈큐");
            System.exit(-1);
        }
        T rdata = tail.data;
        tail = tail.pre;
        if(tail==null) head =null;
        else
            tail.next = null;

        return rdata;
    }

    T getFrount(){
        if(isEmpty()){
            System.out.print("빈큐");
            System.exit(-1);
        }
        return head.data;
    }
    T getLast(){
        if(isEmpty()){
            System.out.print("빈큐");
            System.exit(-1);
        }
        return tail.data;
    }


    private class Node<T>{
        T data;
        Node<T> next;
        Node<T> pre;
    }
    }

 

 

참고자료: 윤성우 열혈자료구조