I'll never know if I never commit

덱 이란? 덱은 큐와 스택의 기능을 모두 갖춘 만능 리스트라고 생각하면 된다. 즉, 앞 ,뒤 모두에서 데이터가 삽입가능하고, 앞, 뒤 모두에서 데이터가 삭제가 가능한 자료구조이다. 즉 add rear 와 delete front는 큐의 성질이고, add rear 와 delete rear는 스택의 성질이라고 보면 된다. 덱은 주로 이중연결리스트로 구현이 되는데, 그 이유는 front와 rear에서 모두 삽입 , 삭제하려면 양쪽으로 링크를 가진 이중연결리스트가 편리하기 때문이다. 또한 덱은 앞,뒤에서 삭제삽입이 이루어지기 때문에, 큐처럼 head 포인터와 tail포인터를 모두 가지고 있어야한다. 덱은 앞서 봤던 큐와 스택을 짬뽕?! 해놓은 개념이라 까다롭지 않으므로 바로 소스코드를 살펴보도록 하겠다! 역시나 ..

큐 란 무엇인가? FIFO, "가장 먼저 들어온 것이 가장 먼저나가는 " 자료구조의 형태이다. 이는 영화관 매표소의 줄을 생각하면 쉽다. 가장 먼저 온 사람이 가장 먼저 티켓을 받고 줄에서 나간다! 그래서 큐는 리스트의 두군데에서 입출력을 담당한다. 스택의 경우 tail 즉 꼬리부분이 입출력을 모두 담당했지만, 큐의 경우 입력은 뒤에서! 출력은 앞에서 ! 담당한다. 그래서 각각 출력을 담당하는 부분을 front , 입력을 rear 라고 한다. 그러면 이러한 큐를 어떻게 구현하는가 ? 일단 크게 세가지의 방법이 있다. 1) 배열리스트 구현 2)원형 배열 구현 3)연결리스트 구현 1번 배열리스트 구현은 너무 쉽게 구현되기 때문에 패스하고, 2번과 3번을 구현해보도록 하겠다. 먼저 원형큐를 살펴보자! 배열을 ..

스택은 LIFO , "가장 늦게 들어간 요소가 가장 먼저나오는" 데이터 구조이다. 그럼 이 스택을 어떻게 구현할 수 있을까? 아마 첫번째로 떠오르는 것은 배열리스트 일 것이다. 동적으로 배열을 할당받는 방법도 있겠지만, '배열'의 형태로 구현할 경우 어쩔수없이 스택은 저장할 수 있는 자료에 있어서 한계가 있다. 이를 위해서는 '연결리스트'로 스택을 구현해주면 된다. 동적할당된 배열의 형태가 아니라, 연결리스트의 link 필드로, 동적 할당된 요소들을 계속해서 연결시켜주면, 우리는 길이의 제한 없이 스택을 이용할 수 있다. 먼저 소스코드에 구현된 세가지 클래스를 설명한 이미지이다. 이 코드는 세가지의 class로 나뉜다. 1) Node Class: 스택의 'Node'가 될 요소들의 데이터와 요소들을 이어줄..

리스트에는 두가지 종류가 있다. 배열리스트와 연결리스트이다. 배열리스트는 말 그대로 '배열'을 이용하여 리스트를 구현한 것이고, 연결리스트는 포인터를 이용하여 리스트를 구현한 것이다. - 배열 리스트의 장점은 원하는 원소를 O(1) 시간으로 찾을 수 있다는 것이다. 하지만 단점은 원소의 개수가 제한되어 있다는 것, 삽입과 삭제가 까다롭다는 점이다. 아무리 탐색에서 O(1)로 효율적이더라도 , 삽입과 삭제에서 O(n)이 걸리므로 그다지 효율적이라 하지 못하겠다. 하지만 그럼에도 불구하고 배열리스트는 리스트 내의 변동 사항이 없고, 리스트의 크기가 클 때 사용하면 효율적일 것이다. 다음은 배열리스트 ADT를 C++로 구현한 것이다. 예외처리는 객체 참조자를 반환해야하는 함수에만 해주었다. 배열리스트 C++ ..