스택이란?

한쪽 끝에서만 데이터를 삽입/삭제 할 수 있는 선형 자료구조

LIFO(Last In First Out)의 특징을 가졌다.





스택 오퍼레이션

isEmpty() : 스택이 현재 비어있는지 체크

push(data) : 스택에 데이터 삽입

pop() : 스택에서 데이터 삭제

peek() : 스택의 맨 위(다음에 꺼낼 데이터) 확인





스택 구조





스택 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.EmptyStackException;
 
public class Stack {
    
    private static class Node {
        private int data;
        private Node next;
        private Node(int data) {
            this.data = data;
        }
    }
    
    private Node top;
    
    public boolean isEmpty() {
        return top == null;
    }
    
    public int peek() {
        if(isEmpty()) throw new EmptyStackException();
 
        return top.data;
    }
    
    public void push(int data) {
        Node node = new Node(data);
        node.next = top;
        top = node;
    }
    
    public int pop() {
        if(isEmpty()) throw new EmptyStackException();
        
        int data = top.data;
        top = top.next;
        return data;
    }
}
cs





큐란?

한쪽에서는 데이터 삽입만, 반대쪽에서는 데이터삭제만 가능한 선형 자료구조

FIFO(First In First Out)의 특징을 가졌다.





큐 오퍼레이션

isEmpty() : 큐가 현재 비어있는지 체크

enqueue() : 큐에 데이터 삽입

dequeue() : 큐에서 데이터 삭제

peek() : 큐의 맨 앞(다음에 꺼낼 데이터) 확인





큐 구조









































큐 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.EmptyStackException;
 
public class Queue {
    
    private static class Node{
        private int data;
        private Node next;
        private Node(int data) {
            this.data = data;
        }
    }
    
    private Node front;
    private Node rear;
    
    public boolean isEmpty() {
        return front == null;
    }
    
    public int peek() {
        return front.data;
    }
    
    public void enqueue(int data) {
        Node node = new Node(data);
        if(rear != null) {
            rear.next = node;
        }
        rear = node;
        if(front == null) {
            front = node;
        }
    }
    
    public int dequeue() {
        if(isEmpty()) throw new EmptyStackException();
        
        int data = front.data;
        front = front.next;
        if(front == null) {
            rear = null;
        }
        return data;
    }
}
cs


저작자표시 비영리 변경금지

'자료구조' 카테고리의 다른 글

해시테이블이란? Hash Table 구현 Java  (0) 2019.10.27
링크드리스트(Linked List) 구현 Java  (0) 2019.10.26



해시테이블이란?

데이터의 키값을 해시함수를 이용해 인덱스화하고 배열의 해당인덱스에 데이터를 저장하는 자료구조







해시테이블 구조






해시함수는 해당 데이터를 배열의 몇번째 인덱스에 저장할 것인지 정해주는 함수이다. 이름과 연락처를 해시테이블에 저장하고 이름의 첫 번째 글자가 알파벳의 몇 번째 문자인지로 배열의 인덱스를 정하는 해시함수를 사용해보자. 예를 들어 Ann은 첫번째(index=0), Becca는 두번째(index=1)에 저장한다.




해시테이블 충돌해결 방식 (Collision Resolution)

서로 다른 데이터도 같은 인덱스값을 가질 수 있다. 예를 들어 위의 해시테이블에 Rachel의 전화번호를 삽입해보자. Rachel과 Racine 둘다 알파벳 첫글자가 r이기 때문에 인덱스 18을 가질 것이다. 이럴 경우에 충돌이 많이 발생하면 속도가 느려진다. 아무리 좋은 해시 함수라도 해시함수에 인덱스 충돌이 아예 안생기기란 거의 불가능하다(배열을 아주 크게 만들면 충돌이 거의 발생하지 않지만 당연히 메모리 낭비가 심하다 관심이 있다면 Birthday Paradox를 검색해봐라). 가장 많이 알려진 해결법 두가지를 알아 보자.




Linear Probing(선형 탐사)

데이터를 삽입할 때 해당 인덱스에 이미 데이터가 존재하면 그 다음 인덱스(+n)로 이동하는 방식이다. 위의 예시에 대입해 보자. Rachel은 원래 18번째 위치에 저장되어야 하는데 그자리에 이미 데이터가 있으므로 +1을 한다. 19번째에도 데이터가 있으므로 +1을 해주어 20번째에 저장한다. 이 상태에서 Tina의 연락처를 저장한다면 데이터는 21번째에 삽입될 것이다.






Chaining(체이닝)

체이닝은 중복된 인덱스값을 갖는 데이터들을 연결(chain)하는 것이다. 각 인덱스에 링크드리스트로 연결한다.




해시테이블 장단점


장점

데이터를 검색할 때 고유의 인덱스값으로 접근하기때문에 검색속도가 매우 빠르다.


단점

테이블내의 여유공간이 많아야 성능이 유지되기 때문에 저장공간을 상대적으로 많이 사용한다.





해시테이블 구현


아래 코드는 체이닝 해시테이블로 위의 예시를 구현한 것이다. 먼저 이름(key)과 연락처(value)를 가진 연락처(Contact) 클래스로 링크드리스트를 만든다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Contact {
    private String key;        //name
    private String value;     //phone number
    public Contact(String key, String value) {
        this.key = key;
        this.value = value;
    }
    public String getKey() {
        return key;
    }
    public void setKey(String key) {
        this.key = key;
    }
    public String getValue() {
        return value;
    }
    public void setValue(String value) {
        this.value = value;
    }
}
cs




이름의 첫 문자의 알파벳 순서대로 인덱스를 지정하고 같은 알파벳 때문에 충돌이 생기면 링크드리스트의 맨 뒤에 삽입한다. 연락처 검색시에는 키값을 이용해 해당인덱스의 링크드리스트를 순서대로 탐색한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.LinkedList;
 
public class ChainingHashTable {
    
    public LinkedList<Contact>[] data;
    
    public ChainingHashTable(int size) {
        data = new LinkedList[size];
    }
 
    int getHashCode(String key) {
        int hashCode = key.charAt(0)-'a';
        return hashCode;
    }
    
    int convertToIndex(int hashCode) {
        return hashCode % 26;
    }
    
    public void put(String key, String value) {
        
        int hashCode = getHashCode(key);
        int index = convertToIndex(hashCode);
        Contact contact = new Contact(key,value);
        if(data[index] == null) {
            data[index] = new LinkedList();
        }
        data[index].addLast(contact);
    }
    
    public String get(String key) {
        
        int hashCode = getHashCode(key);
        int index = convertToIndex(hashCode);
        LinkedList<Contact> contacts = data[index];
        for(Contact c : contacts) {
            if(c.getKey().equals(key)) {
                return c.getValue();
            }
        }
        return null;
    }
}
cs


저작자표시 비영리 변경금지

'자료구조' 카테고리의 다른 글

스택&큐 Stack and Queue 구현 java  (0) 2020.04.19
링크드리스트(Linked List) 구현 Java  (0) 2019.10.26



링크드리스트란?

데이터가 연속한 공간에 저장되는것이 아닌, 데이터와 다음 데이터로의 링크를 가진 노드들이 연결된 선형 데이터구조 





링크드리스트 구조




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LinkedList {
    
    Node head;
}
 
public class Node {
    
    Node next;
    String data;
    
    public Node(String data) {
        this.data = data;
    }
    
}
cs





링크드리스트 장단점


장점

배열처럼 처음부터 크기가 고정되는게 아니라 동적할당을 하기 때문에 선언시 크기를 지정하지 않아도 되어 메모리를 효율적으로 사용할 수 있다.

데이터의 추가/삭제가 용이하다.


단점

배열은 데이터를 찾을 때 인덱스로 접근하고 링크드리스트는 처음부터 순차적으로 접근한다. 그래서 k번째 데이터를 조작할 때 시간이 O(n)으로 오래 걸린다.



링크드리스트 구현


링크드리스트의 오퍼레이션들을 직접 구현해보자. 먼저 아래와 같은 링크드리스트 맨 앞에 데이터를 삽입하는것을 생각해보자.



순서는 다음과 같을 것이다.


1 노드 생성

2 1에서 만든 노드의 링크를 기존 링크드리스트의 head로 연결

3 링크드리스트의 head를 1에서 만든 노드로 변경


그림으로 보면 이해가 더 쉽다.


코드로 구현하면 다음과 같다.


1
2
3
4
5
6
7
8
9
public void addFirst(String data) {
    if(head == null) {
        head = new Node(data);
        return;
    }
    Node newHead = new Node(data);
    newHead.next = head;
    head = newHead;
}
cs



이번엔 링크드리스트의 마지막 값을 삭제해보자.


1 현재노드를 링크드리스트의 head로 지정

2 현재노드를 다음노드로 변경

3 다음노드를 가리키는 링크가 없을때까지 2를 반복

4 현재노드의 이전노드의 링크 삭제


previous : 이전노드 / current : 현재노드



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void removeLast() {
    if(head == null) {
        return;
    }
    if(head.next == null) {
        head = null;
        return;
    }
    Node current = head;
    Node previous = null;
    while(current.next != null) {
        previous = current;
    }
    current = current.next;
    previous.next = null;
}
cs




처음값 삭제, 특정 값 삭제 등도 구현해보자.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
public class LinkedList {
    
    Node head;
    
    public void addFirst(String data) {
        if(head == null) {
            head = new Node(data);
            return;
        }
        Node newHead = new Node(data);
        newHead.next = head;
        head = newHead;
    }
    
    public void addLast(String data) {
        if(head == null) {
            head = new Node(data);
            return;
        }
        Node current = head;
        while(current.next != null) {
            current = current.next;
        }
        current.next = new Node(data);
    }
    
    public void removeFirst() {
        if(head == null) {
            return;
        }
        head = head.next;
    }
    
    public void removeLast() {
        if(head == null) {
            return;
        }
        if(head.next == null) {
            head = null;
            return;
        }
        Node current = head;
        Node previous = null;
        while(current.next != null) {
            previous = current;
        }
        current = current.next;
        previous.next = null;
    }
    
    public void removeValue(String data) {
        if(head == null) {
            return;
        }
        if(head.data.equals(data)) {
            head = head.next;
            return;
        }
        Node current = head;
        while(current.next != null) {
            if(current.next.data.equals(data)) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }
}
cs


저작자표시 비영리 변경금지

'자료구조' 카테고리의 다른 글

스택&큐 Stack and Queue 구현 java  (0) 2020.04.19
해시테이블이란? Hash Table 구현 Java  (0) 2019.10.27

+ Recent posts

티스토리툴바