알고리즘 기초 6 - [자료구조, 덱]

Dequeue

덱 ( 이중 링크드 리스트로 구현)

FIFO + LIFO (Stack + Queue)

Stack

• putFront
• getBack

Queue

• putBack
• getFront

 

과정

1. initDeque

 

2. putFront(10) or putBack(10)

 

3. putFront(5)

 

4. putBack(4)

 

5. getBack()

 

6. getFront()

 

---

 

Java

class Deque {

    static class Node {
        int data;
        Node next;
        Node prev;

        public Node(int data) {
            this.data = data;
            this.next = null;
            this.prev = null;
        }
    }

    static Node front, rear, ptrNode;

    public static void initDeque() {
        front = new Node(-1);
        rear = new Node(-1);

        front.prev = rear;
        fornt.next = rear;

        rear.prev = front;
        rear.next = front;
    }

    public static void putBack(int data) {
        ptrNode = new Node(data);

        if(front.next == rear) {
            front.next = ptrNode;

            ptrNode.prev = front;
            ptrNode.next = rear;

            rear.next = ptrNode;
        } else {

            rear.next.next = ptrNode;

            ptrNode.prev = rear.next;
            ptrNode.next = rear;
            rear.next = ptrNode;
        }
    }

    public static void putFront(int data) {
        ptrNode = new Node(data);

        if(front.next == rear) {
            front.next = ptrNode;

            ptrNode.prev = front;
            ptrNode.next = rear;

            rear.next = ptrNode;
        } else {
            ptrNode.next = front.next;
            ptrNode.prev = front;
            front.next = ptrNode;
        }
    }

    public static int getFront() {
        Node ptrTemp = front.next;
        int ret = -1;

        if(front.next == rear) {
            System.out.println("empty");
            return ret;
        }

        ret = ptrTemp.data;
        front.next = ptrTemp.next;

        System.out.println("get Front() : "+ ret );
        return ret;
    }

    public static int getBack() {
        Node ptrTemp = rear.next;
        int ret = -1;

        if(front.next == rear) {
            System.out.println("empty");
            return ret;
        }

        ret = ptrTemp.data;
        ptrTemp.prev.next = rear;
        rear.next = ptrTemp.prev;

        System.out.println("get Back() : "+ ret );
        return ret;
    }


    public static void display() {
        Node ptrTemp;

        if(front.next == rear) {
            System.out.println("empty");
        } else {
            for(ptrTemp = front.next; ptrTemp.next != rear; ptrTemp = ptrTemp.next) {
                System.out.print(ptrTemp.data + " -> ");
            }
            System.out.println(); 
        }
    }

    public  static  void  main(String[] args) {

        int  ret = 0;

        initDeque();

        putFront(1);
        putBack(2);
        putFront(10);
        display();

        ret = getFront();
        ret = getBack();
        display();

        ret = getBack();
        display(); 

        putBack(3);
        putBack(5);
        display();

        ret = getFront();

        display();
    }
}
// 결과
// 10 -> 1 -> 2
// get Front() : 10
// get Back() : 2
// 1
// get Back() : 1
// empty
// 3 -> 5
// get Front() : 3
// 5

---

 

---

JavaScript

    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
            this.prev = null;
        }
    }

    let front, rear, ptrNode;

    const initDeque = () => {
        front = new Node(-1);
        rear = new Node(-1);

        front.prev = rear;
        front.next = rear;

        rear.prev = front;
        rear.next = front;
    }

    const putBack = (data) => {
        ptrNode = new Node(data);

        if(front.next === rear) {
            front.next = ptrNode;

            ptrNode.prev = front;
            ptrNode.next = rear;

            rear.next = ptrNode;
        } else {

            rear.next.next = ptrNode;

            ptrNode.prev = rear.next;
            ptrNode.next = rear;
            rear.next = ptrNode;
        }
    }

    const putFront = (data) =>  {
        ptrNode = new Node(data);

        if(front.next === rear) {
            front.next = ptrNode;

            ptrNode.prev = front;
            ptrNode.next = rear;

            rear.next = ptrNode;
        } else {
            ptrNode.next = front.next;
            ptrNode.prev = front;
            front.next = ptrNode;
        }
    }

    const getFront = () => {
        let ptrTemp = front.next;
        let ret = -1;

        if(front.next === rear) {
            consoel.log("empty");
            return ret;
        }

        ret = ptrTemp.data;
        front.next = ptrTemp.next;

        console.log("get Front() : "+ ret );
        return ret;
    }

    const getBack = ()  => {
        let ptrTemp = rear.next;
        let ret = -1;

        if(front.next === rear) {
            console.log("empty");
            return ret;
        }

        ret = ptrTemp.data;
        ptrTemp.prev.next = rear;
        rear.next = ptrTemp.prev;

        console.log("get Back() : "+ ret );
        return ret;
    }


    const display = () => {
        let ptrTemp;
        let str = "";
        if(front.next === rear) {
            console.log("empty");
        } else {
            for(ptrTemp = front.next; ptrTemp.next !== rear; ptrTemp = ptrTemp.next) {
                str += `${ptrTemp.data} -> `;
            }
            str += `${ptrTemp.data}`;
            console.log(str); 
        }
    }

    const main = () => {

        let ret = 0;

        initDeque();

        putFront(1);
        putBack(2);
        putFront(10);
        display();

        ret = getFront();
        ret = getBack();
        display();

        ret = getBack();
        display(); 

        putBack(3);
        putBack(5);
        display();

        ret = getFront();

        display();
    }

    main();
// 결과
// 10 -> 1 -> 2
// get Front() : 10
// get Back() : 2
// 1
// get Back() : 1
// empty
// 3 -> 5
// get Front() : 3
// 5

---