Open-Closed Principle

연결 리스트로 큐를 구현하면 동적 할당의 성질에 의해 메모리의 한계까지 큐의 크기를 늘릴 수도 있고, 또 큐가 아주 작을 때에도 메모리도 조금 밖에 차지하지 않는다. 단순 연결 리스트를 이용하여 큐를 구현하는 것은 약간의 무리가 있다. 큐를 구현하려면 앞 노드의 위치와 뒷 노드의 위치를 모두 알고 있어야 하므로 할 수 없이 이중 경결 리스트를 사용하여야 한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101..

큐는 입구와 출구가 따로 있는 긴 통이라고 생각하면 된다. 큐는 접근이 제한된 자료구조이며 행위적 측면을 부여받은 추상적 자료형이기 때문에 큐를 조작하는 방법은 두가지로 제한되어 있다. 큐를 조작하는 방법은 put 동작과 get 동작이 있다. 큐에 자료를 집어넣을 때는 뒤(rear)에서 집어넣는다. 이 집어넣는 동작은 put 동작이라고 한다. 그리고 큐에서 자료를 얻어낼 때는 앞(front)에서 얻어낸다. 이 자료를 얻는 동작은 get 동작이라고 한다. 배열을 이용해서 큐를 구현하는 것은 문제가 없어 보이지만 문제가 많다. 배열을 이용한 큐의 구현은 자료를 저장할 배열과 앞과 뒤를 가리키는 변수만 있으면 될 것같다. 하지만 큐에 자료를 집어 넣고 빼는 동작을 계속하다보면 rear와 front는 계속 증가..

연결리스트 자체가 동적인 할당을 통해서 구현되기 때문에 연결리스트를 이용해서 구현되는 스탹은 매우 유연하다. 연결 리스트를 이용하여 스택을 구현할 때의 장점은 현재 스택에 저장되어 있는 자료 만큼만 메모리를 잡아먹기 때문에 메모리가 절약되고 스택의 크기가 메모리가 허용하는 한도에서 커질 수 있다는 것이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include #include // 리스트 노드 typedef struct _node{ int key; ..

스택은 제한된 접근 방식의 행위적 측면을 부여받은 자료 구조이다. 이러한 자료구조를 추상적 자료 구조(Abstract Data Structure)라고 한다. 스택이 어떤 제한된 접근 방식과 행위적 부여 받았는지 지금부터 살펴보도록 하겠다. 스택의 구조는 매우 간단한다. 스택은 밑이 막힌 긴 통이라고 보면 되겠다. 밑이 막힌긴 통은 무언가를 넣는 곳과 무언가를 통에서 빼내는 곳이 같다. 입구와 출구가 같기 때문에 먼저 들어간 것은 밑에 있게 되고 나중에 들어간 것이 위에 있다.그러면 제일 나중에 들어간 것이 제일 먼저 나오게 된다. 그래서 스택을 LIFO(Last In First Out) 구조라고 한다. 스택을 프로그램에서 구현할 때에는 여러가지 방법이 있지만 가장 많이 사용되는 방법은 배열과 연결 리스트..

참고 : 이중 연결 리스트는 단순 연결 리스트와 함께 가장 많이 사용되는 연결 리스트의 형태이다. 단순 연결 리스트가 다음의 노드를 가리키는 하나의 링크를 가져서 바로 전의 노드를 알 수 없던 단점에 비해서, 이중 연결 리스트는 다음의 노드를 가리키는 링크와 전의 노드를 가리키는 링크 두 가지를 가져서 바로 전의 노드에도 접근할 수 있다는 것이 가장 큰 장점이다. 물론 하나의 링크를 더 사용하기 때문에 단순 연결 리스트보다는 메모리를 더 소모 한다. 이중 연결 리스트의 Node 구조이다. 12345typedef struct _dnode{ int key; // 정보 struct _dnode *prev; // 전 노드링크 struct _dnode *next; // 다음 노드링크} dnode;cs이중 연결 리..

연결 리스트는 노드(node)와 링크(link)로 구성이 된다.노드 : 실제의 정보를 담고 있는 하나의 단위링크 : 인접 노드의 위치를 저장하고 있어 연결 리스트의 순서를 유지할 수 있게 하는 연결고리연결 리스트는 정적인 자료 구조인 배열과는 달리 동적인 자료 구조이다. 연결 리스트는 필요하면 할당하고, 필요없으면 해제하는 식의 메모리 관리가 가능하기 때문에 배열처럼 여분의 공간을 마련할 필요가 없어 메모리를 절약할 수 있는 이점이 있다. 연결 리스트는 동적으로 메모리를 사용하기 때문에 프로그램의 실행중에도 얼마든지 규모를 크게 하든지, 작게 할 수 있다. 또 연결 리스트가 배열과 다른점은 배열은 메모리의 연속된 공간을 차지하는데 비해서 연결 리스트는 동적으로 수시로 할당 해제되기 때문에 메모리의 연속된..