큐 ( Queue )

스택은 보통 큐와 비교해서 알아보는데 스택에 대해 알아봤고, 이번엔 큐에 대해 알아보자.

Queue 이란?

큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다.

영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.

나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.

구조

큐는 put(insert)와 get(delete)을 이용하여 구현된다.

put는 큐에 자료를 넣는 것을, get은 큐에서 자료를 꺼내는 것을 의미한다.

front(head)와 rear(tail)는 데이터의 위치를 가리킨다.

front는 데이터를 get할 수 있는 위치를, rear은 데이터를 put할 수 있는 위치를 의미한다.

또, 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우(put 할 수 없는 경우)를 오버플로우(Overflow), 큐가 비어 있어 자료를 꺼낼 수 없는 경우(get 할 수 없는 경우)를 언더플로우(Underflow)라고 한다.

종류

  • 선형
    막대 모양으로 된 큐, 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있다.

  • 환형
    선형 큐의 문제점(배열로 큐를 선언할시 큐의 삭제와 생성이 계속 일어났을때, 마지막 배열에 도달후 실제로는 데이터공간이 남아있지만 오버플로가 발생)을 보완한 것이 환형 큐이다. front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결 하는 방식이다.

언제 사용하는가?

  1. 우선순위가 같은 작업 예약 ( ex 인쇄 대기열 )
  2. 선입선출이 필요한 대기열 ( ex 티켓 카운터 )
  3. 멀티 프로그래밍
  4. 비동기 데이터 교환 ( 파일I/O, pipes, sockets )
  5. 콜센터 고객 대기시간, 마트 계산대 수 결정 등
  6. 다른 알고리즘의 보조 자료구조 ( 트리 Level Order Traversal)

구현

먼저 기본적인 큐를 구성해보자.

const Queue = (() => {
    class Queue {
        constructor() {
            this.count = 0;
            this.head = null;
            this.rear = null;
        }
    }
    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    }
    return Queue;
})()

Queue 클래스에서 count는 큐의 길이, head와 rear는 처음과 끝 자료를 의미하고,

각 자료는 Node 클래스의 인스턴스로 구성된다.

큐의 뒤에서 자료를 넣는 put을 구현해보자.

put(value) {
    const node = new Node(value);
    if ( !this.head ) {
        this.head = node;
    } else {
        this.rear.next = node;
    }
    this.rear = node;
    return ++this.count;
}

만약 헤드가 비어있다면 헤드에 추가, 아니라면 rear의 next와 rear에 순서대로 추가해주고, 크기를 리턴

큐의 앞에서 자료를 꺼내는 get을 구현해 보자.

get() {
    if ( !this.head ) {
        return false;
    }
    const data = this.head.data;
    this.head = this.head.next;
    this.count--;
    return data;
}

헤드가 없다면 false를 리턴해 get이 일어나지 않도록 하고, 이외의 경우라면 data에 추출할 데이터를 담고, 헤드를 뒤로 한칸밀고 추출한 데이터를 리턴.

head를 리턴하는 front 메소드, rear를 리턴하는 back 메소드를 추가하면 다음과 같다.

front() {
    return this.head && this.head.data;
}

back() {
    return this.rear && this.rear.data;
}

스택과 비슷하지만 자료의 삽입, 제거 방식이 조금 다르므로 차이를 알고 필요한 부분에 쓸 수 있으면 유용할 것 같다.

전체 코드

const Queue = (() => {
    class Queue {
        constructor() {
            this.count = 0;
            this.head = null;
            this.rear = null;
        }

        put(value) {
            const node = new Node(value);
            if ( !this.head ) {
                this.head = node;
            } else {
                this.rear.next = node;
            }
            this.rear = node;
            return ++this.count;
        }

        get() {
            if ( !this.head ) {
                return false;
            }
            const data = this.head.data;
            this.head = this.head.next;
            this.count--;
            return data;
        }

        front() {
            return this.head && this.head.data;
        }

        back() {
            return this.rear && this.rear.data;
        }
    }
    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    }
    return Queue;
})()


'자료구조, 알고리즘 > JS 자료구조' 카테고리의 다른 글

3. 큐 ( Queue )  (0) 2017.11.17
2. 스택 ( Stack )  (0) 2017.11.15
1. 연결 리스트 ( Linked List )  (0) 2017.11.10
0. 자료구조  (0) 2017.10.31

스택 ( Stack )

스택은 보통 큐와 비교해서 알아보는데 우선 스택에 대해 알아보자.

stack 이란?

스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다.

쉽게 한쪽이 막힌 통이라고 생각하면 된다.

그림과 같이 가장 나중에 넣은것이 가장 먼저 나오게된다.

개발자라면 한번쯤 들어가봤을 사이트 stack overflow에서 그 스택이 이 스택이 맞다.

의미는 스택이 꽉차있는데 push로 삽입하려 하는 것을 stack overflow,

스택이 비어있는데 pop으로 제거하려 하는 것을 stack underflow 라 부르며,

스택을 만들 때는 위의 두가지를 예외처리 해줘야 한다.

구조

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다.

자료를 넣는 것을 ‘밀어넣는다’ 하여 푸시(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 보관한 자료부터 나오게 된다.

이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.

위에 설명에서 보다시피 자바스크립트에서는 이미 배열 메소드에 push, pop메소드가 있어 스택처럼 사용할 수 있지만, 직접 구현해 보면서 이해를 도와보자.

언제 사용하는가?

  1. 브라우저 방문 기록(뒤로가기)
  2. 실행 취소(undo)
  3. 역순 문자열 만들기
  4. 수식의 괄호 검사
  5. 후위표기법 계산

위와 같은 경우가 있고, 추가로 다른분이 쓴 글을 덧붙여야겠다.
큐와 스택의 실제 사용 에

구현

스택을 링크드 리스트리스트로 구현해보자. (참고 : zeroCho님 블로그)

우선 스택을 정의해주면 다음과 같다.

const Stack = (() => {
    class Stack {
        constructor() {
            this.top = null;
            this.count = 0;
        }
    }
    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    }
    return Stack;
})()

Stack클래스에 top은 가장 위의 데이터, count는 데이터의 개수이다.

이제 원소를 삽입하는 push, 제거하는 pop을 구현해 보자.

push(value) {
    const node = new Node(value);
    node.next = this.top;
    this.top = node;
    return ++this.count;
}

푸시로 새로운 값을 넣어주면 현재 top을 다음으로 밀고, top에 새로운 값을 넣어준다.

리턴 값은 현재 스택의 크기를 반환해주는데, 콘솔창에서 자바스크립트로 push를 해보면 스택 크기가 리턴되는 것을 알 수 있다.

마찬가지로 pop을 구현해 보자.

pop() {
    if ( !this.top ) {
        return false;
    }
    const data = this.top.data;
    this.top = this.top.next;
    this.count--;
    return data;
}

if문은 top이 없을 때, 즉 스택이 비었을 때 pop을 못하도록 하는 것, 즉 stack underflow방지를 위해 넣은 코드,

pop을 실행시 현재 탑의 데이터를 data에 담고, top을 현재 탑의 next로 바꿔주고 크기를 1줄인 뒤에 data를 리턴해준다.

아래는 현재 top을 리턴해주는 메소드이다.

top() {
    return this.top.data;
}

별거 없음.

전체 코드

const Stack = (() => {
    class Stack {
        constructor() {
            this.top = null;
            this.count = 0;
        }

        push(value) {
            const node = new Node(value);
            node.next = this.top;
            this.top = node;
            return ++this.count;
        }

        pop() {
            if ( !this.top ) {
                return false;
            }
            const data = this.top.data;
            this.top = this.top.next;
            this.count--;
            return data;
        }

        top() {
            return this.top.data;
        }
    }
    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    }
    return Stack;
})()

스택 크기 정해서 stack overflow 방지하는 코드도 만들어보고 싶은데,

크기 설정에 대한 개념이 안잡혀 있어서 할 수가 없다. sombody help me..


'자료구조, 알고리즘 > JS 자료구조' 카테고리의 다른 글

3. 큐 ( Queue )  (0) 2017.11.17
2. 스택 ( Stack )  (0) 2017.11.15
1. 연결 리스트 ( Linked List )  (0) 2017.11.10
0. 자료구조  (0) 2017.10.31

Linked List ( 연결 리스트 )

자바스크립트를 공부하면서 딱히 쓸모도 없다라고 생각했어서 피하고 싶은 자료 구조 내용인데, 알고리즘 문제를 풀면서 여러가지를 익혀놔야겠다는 생각이 들고는 더이상 미룰 수 없을 것 같아서, 공부하고 포스팅 해보려 함!

잘 모르기 때문에 틀린 부분이나 설명이 부족한 부분은 지적 부탁드리겠습니다.

참고 : zerocho님 블로그, 위키백과

linked list란?

연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.

구조

노드(Node)와 링크(Link)로 구성되며,

노드는 실제 정보를 담고 있는 하나의 단위이고,

링크는 노드간의 위치정보를 저장하고 있어 연결리스트의 순서를 유지할 수 있도록 하는 연결고리라 할 수 있다.

노드의 시작점은 head, 끝점은 tail이라 부르며 노드의 추가, 삭제, 탐색이 가능하다.

종류

단일 연결 리스트 ( Singly Linked List )

단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

이중 연결 리스트 ( Doubly Linked List )

이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

원형(환형) 연결 리스트 ( Circular Linked List )

원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

이중 원형(환형) 연결 리스트 ( Doubly Circular Linked List )

이중 원형 연결 리스트는 이중 연결 리스트의 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

배열과의 비교

배열은 각 값마다 고유한 인덱스를 가지고 있다.

이는 탐색에는 매우 유리하지만 삽입이나 삭제를 하는 부분에서 단점이 있다.

예를 들어 [1,2,3,5,6] 라는 배열에서 3과 5사이에 4를 삽입하고 싶다면

5,6의 인덱스를 뒤로 한칸씩 밀고 4를 빈 자리에 넣어줘야 한다.

위와 같은 과정은 배열의 복사, 이동을 통해 생기며, 삽입, 삭제의 규모가 커진다면 이는 많은 소요를 필요로 한다.

링크드 리스트는 이러한 단점을 해결하기 위해 나왔다.

링크드 리스트에서의 삽입은 삽입할 노드를 삽입할 위치의 이전노드, 다음노드와 연결만 해주면 되고,

삭제도 마찬가지로 삭제하고 싶은 노드에 연결되어있는 앞 뒤의 노드를 서로 이어주면 된다.

하지만 링크드 리스트는 탐색을 위해서는 항상 첫번째 노드부터 비교해야한다 하는 단점이 있다.

위에서 설명한 내용과 같이, 배열과 링크드 리스트는 장단점이 반대이므로

데이터 탐색이 많이 필요한 상황에서는 배열을 사용하고

데이터 삽입, 삭제가 많이 필요한 상황에서는 링크드 리스트를 사용하는 것이 효율적이다.

추가로 기본적인 두가지의 장점을 합쳐놓은 Chunked List, 이를 발전시킨 B+ 트리라는 자료 구조가 있다고 하는데, 아직은 이해할 만큼 내공이 쌓이지 않았기 때문에 우선은 패스~

생활코딩에 그림과 예제로 쉽게 차이를 알려주고 있음.

구현

ES6 문법을 기반으로 코드를 작성.

ES6 clsss를 잘 모른다면 참고하시면 좋을 것 같습니다.

우선 기본적인 단일 연결 리스트를 구현!

const LinkedList = (() => {
    class LinkedList {
        constructor() {
            this.length = 0;
            this.head = null;
        }
      }
    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    }
    return LinkedList;
})();

연결 리스트와, 노드 클래스를 생성해주었고,

데이터 추가, 삭제, 탐색을 아래에 구현해 보면 다음과 같다.

  1. 추가 ( add )
    add(value) {
        const node = new Node(value);
        let current = this.head;
        if (!current) {
            this.head = node;
            this.length++;
            return node;
        } else {
            while(current.next) {
            current = current.next;
        }
        current.next = node;
        this.length++;
        return node;
    }

위의 추가 메소드는 position을 인자로 받지 않고, 리스트의 맨 뒤에 추가만 가능한 메소드이다.

add 메소드에 value값을 넣어주면 새로운 Node 인스턴스를 생성 해주고

if문에서 현재 head가 비어있다면, 즉 리스트가 비어있다면 node를 head에 넣어주고

아니라면 next가 null일 때 까지 이동 후에 현재노드의 next에 추가해주고 length를 1 더해준다.

추가가 완료되면 추가한 노드를 리턴해준다.

    2.삭제 ( remove )

    remove(position) {
        let current = this.head;
        let before;
        let remove;
        let count = 0;
        if (position == 0) {
            remove = this.head;
            this.head = this.head.next;
            this.length--;
            return remove;
        } else {
            while (count < position) {
                before = current;
                remove = current.next;
                count++;
                current = current.next;
            }
            before.next = remove.next;
            this.length--;
            return remove;
        }
    }

remove 메소드에 position을 넣어 position에 있는 노드를 삭제해준다.

이때, position을 배열의 index라 생각하면 이해가 쉬움

하지만 배열과 다르게 삭제하려는 위치(position)까지 가려면 head부터 순차적으로 탐색해서 가야함.

if문에서 0번 노드, 즉 head를 삭제한다면

기존 head의 다음 노드를 head로 이동, length를 1 줄이고 삭제한 노드를 리턴해준다.

이외의 경우에서는

while문으로 next로 한칸씩 이동해서 position까지 찾아간 뒤에

해당 position의 노드를 삭제해주고, 삭제된 노드의 이전 노드와 다음 노드를 연결, length를 1 줄이고 삭제한 노드를 리턴해준다.

    3. 탐색 ( search )

// 탐색 메소드
    search(position) {
        let current = this.head;
        let count = 0;
        while (count < position) { // position 위치만큼 이동합니다.
            current = current.next;
            count++;
        }
        return current.data;
    }

position위치의 노드를 찾기 위해 사용하는 메소드.

위의 remove와 비슷하게 작동하며, position까지 이동을 완료하면 해당 노드의 데이터를 리턴해준다.

전체 코드

const LinkedList = (() => {

    // LinkedList 클래스
    class LinkedList {
        constructor() {
            this.length = 0;
            this.head = null;
        }

        // 추가 메소드
        add(value) {
            const node = new Node(value);
            let current = this.head;
            if (!current) {
                this.head = node;
                this.length++;
                return node;
        } else {
          while(current.next) {
        current = current.next;
      }
      current.next = node;
      this.length++;
      return node;
    }

        // 삭제 메소드
        remove(position) {
        let current = this.head;
        let before;
            let remove;
          let count = 0;
        if (position == 0) {
          remove= this.head;
          this.head = this.head.next;
          this.length--;
          return remove;
            } else {
                while (count < position) {
                    before = current;
                    remove = current.next;
                    count++;
                    current = current.next;
                }
                before.next = remove.next;
                this.length--;
                return remove;
            }
        }

        // 탐색 메소드
        search(position) {
        let current = this.head;
        let count = 0;
        while (count < position) {
          current = current.next;
          count++;
        }
        return current.data;
      }
    }

    // Node 클래스
    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    }

    return LinkedList;
})();

막상 작동 원리를 보고 코드를 구현(사실 거의 베꼈다..백지에서 작성은 해봤음)해보니 생각한것 만큼은 어렵지 않았다.

물론 단일이라 그런걸수도..ㅎㅎ

나중에 다른 연결리스트도 구현해보는 연습을 해봐야겠다.

내용이 길어 틀린 부분이 있을 수 있습니다.


'자료구조, 알고리즘 > JS 자료구조' 카테고리의 다른 글

3. 큐 ( Queue )  (0) 2017.11.17
2. 스택 ( Stack )  (0) 2017.11.15
1. 연결 리스트 ( Linked List )  (0) 2017.11.10
0. 자료구조  (0) 2017.10.31

자료구조

독학하면서 자료구조, 알고리즘 같은 이론의 중요성을 간과하고 넘어가니 본질적인 이해가 어려워 부족한 부분을 채우기 위해 블로그와 사이트를 뒤져가며 하나씩 열심히 해볼 예정!

자료구조란?

자료구조(資料構造, 영어: data structure)는 전산학에서 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택문제는 대개 추상적 자료구조의 선택으로부터 시작하는 경우가 많다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다. - 위키백과 -

자료구조가 필요한 이유

효율적으로 설계하기 위함.

여기서 효율적인 설계란 퍼포먼스의 향상과 동시에 메모리를 절약하는 방법이고, 이를 위해 자료구조의 선택이 중요한 것 같다.

종류

보통 형태에 따라서 자료구조를 나누는데 크게 두가지로 나뉜다.

  1. 선형구조

    • 선형 리스트
      • 배열
      • 레코드
    • 연결 리스트
    • 스택
  2. 비선형 구조

    • 그래프
    • 트리
      • 일반 트리
      • 이진 트리

크게 위와같이 나눠진다고 보이며,

아직은 자세히 알지 못하기 때문에 빼먹거나 틀린 부분은 하나하나 알아야겠다.

'자료구조, 알고리즘 > JS 자료구조' 카테고리의 다른 글

3. 큐 ( Queue )  (0) 2017.11.17
2. 스택 ( Stack )  (0) 2017.11.15
1. 연결 리스트 ( Linked List )  (0) 2017.11.10
0. 자료구조  (0) 2017.10.31

Quick-sort with Hungarian (Küküllőmenti legényes) folk dance - YouTube

퀵소트를 춤으로 이해시켜주는데 황당하지만 엄청난 설명


다른 정렬들도 관련 동영상에 나와있음!

'좋은글 > 개발' 카테고리의 다른 글

개발 좋은 글 모음  (3) 2017.07.02
자료구조 소트 쉽게 이해하기  (0) 2017.04.07
블로그 운영시 참고 사이트, 프로그램  (0) 2017.04.03
스타트업 관련 정보 사이트  (2) 2017.03.29

+ Recent posts