KiTFOx's Notepad 📝

큐를 가장 쉽게 이해하는 방법은 줄을 서서 하는 싸인회를 생각하면 된다.
예를 들어서 유명 가수의 싸인회가 열린다고 가정해보자
나는 가수의 싸인회에 당첨이 되었고 현장에서 3번의 번호를 부여받았다.
다른 팬들은 1~20번의 번호를 부여받았다고 가정하였을 때, 진행자가 1번부터 싸인을 받으러 오라고 부를 것이다.
그리고 2~20번의 사람들에게 차례로 줄을 서라고 할 것이고 그 다음 차례는 2번부터 순서대로 싸인을 받으러 줄을 이탈할 것이다.
이게 바로 큐의 개념이다! FIFO(First In First Out) 선입선출 자료구조이다.
먼저 들어간 데이터는 먼저 빠져나온다. 즉 2번이 맨 앞에 있는데 3번이 먼저 빠져나갈 수 없다는 것이다.

큐가 쓰이는 구조는 어디에 있을 까? 미루어 짐작해보건데
명절날 내려가는 KTX 예매를 할 때, 내 앞의 대기자 00명이 있습니다. 라는 문구를 본 적 있는가?
아마도 그러한 곳에 쓰일 것 같다.
물론 이것 말고도 많은 곳에 쓰이겠지만 가장 가시적으로 볼 수 있는 느낌이 아닐까 싶다.

스택은 굉장히 많이 쓰이는 개념이다.
’가장 먼저 들어간 데이터가 가장 마지막에 나오는(FILO, First In Last Out) 구조‘ 이다.
배열과 링크드 리스트 둘다 구현 가능한데 이전 포스팅에서 언급했듯이
탐색은 빠른 배열, 용량의 제한이 자유로운 링크드 리스트 이기에 데이터의 종류에 따라 다르게 쓰일 듯하다.

스택은 말그대로 쌓다 인데, 가장 와닿는 것은 프링글스 통이 아닐까 싶다..!
물론 프링글스를 뒤집으면 우르르 쏟아져나온다만은.. 프링글스는 위에서부터 꺼내서 제일 밑에까지 먹을 수 있는 과자이다.
반대로 프링글스 통에 과자를 다시 넣는다면 맨 마지막에 넣은 과자부터 꺼낼 수 있을 것이다.

스택을 사용하여서 어떤 것을 만들면 유용할까 하고 생각하여보았는데
아무래도 Undo, Redo 아닐까 싶다.
한글(.hwp)에서도 잘 볼 수 있는데, 단축키 Ctrl+Z 를 통해 이전의 작업으로 돌아가는 기능 말이다.
이전의 작업들을 한개한개씩 쌓아놓고, 만약 되돌아가기를 실행한다면 한큐에 작업했던 것들을 제거하면 이전의 작업으로 돌아갈 수 있을 것이다.

프로그램을 짜다보면 배열을 사용할 때가 많아진다.

배열은 크기가 한정되어 있기 때문에 공간이 모자라는 경우가 종종 생길 수 있는데, C++을 사용하는 사람들은 STL의 vector를 보통 떠올린다. 나의 경우도 그랬고

하지만 STL의 vector 경우 크기에 상관없이 자유자재로 늘어나는 것처럼 보이지만 배열 형태에서 배열이 가득 찰 때마다 크기를 1.5배 ~ 2배 (컴파일러에 따라 다름) 늘린 후 다시 옮겨담는 형식이라고 한다.

따라서 링크드 리스트랑은 다른 개념이다.

링크드 리스트는 C에서 배열의 크기가 한정되어 있는 한계를 극복하고자 만든 개념이다.

하지만 여러가지 장단점이 있기에 소개하려고 한다.

🔹01. 링크드 리스트

유연하게 크기를 바꿀 수 있는 구조를 보고 '리스트(list)'라고 하는데, 링크드 리스트는 이 중에서 가장 간단히 구현하는 방법이다.

'리스트' 내의 각 요소는 '노드(Node)' 라고 부른다.

'링크드'는 '연결된' 이라는 뜻이다. 즉 링크드 리스트는 연결된 리스트이다.

구조

노드는 데이터와 포인터를 가진 구조입니다.

포인터는 뒤에올 노드를 가르킴으로써 해당 포인터를 이용해 다음 노드를 탐색할 수 있다.

첫 번째 노드를 헤드, 마지막 노드를 테일이라고 부른다.

마치 KTX 기차를 이어붙이는 것 처럼 뒤를 이어서 붙인다.

기차 사이의 이음새 역활을 하는 고리가 노드의 포인터가 하는 역할이다.

struct Node
{
    Data data;		//데이터
    struct Node* NextNode;	//다음 노드를 가리키는 포인터
}

링크드 리스트를 설정하기 위해서는 코드블록이 종료됨에 따라 사라지지 않도록 malloc() 함수를 통해 할당을 해준다.

이러한 링크드 리스트는 탐색 연산에서 약점을 가지고 있다.

앞에서부터 쭈욱 연결된 구조이다 보니 HEAD부터 탐색을 시작해서 만약 10개의 노드 중 10번째 노드를 찾으려고 한다면 1번부터 탐색해서 10번까지 다달아야한다.

따라서 n개의 노드 중 n번째 노드를 찾으려고 한다면 n번 탐색을 진행해야하기에 비용이 크고 속도가 느리다.

❗배열에 비해 링크드 리스트의 장단점 정리❗

🔸단점🔸

  1. 포인터 때문에 각 노드마다 4 byte의 메모리가 추가로 필요함

  2. 최약의 경우 n회의 노드 탐색 루프 -> 비용이 크고 속도가 느림

🔸장점🔸

  1. 새로운 노드의 추가,삽입,삭제가 쉽고 빠름

따라서, 링크드 리스트는 추가,삽입,삭제가 잦고 조회는 드문 곳에 유용하다.

🔹02. 더블 링크드 리스트

더블 링크드 리스트는 링크드 리스트의 탐색 기능을 개선한 자료구조이다.

이전 노드를 참조하는 포인터를 하나 더 Node 안에 만들어서 양방향 탐색이 가능하도록 만들었다.

🔹03. 환형 링크드 리스트

환형 링크드 리스트는 헤드와 테일을 연결한 링크드 리스트이다.

이러한 방법을 사용하면 테일에 접근하는 비용이 작아져서, 뒤에서부터 노드를 찾아 나가는 탐색을 구현할 수 있다.

예를들어 10개의 노드 중 8번째를 찾고 싶다면 HEAD에서 TAIL로 2번 탐색하면 더 빠르게 찾을 수 있다.

🔅알아두면 좋은 TIP🔅

유연하게 크기를 바꿀 수 있는 구조를 보고 '리스트(list)'라고 하는데,

C++ STL vector도 리스트의 일종이라고 볼 수 있겠다.

여기서 C++ STL vector 는 동적 배열의 형태이고,

C++ STL list는 더블 링크드 리스트로 구성되어있다고 한다.