[자료구조 및 프로그래밍] 5. Stack & Queue With Linked List

지난 글에서 Linked List 의 개념과 그 구현에 대해 정리하였다.

이번에는 Array 로 구현했던 Stack 과 Queue를 Linked List 로 구현하는 과정을 살펴보고자 한다.

---

Stack With Linked List

스택을 연결리스트로 구현해보자.

연결리스트에서 데이터를 중간에 삽입할 때는 이전 노드의 주소를 알아야 하기 때문에 아주 복잡했다.

데이터를 맨 처음에 삽입하는 것이 아주 간단하기 때문에,

스택의 데이터 삽입과 삭제가 빈번히 일어나는 top 을 연결리스트의 첫 head로 설정하자.

그림으로 나타내면 이렇게 나타난다.

 

스택에 데이터를 추가하면 추가된 데이터를 top 이 가리키고, 추가된 데이터가 기존 데이터를 가리키는 방식으로 구현하면 된다.

스택에서 데이터를 뺄 때는 top 의 데이터를 빼고, top의 데이터가 기리키고 있던 node의 주소를 top 으로 설정하면 된다.

top: pointer

init: top <- null

push(x) {
  p <- new()
  if (p = ^)
    OVERFLOW!
  
  ITEM(p) <- x
  LINK(p) <- top
  top <- p
}

pop() {
  if (top = ^) {
    UNDERFLOW!
  }
  
  p <- top
  x <- ITEM(top)
  top <- LINK(top)
  free(p)
  return x
}

아래와 같이 간단하게 코드로 구현할 수 있다.

top 의 역할은 head 와 같기 때문에 head 변수는 따로 필요하지 않다.

Linked List 를 이용하여 자료구조를 구현할 때, 삭제를 하면 반드시 메모리를 해제하는 free가 필요하므로,

free를 위해 삭제할 메모리 주소를 변수에 꼭 미리 저장해두자.

---

Queue With Linked List

이번에는 Queue 를 구현해보자.

큐는 front 와 back 이 나누어져 있으므로, 데이터를 어디에 추가하고 어디에서 뺄 지 결정해야한다.

한번 queue 의 fornt 를 연결리스트의 head 로 보고, queue의 back 을 연결리스트의 마지막 노드라고 생각해보자.

 

데이터를 pop할 때는, Linked List 의 첫 번째 노드를 삭제한다.

삭제하고나서 head가 첫번째 노드의 Link 를 가리키도록 하면 pop이 끝난다.

 

데이터를 push 할 때는, 데이터를 연결리스트의 마지막 노드에 저장하기로 하였는데, 마지막 데이터를 찾기 위해 매번 Traverse 하는 것은 비효율적이므로 현재 저장된 마지막 노드의 주소를 별도 변수에 저장한다.

데이터를 새로 추가하면, 추가한 데이터의 Link 는 반드시 Null 이된다.

별도 변수에 저장한 마지막 노드의 Link 를 새로 추가한 노드로 설정하면 Push 가 끝난다.

 

이제 이를 코드로 작성하면 아래와 같이 된다.

head, last : pointer

init: head <- null, last <- null

push(x) {
  p <- new()
  if (p = ^)
    OVERFLOW!
  
  ITEM(p) <- x
  LINK(p) <- null
  
  LINK(last) <- p
  last <- p
}

pop() {
  if (head = ^)
    UNDERFLOW!
    
  p <- head
  x <- ITEM(head)
  head <- LINK(head)
  free(p)
  return x
}

이제 이 코드로 충분한지 node 가 한개만 남았을 때 pop을 하는 상황을 생각해보자.

head와 last 는 모두 그 노드를 가리키고 있을 것이다.

이때 pop 을 하면 Link(head) = null 이므로, head 에는 null 이 저장된다.

 

따라서 큐가 비어잇는 초기 상태의 head 는 null 이 된다.

이 상황에서 다시 데이터를 push 한다고 생각해보자.

데이터를 push 하면 last 가 새로 생성된 데이터를 잘 가리키지만, head 는 여전히 null 을 가리키고 있기 때문에 

이 상황에서 다시 pop 을 하려고 하면 underflow가 발생한다.

 

따라서 head 가 null 일 때 데이터를 추가하면 head 를 새로 생성된 데이터로 가리켜줄 필요가 있다.

그리고 이때는 last 변수가 가리키는 노드가 없기 때문에 LINK(last) 를 설정할 수도 없다.

따라서 push 부분을 아래와 같이 고쳐야 한다.

 

push(x) {
  p <- new()
  if (p = ^)
    OVERFLOW!
  
  ITEM(p) <- x
  LINK(p) <- null
  
  if (head = ^) { // 데이터가 없다면 초기 head 설정
    head <- p
  } else {        // 데이터가 있다면 last가 존재하므로 last 연결 바꿔주기
    LINK(last) <- p 
  }
  
  last <- p
}

그리고 이렇게 했을 때 큐가 잘 동작하기 때문에 last 변수의 초기화는 아무 값을 넣어도 상관없음을 알 수 있다.

따라서 이를 모두 정리하면 아래와 같이 코드를 쓸 수 있다.

head, last : pointer

init: head <- null, last <- arbitary

push(x) {
  p <- new()
  if (p = ^)
    OVERFLOW!
  
  ITEM(p) <- x
  LINK(p) <- null
  
  if (head = ^) {
    head <- p
  } else {
    LINK(last) <- p 
  }
  
  last <- p
}

pop() {
  if (head = ^)
    UNDERFLOW!
    
  p <- head
  x <- ITEM(head)
  head <- LINK(head)
  free(p)
  return x
}

---

이것으로 연결리스트를 이용한 스택과 큐 구현을 정리하였다.

큐를 구현할 때는 조금 복잡한 부분이 많아서 구현을 실수하지 않도록 주의가 필요해보인다.

일반적인 상황을 먼저 구현하고나서, 데이터가 1개 남았을 때 pop, 그리고 다시 비어있을 때 push 를 해보면서 발생하는 문제를 수정하면 코드를 완성할 수 있다.

 

다음 글에서는 Linked List 의 메모리 관리 시스템을 Array 스택을 이용해 구현하는 과정을 정리해보겠다.