앞서 배열을 이용해 큐를 구현했었다. 이번에는 연결 리스트를 이용해서 큐를 구현해보자. 연결 리스트로 구현한 큐도 스택과 마찬가지로 크기가 제한되지 않고 필요한 메모리만 사용한다는 장점과 배열을 사용하는 방식보다는 구현이 조금 상대적으로 복잡하고 링크 필드를 추가로 사용하기 때문에 메모리 공간을 조금 더 사용하는 단점이 있다. 배열을 이용한 큐에서는 front와 rear 변수가 배열의 인덱스 값을 갖고 있는 것과 달리 연결 리스트를 이용한 큐에서는 front와 rear가 노드를 가리키는 포인터 변수이다. front 포인터는 가장 먼저 삽입된 노드를 가리키고, rear 포인터는 가장 최근에 삽입된 노드를 가리킨다. 큐가 공백 상태일 때는 front, rear 둘 다 NULL을 가리킨다. 삽입/삭제 연산 데..

연결 리스트로 구현한 스택 앞서 배열을 이용해 스택을 구현했었다. 이번에는 연결 리스트를 이용해서 스택을 구현해보자. 배열을 이용한 스택과 달리 연결 리스트를 이용한 스택에서는 각 요소들을 한꺼번에 할당하지 않고 필요할 때마다 하나씩 동적 할당한다. 연결 리스트로 스택을 구현하기 때문에 노드 클래스를 추가로 정의해서 스택에 저장할 요소 정보(데이터 필드)와 다음 노드를 가리키기 위한 포인터(링크 필드)를 멤버 변수로 갖게 한다. 배열로 스택을 구현할 때는 top 변수가 배열의 인덱스를 가리키는 정수형 변수였다. 연결 리스트로 스택을 구현할 때는 top은 포인터 변수가 된다. top이 가리키는 노드가 최상단 노드가 되고, 노드의 링크 필드가 NULL인 노드가 가장 먼저 삽입된 노드이다. 삽입/삭제 연산 t..

연결 리스트란? 프로그래밍을 할 때 배열은 아주 많이 사용된다. 해당 블로그에서는 앞서 배열을 이용해 스택과 큐를 구현하는 방법을 소개했다. 그런데 배열을 이용할 때는 항상 따라오는 단점이 하나 있다. 바로 고정된 크기이다. 이것을 해결하기 위해 사용하는 방법이 연결 리스트(linked list)이다. 연결 리스트는 크기를 늘리고 줄이고 할 수 있다. 📍 후에 리스트를 다룰 때 다시 얘기하겠지만 연결 리스트와 리스트는 다르다. 연결 리스트를 쉽게 이해하기 위해 두 가지 사진을 가져왔다. 왼쪽 사진은 2호선 지하철, 오른쪽 사진은 화물 기차의 사진이다. 2호선은 8-4칸까지 있기 때문에 처음 만든 크기대로 계속 사용될 것이다. 반면 오른쪽 사진의 화물 기차는 뒤에 컨테이너를 붙였다 뗐다 하면서 연결할 개수..

연결 리스트를 알아 보기 전에 필요한 것들을 먼저 알아보자. 자기 참조 구조체 자기 참조 구조체(self-referential structure)는 멤버 변수들 중에서 자신과 동일한 구조체를 가리키는 포인터가 하나 이상 존재하는 구조체이다. 미리(컴파일 시에) 일정한 크기를 할당하는 배열이나 일반 구조체와 달리 항목의 개수를 미리 예측할 수 없는 경우에 자기 참조 구조체를 정의하고 동적으로 객체를 생성하여 이들을 포인터로 연결하는 구조체에서 흔히 사용된다. typedef struct _node { string name; struct _node *next; // 자기 참조 } Node; 위 코드에서 볼 수 있듯이 구조체의 멤버 변수에 자기 자신을 가리키는 포인터를 멤버 변수로 갖고 있다. 자기 참조 구조체..

앞에서 배열을 이용해 덱을 직접 구현해보았다. 이번에는 C++에서 제공하는 표준 템플릿 라이브러리(STL)을 이용해보자. STL은 프로그래밍에서 공통적으로 사용되는 자료구조와 알고리즘에 대한 클래스이다. 템플릿을 기반으로 작성되었기 때문에 어떤 자료형(사용자 정의 자료형 포함)에도 사용할 수 있다. 덱 템플릿 deque을 사용하려면 소스 코드에 헤더파일을 포함시키면 된다. #include using namespace std; // deque 이름; deque deque_name; deque의 멤버 함수 void push_front (const value_type& val); void push_front (value_type&& val); deque의 가장 앞 쪽에 전달받은 val을 삽입한다. void p..

앞에서 배열을 이용해 큐를 직접 구현해보았다. 이번에는 C++에서 제공하는 표준 템플릿 라이브러리(STL)을 이용해보자. STL은 프로그래밍에서 공통적으로 사용되는 자료구조와 알고리즘에 대한 클래스이다. 템플릿을 기반으로 작성되었기 때문에 어떤 자료형(사용자 정의 자료형 포함)에도 사용할 수 있다. 큐 템플릿 queue를 사용하려면 소스 코드에 헤더파일을 포함시키면 된다. #include using namespace std; // queue 이름; queue queue_name; queue의 멤버 함수 void push(const value_type& val); void push(value_type&& val); 가장 최근에 삽입된 위치 뒤에 전달받은 val을 삽입한다. void pop(); 가장 먼저 ..

덱 이란? 덱(deque)은 double-ended queue의 줄임말로, rear에서는 삽입 front에서는 삭제 연산만 가능했던 queue와 달리 rear, front 모두에서 삽입/삭제 연산을 허용하는 자료구조이다. 덱의 ADT 데이터 : 전단과 후단을 통한 접근을 허용하는 요소들의 모음 연산 addFront(x) : 덱이 꽉 차지 않았다면 전달받은 x를 덱의 맨 앞에 추가한다. addRear(x) : 덱이 꽉 차지 않았다면 전달받은 x를 덱의 맨 뒤에 추가한다. (enqueue(x)와 동일) deleteFront() : 덱이 비어있지 않으면 덱 맨 앞 요소를 삭제하고 반환한다. (dequeue()와 동일) deleteRear() : 덱이 비어있지 않으면 덱 맨 뒤 요소를 삭제하고 반환한다. get..

배열을 이용해 정수(int)를 저장하는 큐를 구현해보자. 일단 정수를 저장할 1차원 배열이 필요하다. 이를 int data[MAX_QUEUE_SIZE] 라고 하자. (MAX_QUEUE_SIZE는 큐에 저장할 수 있는 최대 요소 개수를 나타낸다.) 또, 큐에서는 삽입 연산을 위한 변수 rear와 삭제 연산을 위한 변수 front가 필요하다. 큐를 처음 생성하면 rear와 front는 0으로 초기화한다. 원형 큐에서는 rear와 front가 원의 형태로 계속 순환한다. 두 변수를 순환시키는 것은 나머지 연산자인 mod 연산으로 처리한다. front ← (front + 1) mod MAX_QUEUE_SIZE; rear ← (rear + 1) mod MAX_QUEUE_SIZE; mod 연산으로 인해 front와..