[Data Structure] Stack / Queue / Linked-list

01. Stack / Queue 배열 구조로 구현하기

Stack : LIFO

1. Enqueue: 스택 상단에 요소를 추가합니다.
2. Dequeue: 스택에서 맨 위 요소를 제거합니다.
3. Peek: 스택의 최상위 요소를 제거하지 않고 어떤 값인지 봅니다.
4. IsEmpty: 스택이 비어 있는지 확인합니다.

// Stack
const stack = [];

stack.push("Apple"); // Enqueue [ Apple ]
stack.push("Banana"); // Enqueue [ Apple, Banana ]
stack.push("Orange"); // Enqueue [ Apple, Banana, Orange ]

stack.pop(); // Dequeue -> Orange 제거
// [ Apple, Banana ]

stack[stack.length-1]; // Peek -> Banana

const isEmpty = () => {
    return stack.length == 0; // false
}

Queue : FIFO

1. Enqueue: 큐 뒤쪽에 요소를 추가합니다.
2. Dequeue: 큐에서 맨 앞의 요소를 제거합니다.
3. Peek: 큐의 맨 앞 요소를 제거하지 않고 어떤 값인지 봅니다.
4. IsEmpty: 큐가 비어 있는지 확인합니다.

// Queue
const queue = [];

queue.push("Apple"); // Enqueue [ Apple ]
queue.push("Banana"); // Enqueue [ Apple, Banana ]
queue.push("Orange"); // Enqueue [ Apple, Banana, Orange ]

queue.shift(); // Dequeue -> Apple
// [ Banana, Oragne ]

queue[0]; // Peek -> Banana

const isEmpty = () => { 
    return queue.length == 0; // false
}

 

 

02. linked list를 Class로 구현하기

1. append : 리스트 가장 뒤에 값을 추가합니다.
2. prepend : 리스트 가장 앞에 값을 추가합니다.
3. delete : 원하는 값을 삭제합니다.
4. delete_first : 리스트 가장 앞에 있는 값을 삭제합니다.
5. delete_last : 리스트 가장 뒤에 있는 값을 삭제합니다.
6. display : 리스트를 출력합니다.

class Node {
    constructor(data, next = null) {
        this.data = data;
        this.next = next;
        // 초기 값을 null로 해준 이유는 꼬리 tail부분에 있는 자료는 가르킴을 받는 자료가 뒤에 없기 때문
    }// constructor
}// Node

class LinkedList {
    constructor() {
        this.head = null; // 처음에 데이터가 없다면 head는 null이다.
        this.size = 0;
    }// constructor

    //append
    insertBack(data) {
        let newNode = new Node(data);
        let current;

        if (!this.head) {
            this.head = newNode;
            return
        }

        current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
        this.size++;
    }//insertBack

    //prepend
    insertFirst(data) {
        this.head = new Node(data, this.head);
        this.size++;
    }//insertFirst

    //delete
    deleteData(data) {
        let currentNode = this.head;
        if (currentNode && currentNode.data == data) {
            this.head = currentNode.next;
            currentNode = null;
            return
        }
        let prevNode = null;
        while (currentNode && currentNode.data != data ) {
            prevNode = currentNode;
            currentNode = currentNode.next;

        }
        if (!currentNode) { return }
        prevNode.next = currentNode.next;
        currentNode = null;
        this.size--;
    }// deleteData

    deleteFirst() {
        if (this.head) {
            this.head = this.head.next;
        }
        this.size--;
    }//deleteFirst

    deleteLast() {
        if (!this.head) { return }
        if (!this.head.next) { this.head = null; return }
        let seconedLast = this.head;
        while (seconedLast.next.next) {
            seconedLast = seconedLast.next;
        }
        seconedLast.next = null;
        this.size--;
    }//deleteLast

    display() {
        let currentNode = this.head;
        let viewDataStructure = '';
        while (currentNode) {
            viewDataStructure += `${currentNode.data}->`;
            currentNode = currentNode.next;
        }
        console.log(viewDataStructure + "end");
    }//display
}// LinkedList

const linkedSample = new LinkedList();

linkedSample.insertFirst(1);
linkedSample.insertFirst(2);
linkedSample.insertFirst(3);
linkedSample.insertBack(9);
linkedSample.display(); // 출력 : 3->2->1->9->end
linkedSample.deleteData(2);
linkedSample.display(); // 출력 : 3->1->9->end 
linkedSample.deleteFirst();
linkedSample.display(); // 출력 : 1->9->end
linkedSample.deleteLast();
linkedSample.display(); // 출력 : 1->end