검색결과 리스트
program/data_structure에 해당되는 글 4건
글
[data structure] 자료구조 트리(Tree), 이진트리(Binary Tree) 알고리즘 이란?? (java로 구현)
Q. 이진트리(Binary Tree) 에 대해 알아보자.
1. 트리(Tree) ??
2. 이진트리(Binary Tree) ??
3. 이진트리 탐색방식(in-order, post-order, pre-order, level-order)
4. 이진트리와 함께하는 대표적인 기능들(add, delete)
5. 이진트리의 탐색 기능(in-order, post-order, pre-order, level-order)
6. 이진트리의 부가적인 기능들(getLevel, getMax)
1. 트리(Tree) ?? |
트리란, 1개 이상의 노드로 이루어진 유한 집합이다.
말로 설명하면 어려우니 아래 그림을 보겠습니다.
각 동그라미를 노드(node)라고 합니다.
A노드, B노드.... H노드까지 8개의 노드가 있습니다.
각 노드들은 부모노드(parent node)와, 자식노드(child node)를 가지고 있습니다.
B노드를 기준으로 설명하자면,
B노드의 부모노드는 A노드이고,
B노드의 자식노드는 E노드, F노드 입니다.
A노드는 가장 위에 있고 부모노드가 없는 유일한 노드이기 때문에,
루트(root) 라는 이름을 가지고 있습니다.
A노드의 자식의 개수는 3개 입니다.
이를 또다른 말로 차수(degree) 라고 하는데,
A노드의 차수는 3 이라고 합니다.
(D노드의 차수는 2)
차수가 0인 가장 마지막에 있는 노드를 리프(leaf) 또는 단말노드(terminal node)라고 합니다.
트리의 깊이(height) 를 나타내는 말로는 레벨(level) 이 있습니다.
루트인 A노드를 1로 하고 가장 아래 자식 노드가 있을때까지는 세어보면,
레벨이 나옵니다. 위, 트리는 레벨이 3 이라고 합니다.
2. 이진트리(Binary Tree) ?? |
위에서 한참 트리에 대해 설명을 해드렸는데요,
트리와 이진트리는 다르지 않습니다.
대신 가장 중요한 차이점은,
트리는 1개 이상의 노드를 가질수 있지만,
이진 트리는 1개 이상 2개 이하의 노드만 가질수 있습니다.
아래 그림은 각 노드가 자식노드를 2개이하로 갖고 있는 이진 트리의 모습입니다.
이진트리를 조금 다르게 표현하면,
이진트리는 차수(degree)를 2 이하로만 갖을수 있다.
이진트리의 최대 노드수는 아래와 같이 구할수 있습니다.
레벨(i)을 알고 있을 때 |
레벨이 3인 트리는 2의 3제곱승 - 1 = 7 이 나오게 됩니다.
포화이진트리(perfect binary tree)는,
모든 리프(단말)노드가 같은 레벨에 있을때를 말합니다.
아래 그림이 바로 포화이진트리 입니다.
완전이진트리(complete binary tree)는,
포화이진트리에서 끝부분을 제외하고 다른것이 남아 있는 트리입니다.
그러니까 왼쪽에서 오른쪽으로 번호를 매겼을때,
그 번호가 연속성이 있는 경우 완전이진트리가 됩니다.
3. 이진트리 탐색방식(in-order, post-order, pre-order, level-order) |
이진트리를 순회(탐색)하는 방식에는 크게 4가지가 있습니다.
- in-order 방식
- post-order 방식
- pre-order 방식
- level-order 방식
이렇게 4가지가 있습니다.
자신 노드를 V라 하고, 왼쪽 자식 노드를 L,
오른쪽 자식노드를 R 이라고 가정하고 설명하겠습니다.
1) in-order 방식(LVR)
in-order 방식은 왼쪽, 자신, 오른쪽 노드를 순차적으로 방문하는 탐색 방식입니다.
위 트리를 in-order 방식으로 탐색한다면,
123456789 순서대로 방문합니다.
2) post-order 방식(LRV)
post-order 방식은 왼쪽, 오른쪽, 마지막으로 자기 자신 노드를 탐색합니다.
위 트리를 post-order 방식으로 탐색한다면,
1 2 4 3 6 9 8 7 5 순서대로 방문합니다.
3) pre-order 방식(VLR)
pre-order 방식은 자신, 왼쪽, 오른쪽 노드를 차례대로 탐색합니다.
위 트리를 pre-order 로 방문한다면,
5 3 2 1 4 7 6 8 9 순서대로 방문합니다.
4) level-order 방식
level-order 방식은 다른 방식과 달리
루트 레벨부터 왼쪽부터 차례대로 탐색하는 방식입니다.
위 트리를 level-order 방식으로 탐색하면,
5 37 2468 19 순서대로 방문을 합니다.
4. 이진트리와 함께하는 대표적인 기능들(add, delete) |
이제 실제로 구현해보겠습니다.
우선 대표적인 기능에는
트리에 노드를 추가하는 add
트리의 노드를 삭제하는 delete
이 두 기능이 있습니다.
※ 트리는 이진트리로 구성되고, data는 int 형이다.
※ 중복값은 add 하지 않는다.
※ 새 값이 자기 자신의 값보다 작으면 왼쪽 자식노드 보낸다.
※ 새 값이 자기 자신보다 크면 오른쪽 자식노드로 보낸다.
※ delete 시 해당노드의 자식노드가 있더라도 같이 삭제 된다.
먼저 add 는 다음과 같이 구성됩니다.
public void add( int data ) { if( root == null ) { TreeNode newNode = new TreeNode( data ); root = newNode; return; }
TreeNode node = root; for( ;; ) { if( node.data == data ) break; else if( node.data < data ) // ① { if( node.right == null ) { TreeNode newNode = new TreeNode( data ); node.right = newNode; break; } else node = node.right; } else if( node.data > data ) // ② { if( node.left == null ) { TreeNode newNode = new TreeNode( data ); node.left = newNode; break; } else node = node.left; } } } |
① : 새로 들어온 data가 기존의 값보다 크기 때문에 오른쪽 자식 노드 쪽에 넣는다.
② : 새로 들어온 data가 기존의 값보다 작기 때문에 왼쪽 자식 노드 쪽에 넣는다.
두번째로 delete 는 이렇게 구성됩니다.
public void delete( int data ) { if( root == null ) { // System.out.println( "isEmpty" ); return; }
if( root.data == data ) { root = null; return; }
TreeNode node = root; for( ;; ) { if( node.right == null && node.left == null ) { // System.out.println( "Not Found value" ); return; }
if( node.data < data ) // ① { if( node.right.data == data ) { node.right = null; break; } else node = node.right; } else if( node.data > data ) // ② { if( node.left.data == data ) { node.left = null; break; } else node = node.left; } } } |
① : 새로 들어온 data가 기존의 값보다 크기 때문에 오른쪽 자식 노드의 값을 비교한다.
② : 새로 들어온 data가 기존의 값보다 작기 때문에 왼쪽 자식 노드의 값을 비교한다.
5. 이진트리의 탐색 기능(in-order, post-order, pre-order, level-order) |
1) in-order 방식(LVR)
public void inOrderPrint() { System.out.println( "## in-order(LVR) ##" ); inOrder( root ); System.out.println(); System.out.println(); }
private void inOrder( TreeNode node ) { if( node != null ) { inOrder( node.left ); // ① System.out.print( node.data ); inOrder( node.right ); // ② } } |
① : 자기 자신을 node.left 바꿔 재귀(recursion)호출을 한다.
② : 자기 자신을 node.right 바꿔 재귀(recursion)호출을 한다.
2) post-order(LRV)
public void postOrderPrint() { System.out.println( "## post-order(LRV) ##" ); postOrder( root ); System.out.println(); System.out.println(); }
private void postOrder( TreeNode node ) { if( node != null ) { postOrder( node.left ); // ① postOrder( node.right ); // ② System.out.print( node.data ); } } |
① : 자기 자신을 node.left 바꿔 재귀(recursion)호출을 한다.
② : 자기 자신을 node.right 바꿔 재귀(recursion)호출을 한다.
3) pre-order(VLR)
public void preOrderPrint() { System.out.println( "## pre-order(VLR) ##" ); preOrder( root ); System.out.println(); System.out.println(); }
private void preOrder( TreeNode node ) { if( node != null ) { System.out.print( node.data ); preOrder( node.left ); // ① preOrder( node.right ); // ② } } |
① : 자기 자신을 node.left 바꿔 재귀(recursion)호출을 한다.
② : 자기 자신을 node.right 바꿔 재귀(recursion)호출을 한다.
4) level-order
public void levelOrderPrint() { System.out.println( "## level-order ##" ); levelOrder( root ); System.out.println(); System.out.println(); }
private void levelOrder( TreeNode node ) { ArrayList<TreeNode> queue = new ArrayList<TreeNode>( getMax() );
if( node == null ) { System.out.println( "Tree is Empty" ); return; } queue.add( node );
int pos = 0; int size = 0; for( ;; ) { size = queue.size(); if( pos == size ) return; else node = queue.get( pos++ ); // ①
if( node != null ) { System.out.print( node.data );
if( node.left != null ) queue.add( node.left ); // ②
if( node.right != null ) queue.add( node.right ); // ③ } else break; } } |
level-order 방식은 노드를 만날때마다 큐(queue)에 넣어
차례대로 빼어사용하는 방식입니다.
① : 큐에 가장 처음 넣은 값을 뺍니다.
② : 왼쪽 노드를 차례대로 큐에 넣습니다.
③ : 오른쪽 노드를 차례대로 큐에 넣습니다.
6. 이진트리의 부가적인 기능들(getLevel, getMax) |
현재 트리의 레벨 과 최대 노드 개수를 가져오는 메소드도 작성해보았습니다.
먼저 getLevel 입니다.
private int level = 0;
public int getLevel() { level = 0; getLevel( root ); return level; }
private void getLevel( TreeNode node ) { int _level = level;
if( node == null ) level = 0; else { _level++; getLevel( node.left ); // ① getLevel( node.right ); // ②
if( level < _level ) // ③ level = _level; } } |
① : node.left 를 파라미터로 넘겨 재귀(recursion)호출을 합니다.
② : node.right 를 파라미터로 넘겨 재귀(recursion)호출을 합니다.
③ : 현재 탐색한 레벨이 기존 갖고 있는 레벨보다 크다면 레벨값을 교체합니다.
두번째로 getMax 입니다.
public int getMax() { int level = getLevel(); // ①
if( level <= 0 ) return 0; else return (int)Math.pow( 2, level ) - 1; // ② } |
① : 우선 getLevel 을 통해서 현재 트리의 레벨을 가져옵니다.
② : 최대 노드를 구하는 수식을 이용하여 최대 노드개수를 구합니다.
※ 결론
이번 트리를 구현하면서 느낀것은 생각보다 어렵습니다.
현재 단계에서는 간단히 구현했지만,
delete 시 삭제될 값을 대체하는 노드가 그 자리를 메꾸면서
정렬을 해야하는 등 많은 고려사항이 있습니다.
이것이라도 충분히 이해하고 지나가야겠습니다.
'program > data_structure' 카테고리의 다른 글
| [data structure] 자료구조 링크리스트, 연결리스트(Linked List) 알고리즘 이란?? (java 로 구현) (0) | 2012.10.26 |
|---|---|
| [data structure] 자료구조 큐(queue) 알고리즘 이란 ?? (java 로 구현) (0) | 2012.10.26 |
| [data structure] 자료구조 스택(stack) 알고리즘 이란 ?? (java 로 구현) (0) | 2012.10.26 |
설정
트랙백
댓글
글
[data structure] 자료구조 링크리스트, 연결리스트(Linked List) 알고리즘 이란?? (java 로 구현)
Q. 연결리스트 (Linked List) 에 대해 알아보자.
1. 연결리스트(Linked List) ??
2. 연결리스트와 함께 하는 대표적인 기능들(add, delete, insert, search, clear, print)
1. 연결리스트(Linked List) ?? |
연결리스트란 배열과 같은 순차(Sequential) 표현에서 제기된,
문제점인 데이터 이동을 보완 위한 방법입니다.
그럼 이전에 문제였던 순차리스트 표현에서 제기된 문제점을 알아보겠습니다.
아래와 같이 꽉찬 배열이 있다고 가정했을때,
[2], [3], [5] 번의 데이터가 삭제 됐을때,
그 뒤에 있는 데이터를 앞으로 가져와야 하는 배열간의 복사가 일어나게 됩니다.
위와 같은 그림처럼 값 50, 70, 80이 삭제된 빈 배열때문에 앞으로 이동되게 됩니다.
(일반적으로 데이터 저장시 빈공간은 두지 않기 때문)
이전 배열은 추가(add) 하는데에는 아무런 문제가 없지만,
삽입(insert), 삭제(delete) 하는데는 배열 복사, 이동 등 많은 소요가 필요했었습니다.
바로 이를 잘 해결하도록 나온것이 연결 리스트(Linked List) 입니다.
연결 리스트는 아래와 같은 모습을 가지게 됩니다.
사각형을 노드(Node)라고 부르는데,
노드는 data 부분과 address(link) 부분으로 불립니다.
data 부분은 값을, address 부분은 다음 데이터의 위치를 기억하고 있습니다.
노드들을 여러개 붙여 놓으면 아래와 같은 모습을 가지게 됩니다.
[그림] 연결리스트(Linked List) : 위키백과
http://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8
각 노드들이 자기 다음 데이터의 위치를 기억하고 있기 때문에,
화살표로 연결되어 있는 모습을 볼수 있습니다.
private static class Node { private Object data; Node next; } |
자기 다음 데이터의 위치를 기억하고 있기 때문에,
삽입(insert)과 삭제(delete)가 용이해집니다.
삽입 삭제가 용이해지는 이유는,
위 그림과 같이 가운데 노드가 없어진다면,
①노드에서 ②노드를 향하고 있는 주소값을 지우고,
①노드에서 ③노드를 향하게하면 됩니다.
이렇게 구현하면 삽입이나, 삭제시 발생하는 배열 복사를 줄일수 있습니다.
각 노드는 자기 다음 데이터의 위치를 기억하고 있지만,
어디가 시작이 되는지는 알수가 없습니다.
그렇게 때문에 first 라는 시작점을 가르키는 객체가 필요 합니다.
끝이란 표현은 address 부분에 null 을 사용하여,
이 데이터가 끝이란 것을 알립니다.
데이터의 추가, 삽입과 삭제는 용이 하지만,
연결리스트는 시작점 밖에 알고 있는것이 없기 때문에,
데이터를 찾기 위해선 처음부터 끝까지 비교해야한다는 단점이 있습니다.
2. 연결리스트와 함께 하는 대표적인 기능들(add, delete, insert, search, clear) |
연결리스트(Linked List) 에는,
연결리스트 마지막에 데이터를 추가하는 add
연결리스트 중간에 데이터를 삽입하는 insert
연결리스트의 값을 삭제하는 delete
연결리스트의 값을 찾는 search
연결리스트를 초기화 시키는 clear
이렇게 대표적인 기능(메소드)이 필요 합니다.
가장 먼저 add 는 아래와 같이 구성됩니다.
private Node first; public void add( Object data ) { Node node = first; // ① if( node == null ) // ② { node = new Node(); node.data = data; first = node; } else { for( ;; ) { if( node.next == null ) // ③ { Node newNode = new Node(); newNode.data = data; node.next = newNode; break; } node = node.next; } } } |
① : 첫번째 노드를 node 에 넣습니다.
② : 첫번째 노드가 있는지 확인하고 없다면(null), 새 노드를 생성합니다.
③ : ②번의 그 외의 경우에는,
루프를 돌아 가장 마지막 노드를 찾습니다. (노드의 다음 값(node.next)이 null)을 찾습니다.
※ node.next 가 null 이면 가장 마지막 노드란 뜻입니다.
두번째로 delete 는 아래와 같이 구성됩니다.
public void delete( Object data ) { Node node = first; if( node.data.equals( data ) ) // ① first = node.next; else { for( ;; ) { Node nextNode = node.next; if( nextNode.data.equals( data ) ) // ② { node.next = nextNode.next; break; } else { if( nextNode.next == null ) // ③ return; node = nextNode; } } } } |
① : 최초 노드 값을 삭제해야 한다면, 첫번째 노드를 바꿔치기 합니다.
② : ①번이 아니라면, 루프를 돌아 해당 값을 찾습니다.
node(기준 값), nextNode(다음 값)이 있는데,
다음 값을 찾아서 값과 같다면 기준 값에 주소부분에 nextNode.next 값을 넣어줍니다.
③ : 끝까지 루프를 돌아도 찾지 못하였을 경우 메소드를 종료합니다.
세번째로 insert 는 다음과 같습니다.
public void insert( Object baseData, Object insertData ) { Node node = first; if( ( node.data ).equals( baseData ) ) // ① { Node newNode = new Node(); newNode.data = insertData; newNode.next = first; first = newNode; } else { for( ;; ) { Node nextNode = node.next; if( nextNode.data.equals( baseData ) ) // ② { Node newNode = new Node(); newNode.data = insertData; newNode.next = nextNode; node.next = newNode; break; } else node = nextNode; } } } |
insert 는 기준값 앞에 값을 넣는 메소드 입니다.
① : 첫번째 노드의 값이 기준값과 같다면 새 노드를 추가하여 first 노드로 바꿔치기 해줍니다.
② : ①번의 경우가 아니라면, 루프를 돌아 기준값을 찾고 새 노드를 기준값 앞에 추가해줍니다.
네번째로 search 는 다음과 같습니다.
public void search( Object data ) { Node node = first; int cnt = 1; for( ;; ) { if( node.data.equals( data ) ) // ① { System.out.println( "'" + data + "' is " + cnt + " node" ); break; } if( node.next == null ) // ② return; else node = node.next; cnt++; } } |
① : 처음부터 루프를 돌아 해당값을 찾고 그에 맞는 index 를 출력합니다.
② : 맨끝까지 돌아도 없을 경우에는, 메소드를 종료 시킵니다.
마지막으로 clear 입니다.
public void clear() { System.out.print( "\n\n - clear -" ); first = new Node(); } |
시작점인 first 노드를 새로 생성하여 초기화 합니다.
C 책을 보고 작성하려 했을 때, 기본 개념과 뭔가 많이 헷갈렸습니다.
자바는 OOP(Object-Oriented Programming) 는 연결리스트를 보다 쉽게 구성할수 있었습니다.
많이 천천히 생각해보고, 자바와 더 친해져봐야겠습니다.
참조 : 위키백과
http://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8
참조 : C로 쓴 자료 구조론 2nd Edition 155 155 page ~ 171 page
'program > data_structure' 카테고리의 다른 글
| [data structure] 자료구조 트리(Tree), 이진트리(Binary Tree) 알고리즘 이란?? (java로 구현) (0) | 2012.10.26 |
|---|---|
| [data structure] 자료구조 큐(queue) 알고리즘 이란 ?? (java 로 구현) (0) | 2012.10.26 |
| [data structure] 자료구조 스택(stack) 알고리즘 이란 ?? (java 로 구현) (0) | 2012.10.26 |
설정
트랙백
댓글
글
[data structure] 자료구조 큐(queue) 알고리즘 이란 ?? (java 로 구현)
Q. 큐에 대해 알아보자.
1. 큐(Queue) ??
2. 큐와 함께 하는 대표적인 기능들(enQueue, deQueue) 과 front, rear, Overflow, Underflow
3. 심화 : 동적 배열을 사용하는 큐
1. 큐(Queue) ?? |
스택과 더불어 가장 많이 나오는 것이 바로 큐 입니다.
큐는 일반적으로 아래와 같은 모습을 지니고 있습니다.
[그림] 큐
큐는 가장 첫 원소를 front 라 하고,
가장 끝 원소를 rear 라 합니다.
큐는 들어올때 가장 끝자리 rear 로 들어오지만,
뺄때는 가장 처음인 front 부터 빠진다는 특성이 있습니다.
큐는 선형구조로 되어 있습니다.
(이해하기 편하도록 원형구조로 표현도 되고 있습니다.)
접근 방법은 가장 처음과 가장 끝 원소만 가능하며,
데이터를 넣을때는 insertion, addition, put (이하 enQueue) 라 하며,
데이터를 꺼낼때는 deletion, removal (이하 deQueue) 이라고 합니다.
큐는 가장 처음 넣은 원소 부터 뺄수 있기 때문에,
선입선출(FIFO, First-In First-Out) 이라고 합니다.
아래 표는 enQueue 와 deQueue 을 했을때의 결과 입니다.
|
|
|
|
| "D" |
|
| "C" | "C" | "C" | "C" |
| "B" | "B" | "B" |
|
|
"A" | "A" | "A" |
|
|
|
enQueue("A"); | enQueue("B"); | enQueue("C"); | deQueue(); | deQueue(); | enQueue("D"); |
큐는 enQueue 나 deQueue 을 할 때 해당 값의 위치를 알고 있어야 하는데,
그 위치를 기억하고 있는 것이 front 와 rear 입니다.
front 는 deQueue 을 할 위치를 기억 하고 있고,
rear 는 enQueue 를 할 위치를 기억 하고 있습니다.
| <- rear 위치 (enQueue) |
"B" | |
"A" |
|
<- front 위치 (deQueue) | |
큐(Queue) | front 와 rear |
2. 큐와 함께 하는 대표적인 기능들(enQueue, deQueue) 과 front, rear, Overflow, Underflow |
큐에 필요한 대표적인 기능(메소드) 에는 4가지가 있습니다.
큐에 데이터를 넣는 enQueue
큐에 데이터를 꺼내오는 deQueue
큐가 비어있는지 확인하는 isEmpty
큐가 꽉차 있는지를 확인하는 isFull
이렇게 대표적인 기능(메소드) 들이 있고,
부가적으로 front 와 rear 가 있습니다.
큐가 꽉차 있는데도 enQueue 를 했을 때 발생하는 Overflow 와
큐가 하나도 없는데 deQueue 를 했을 때 발생하는 Underflow 도 있습니다.
※ 구성의 편의상 cnt 라는 현재 개수를 저장하는 변수를 추가하였습니다.
가장 먼저 enQueue 는 아래와 같이 구성됩니다.
public void enQueue( Object o ) { if( isFull( cnt ) ) // ① { System.out.println( "Error Overflow : " + o ); return; } if( isFull( rear ) ) // ② rear = 0; queue[rear++] = o; // ③ cnt++; } |
① : enQueue 를 할때 현재 데이터 개수인 cnt 가 가득 찼다면,
꽉차 있는 상태에서 enQueue 를 실행 했기 때문에,
Overflow 라는 오류를 내게 됩니다.
② : 현재 입력할 곳인 rear 가 최상위 위치라면 0번 위치로 돌려놓습니다.
③ : rear에 데이터를 넣고 + 1 을 증가 시킵니다.
두번 째로 deQueue 는 아래와 같습니다.
public Object deQueue() { if( isEmpty( cnt ) ) // ① { System.out.println( "Error Underflow" ); return null; } if( isFull( front ) ) // ② front = 0; Object o = queue[front]; // ③ queue[front++] = null; // ④ cnt--; return o; } |
① : deQueue 를 할때 현재 cnt 의 개수가 0 이면, Underflow 오류를 발생합니다.
② : front 의 값이 MAX_SIZE 의 값과 같으면 초기화 합니다.
③ : 현재 front 위치의 queue 의 값을 Object 에 담아 리턴 합니다.
④ : 꺼낸 값 부분이 null 을 채워넣어 줍니다.
세번째로 isEmpty 는 아래와 같습니다.
public boolean isEmpty( int _cnt ) { return _cnt == 0 ? true : false; } |
들어온 값이 0 이면 true, 같지 않으면 false 를 리턴 합니다.
네번째로 isFull 은 아래와 같습니다.
public boolean isFull( int _cnt ) { return _cnt == MAX_SIZE ? true : false; } |
들어온 값이 MAX_SIZE와 같으면 true, 아니면 false 를 리턴 합니다.
부가적으로 쓰이는 front, rear, cnt 변수는 아래와 같이 초기화 합니다.
private int front = 0; private int rear = 0; private int cnt = 0; |
모두 기본값은 0 입니다.
3. 심화 : 동적 배열을 사용하는 큐 |
위와 같이 구성하였을 경우 큐에는 MAX_SIZE 라는 최대 크기가 존재합니다.
데이터의 양이 MAX_SIZE 의 크기만큼 찼을때는, Overflow 라는 오류를 내게 됩니다.
그럼 최대크기가 없는 큐를 만들어 보겠습니다.
public void enQueue( Object o ) { if( isFull( cnt ) ) { Object[] arr = new Object[MAX_SIZE * 2]; // ① int pos = 0; int i = front; while( pos != cnt ) // ② { if( i == MAX_SIZE ) i = 0; arr[pos++] = queue[i++]; // ③ front = 0; } MAX_SIZE *= 2; queue = arr; // ④ rear = cnt; } if( isFull( rear ) ) rear = 0; queue[rear++] = o; cnt++; } |
① : 우선 꽉찼을때 기존 크기의 2배인 arr 배열을 준비합니다.
② : pos 라는 변수를 이용해서 순차적으로 배열을 넣을건데,
pos 의 값이 최대값 cnt 와 같아질때까지 루프를 돕니다.
③ : i (front)부터 하나씩 증가하며 순서대로 arr 배열에다가 넣어줍니다.
④ : 마지막으로 루프가 끝나면 queue 에 arr 을 참조하게 하여 queue 배열을 바꿔줍니다.
처음 front, rear 만으로 구상하려했는데,
생각보다 너무 어려워져서, 무능한 머리탓에..
cnt 라는 총 카운트를 추가하게 되었습니다.
책에 나오는 대표적인 방법은 아니지만,
그래도 최대한 비슷하게 구현해보았습니다.
참조 : 위키백과
http://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)
참조 : C로 쓴 자료구조론 2nd Edition 120 page ~ 128 page
'program > data_structure' 카테고리의 다른 글
설정
트랙백
댓글
글
[data structure] 자료구조 스택(stack) 알고리즘 이란 ?? (java 로 구현)
Q. 스택에 대해 알아보자.
1. 스택(Stack) ??
2. 스택과 함께하는 대표적인 기능들(push, pop, isEmpty, isFull)과 SP
3. 심화 : 동적배열을 사용하는 스택
1. 스택(Stack) ?? |
흔히 자료구조를 배울때 항상 나오는것이 스택입니다.
스택은 데이터를 (임시)저장하는 저장방식입니다.
스택은 일반적으로 아래와 같은 모습을 지니고 있습니다.
[그림] 위키백과 스택
http://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D
스택을 표현할때 접시를 쌓아올린것과 같은 형태를 지니게 되는데,
이 형태를 갖는 이유는 메모리의 가장 끝(가장 아래쪽)에서부터 사용하기 때문이라고 합니다.
(확실하지 않을수 있음)
스택은 접시를 쌓아올린것과 같은 모습이기 때문에,
가장 상위 것만 접근이 가능한 제한적으로만 접근할수 있는 나열 구조입니다.
가장 상위, 가장 최근 것만 넣고 빼고 할 수 있기 때문에,
후입선출(LIFO, Last-In First-Out) 이라고 합니다.
스택은 가장 상위에서만 빼고 넣을수 있는 선형구조로 되어 있습니다.
접근 방법은 가장 상위의 목록만 가능하며,
데이터를 넣을때는 푸시(push),
데이터를 꺼낼때는 팝(pop) 이라고 합니다.
아래 표는 push와 pop을 했을 때의 결과입니다.
|
|
| "D" |
|
|
| "C" | "C" | "C" |
| "B" | "B" | "B" | "B" |
"A" | "A" | "A" | "A" | "A" |
push("A"); | push("B"); | push("C"); | push("D"); | pop(); |
스택은 push나 pop을 할때의 해당 값의 위치를 알고 있어야 하는데,
그 위치를 기억하고 있는 것이 스택 포인터 (SP, Stack Pointer) 라고 합니다.
스택 포인터는 다음 값이 들어갈 위치를 가르킵니다. (SP 의 기본 값은 -1 입니다.)
| <- SP(스택 포인터) 위치 |
"C" |
|
"B" |
|
"A" |
|
스택(Stack) | 스택포인터(Stack Pointer) |
2. 스택과 함께하는 대표적인 기능들(push, pop, isEmpty, isFull)과 SP |
스택이 필요한 대표적인 기능(메소드) 에는 4가지가 있습니다.
스택에 데이터를 넣는 push
스택의 최 상위 값을 가져오는 pop
스택이 비어있는지를 확인하는 isEmpty
스택이 꽉차 있는지를 확인하는 isFull
이렇게 대표적인 기능(메소드) 들이 있고,
부가적으로 스택 포인터 SP가 있습니다.
가장 먼저 push는 아래와 같이 구성됩니다.
public void push( Object o ) { if( isFull( sp ) ) { System.out.println( "Overflow" ); return; } stack[sp++] = o; } |
SP(스택 포인터)가 스택의 isFull() 을 호출하여 최대크기와 같다면 오류를 발생시키고,
그외의 경우에는 스택의 최상위 위치에 값을 집어 넣습니다.
두번째로 pop 은 아래와 같이 구성됩니다.
public Object pop() { if( isEmpty( sp ) ) { System.out.println( "Underflow" ); return null; } Object o = stack[--sp]; stack[sp] = null; return o; } |
SP 가 0으로 초기값과 같다면, Underflow 를 발생시키고,
그외의 경우에는 stack[--sp] 하여 스택의 최상위 위치의 값을 꺼내옵니다.
세번째로 isEmpty 는 아래와 같이 구성됩니다.
private boolean isEmpty( int _cnt ) { return _cnt == 0 ? true : false; } |
입력된 값이 최초 값과 같다면 true 를 리턴하고,
그외의 경우에는 false 를 리턴 합니다.
마지막으로 isFull 은 아래와 같이 구성됩니다.
private boolean isFull( int _cnt ) { return _cnt == MAX_SIZE ? true : false; } |
SP 의 값이 MAX_SIZE 와 같다면 true 를 리턴하고,
그외의 경우에는 false 를 리턴 합니다.
그리고 부가적으로 스택의 위치를 담당하는 SP(스택포인터) 는,
private int sp = 0; |
0 을 기본값으로 가지고 생성 됩니다.
3. 심화 : 동적배열을 사용하는 스택 |
위와 같이 구성하였을 경우 스택에는 MAX_SIZE 라는 최대 크기가 존재해야 합니다.
그래야 SP(스택포인터) 와 MAX_SIZE 를 비교하여 isFull 오류를 내야 하기 때문입니다.
그럼 최대 크기가 없는 스택을 만들어 보겠습니다.
바로 java 의 arraycopy 를 사용하면 쉽게 만들수 있습니다.
public void push( Object o ) { if( isFull( sp ) ) { Object[] arr = new Object[MAX_SIZE * 2]; System.arraycopy( stack, 0, arr, 0, MAX_SIZE ); stack = arr; MAX_SIZE *= 2; } stack[sp++] = o; } |
가장 먼저 기존 스택보다 확장된 배열을 생성합니다.
이때 크기는 통상적으로 기존 스택의 2배 크기만큼으로 생성합니다. (보라색)
그리고, System.arraycopy 를 활용하여 스택의 0번째부터, MAX_SIZE 만큼을
arr 배열에 0번째부터 복사합니다. (빨간색)
복사를 마치고 arr 의 참조값을 stack 에 덮어씌웁니다. (녹색)
마지막으로 MAX_SIZE를 2배 만큼 증가 시켜줍니다.
이렇게 해서 스택이 가득 차면 자동으로 확장되는 스택을 만들어 보았습니다.
쉽게 이해가 되시나요 ??
참조 : 위키백과 http://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D
참조 : C로 쓴 자료구조론 2nd Edition 113 page ~ 127 page
