[Data Structure] CHAP 7. Linked List based Stack & Queue ( 연결리스트로 스택,큐 구현) - C언어 ver.

저번 챕터에서 했던 연결리스트에 이어 이번 챕터에서는 연결 리스트를 이용해 스택과 큐를 구현하는 것을 기록하려고 한다. 배운거 + 배운거 = 쉬운거 일 줄 알았으나.. 아니었던 거😂 이번 챕터에서는 아래 순서로 작성할 예정이다.

• 연결리스트로 스택 구현하기
• 연결리스트로 큐 구현하기

그럼 시작-!!

---

1. 연결리스트로 스택 구현하기

배운지 오래돼서 리마인드를 해주자면, 스택은 후입선출구조 즉 push와 pop이 top에서만 이루어지는 자료구조이다.

생긴건 단일연결리스트지만 스택이니까 t에서만 push,pop

위 사진에서 t는 top을 가리키며, push,pop 모두 t에서 일어난다.

1-1. push 구현

push는 새 요소를 넣는 것을 말한다. 위 linked list에 black이라는 요소를 넣는다고 가정하자. 먼저 black이라는 새 노드를 생성한다. 그 후 이 노드를 위 연결리스트의 가장 앞에 연결해야한다.
새 노드의 next를 t가 가리키고 있는 노드, 즉 첫 노드에 연결해준다. 그 후 t를 새 노드에 연결해주면 끝난다. 정리하면

• 노드 생성 ( 편의상 새 노드는 new라고 칭한다. )
• new.next = t
• t = new

라고 정리할 수 있겠다. top에서만 작업하면 되므로 BIG-O로 나타낸다면 O(1)이 된다.

1-2. pop 구현

pop은 top에 가장 가까이 있는 요소를 제거하는 것을 의미한다. 위 linked list에서 red요소를 제거하는 작업을 한다고 가정해보자.

전반적으로 생각해보면 t를 yellow에 연결하고, 기존 red의 요소를 return해주면 된다. 그러나 t를 곧장 yellow노드에 연결해버리면 red노드의 주소를 알아낼 수 없고, 그렇게 되면 값을 리턴할 수 없기 때문에  tmp라는 새로운 변수를 만들어 넣어준다. 이름은 아무래도 상관없다.
tmp로 t가 가리키는 노드를 가리킨다. 이렇게 red의 주소를 tmp에 넣어두고 t를 yellow노드로 옮긴다. 그 후 tmp가 가리키는 노드, 즉 red노드의 요소를 리턴해준다. 그 후 tmp를 없애주면 된다. 정리하면 다음과 같다.

• tmp = t
• t = t.next
• return(tmp.element)
• free(tmp)

이것도 마찬가지로 top에서만 작업하면 되므로 BIG-O로 나타낸다면 O(1)이 된다.

---

2. 연결리스트로 큐 구현하기

큐는 선입선출구조로 rear에서 enqueue가, front에서 dequeue가 이루어지는 자료구조이다.

위 사진에서 f는 front, r은 rear를 가리킨다. 헷갈릴 수 있겠지만 f에서 데이터가 제거되고, r에서 데이터가 생성된다.

2-1. rear에서 enqueue 구현

enqueue는 노드를 생성하는 것을 의미한다. 위 연결리스트에 purple이라는 노드를 생성하는 상황을 가정해보자.
r이 가리키고 있는 blue노드의 링크를 purple에 연결해준다. rear을 purple에 연결하게 되면 blue노드의 주소를 찾기 위해 많은 시간이 소요될 수 있어 blue를 purple에 연결하는 작업을 먼저 해준다. 그 후 r을 purple노드에 연결해주면 된다. 정리하면 다음과 같다

• r.next = new
• r = new

이 작업은 rear에서만 이루어지므로, BIG-O로 나타내면 O(1)이 된다.

2-2. front에서 dequeue 구현

dequeue는 노드를 제거하는 것을 의미한다. 마찬가지로 위 연결리스트에서 red노드를 제거하는 상황을 가정해보자.
f를 바로 yellow노드로 옮기면 red노드의 주소를 알 수 없기 때문에 tmp라는 변수를 따로 설정해준다. tmp에 f가 연결하고 있는 노드, 즉 red노드를 연결한 후 f를 yellow노드에 연결해준다. 그 후 tmp를 없애주면 된다. 정리하면 다음과 같다.

• tmp = f
• f = f.next
• return(tmp.element)
• free(tmp)

이 작업도 enqueue와 마찬가지로 front에서만 이루어지므로, BIG-O로 나타내면 O(1)이 된다.