[바미] Go - Packaging 과 Stack, Queue에 대해 알아보자!

안녕하세요. 오늘은 Go의 Packaging 과 Stack, Queue에 대해 알아보겠습니다.

 

패키지(Package)라는 것은 어떤 모듈, 기능 등을 묶어 놓은 것을 의미 합니다.

Go 자체가 가지고 있는 "fmt"라는 패키지가 있는데 "format"의 약자인데 이것은 출력과 관련된 것들을 묶어놓은 것이고, "math"라는 패키지가 있는데 수학과 관련된 함수들을 묶어 놓은 패키지 입니다.
이런 관련된 기능들을 묶어 놓은 것을 패키지(Package)라고 합니다.

 

이전에 Linked List를 만들었었는데 그 외에도 Stack, Queue, Tree, Heap들을 하나의 패키지로 만들어서 dataStruct라는 것으로 만들어 늘려가볼까 합니다.

 

먼저 지난 시간에 만들었던 Linked List를 패키지로 분리시켜보죠.

우선 패키지를 만들어야 하니까 폴더를 하나 생성해줍시다.

dataStruct라는 폴더를 만들어 준 뒤 그 안에 linkedList.go라는 파일을 생성해줍니다.

이제 linkedList.go 파일을 작성해봅시다.

linkedList.go

package dataStruct

import "fmt"

type Node struct {
    next *Node
    prev *Node
    val  int
}

type LinkedList struct {
    root *Node
    tail *Node
}

func (l *LinkedList) AddNode(val int) {
    if l.root == nil {
        l.root = &Node{val: val}
        l.tail = l.root
        return
    }
    l.tail.next = &Node{val: val}
    prev := l.tail
    l.tail = l.tail.next
    l.tail.prev = prev
}

func (l *LinkedList) RemoveNode(node *Node) {
    if node == l.root {
        l.root = l.root.next
        l.root.prev = nil
        node.next = nil
        return
    }

    prev := node.prev

    if node == l.tail {
        prev.next = nil
        l.tail.prev = nil
        l.tail = prev
    } else {
        node.prev = nil
        prev.next = prev.next.next
        prev.next.prev = prev
    }
    node.next = nil
}

func (l *LinkedList) PrintNodes() {
    node := l.root
    for node.next != nil {
        fmt.Printf("%d -> ", node.val)
        node = node.next
    }
    fmt.Printf("%d\n", node.val)
}

func (l *LinkedList) PrintReverse() {
    node := l.tail
    for node.prev != nil {
        fmt.Printf("%d -> ", node.val)
        node = node.prev
    }
    fmt.Printf("%d\n", node.val)
}

기존에 linked List를 작성했던 코드를 잘라내어 가져옵니다.
그 후 main.go로 돌아와서 위의 패키지를 써 줍니다.

main.go

package main

import (
    "fmt"

    "./dataStruct"
)

func main() {
    list := &dataStruct.LinkedList{}
    list.AddNode(0)

    for i := 1; i < 10; i++ {
        list.AddNode(i)
    }

    list.PrintNodes()

    list.RemoveNode(list.root.next)

    list.PrintNodes()

    list.RemoveNode(list.root)

    list.PrintNodes()

    list.RemoveNode(list.tail)

    list.PrintNodes()
    fmt.Printf("tail:%d\n", list.tail.val)

    list.PrintReverse()

    a := []int{1, 2, 3, 4, 5}
    a = append(a[0:2], a[3:]...)
    fmt.Println(a)
}

LinkedList{}는 dataStruct 패키지 안에 있는 LinkedList struct이므로 다음과 같이 수정해 줍니다.

이렇게 수정해주면

위와 같이 빨간줄이 그어지면서 에러가 뜰텐데

에러 내용은 다음과 같습니다.

list.root가 정의되지 않았다는 의미인데 dataStruct 패키지 안에 있는LinkedList struct는 정의가 되어있음에도 불구하고 에러가 납니다. 그 이유는 패키지에 외부로 공개되는 정보가 있고, 외부로 공개되지 않는 정보를 구분하기 때문입니다.

그러니까 dataStruct 패키지 안에 있는LinkedList struct의 root는 외부로 공개를 하지 않는 상태입니다.

그것을 구분하는 방법은 어떤 함수, 구조체, 변수 등의 첫글자가 대문자이면 외부로 부터 공개(Public)가 되고, 첫글자가 소문자면 외부로 부터 공개가 되지 않게 됩니다. (private)

type LinkedList struct {
    root *Node
    tail *Node
}

이것만 살펴보면 LinkedList struct는 첫글자가 대문자이기 때문에 외부로부터 공개가 되지만, root, tail은 소문자이기 때문에 외부로부터 공개가 되지 않죠.

그렇기 때문에 외부 패키지에서도 공개되도록 root, tail의 첫글자를 대문자로 바꾸어 줍니다.

dataStruct/likedList.go

  package dataStruct

  import "fmt"

  type Node struct {
    next *Node
    prev *Node
    val  int
  }

  type LinkedList struct {
    Root *Node
    Tail *Node
  }

  func (l *LinkedList) AddNode(val int) {
    if l.Root == nil {
      l.Root = &Node{val: val}
      l.Tail = l.Root
      return
    }
    l.Tail.next = &Node{val: val}
    prev := l.Tail
    l.Tail = l.Tail.next
    l.Tail.prev = prev
  }

  func (l *LinkedList) RemoveNode(node *Node) {
    if node == l.Root {
      l.Root = l.Root.next
      l.Root.prev = nil
      node.next = nil
      return
    }

    prev := node.prev

    if node == l.Tail {
      prev.next = nil
      l.Tail.prev = nil
      l.Tail = prev
    } else {
      node.prev = nil
      prev.next = prev.next.next
      prev.next.prev = prev
    }
    node.next = nil
  }

  func (l *LinkedList) PrintNodes() {
    node := l.Root
    for node.next != nil {
      fmt.Printf("%d -> ", node.val)
      node = node.next
    }
    fmt.Printf("%d\n", node.val)
  }

  func (l *LinkedList) PrintReverse() {
    node := l.Tail
    for node.prev != nil {
      fmt.Printf("%d -> ", node.val)
      node = node.prev
    }
    fmt.Printf("%d\n", node.val)
  }

수정 후에 main.go로 넘어가면 에러가 사라진 것을 알 수 있는데 여기에서도 소문자인 root,tail을 첫글자만 대문자로 바꾸어 줍니다.

 

main.go

package main

import (
    "fmt"

    "./dataStruct"
)

func main() {
    list := &dataStruct.LinkedList{}
    list.AddNode(0)

    for i := 1; i < 10; i++ {
        list.AddNode(i)
    }

    list.PrintNodes()

    list.RemoveNode(list.Root.next)

    list.PrintNodes()

    list.RemoveNode(list.Root)

    list.PrintNodes()

    list.RemoveNode(list.Tail)

    list.PrintNodes()
    fmt.Printf("Tail:%d\n", list.Tail.val)

    list.PrintReverse()

    a := []int{1, 2, 3, 4, 5}
    a = append(a[0:2], a[3:]...)
    fmt.Println(a)
}

수정한 뒤 실행시켜주면 다음과 같은 에러가 뜨는 것을 알 수 있는데

.\main.go:19:27: list.Root.next undefined (cannot refer to unexported field or method next)
.\main.go:30:35: list.Tail.val undefined (cannot refer to unexported field or method val)

이 부분도 마찬가지로 외부로 공개되지 않아 생긴 문제 입니다. 저 부분들도 바꾸어 줍시다.

dataStruct/likedList.go에서

type Node struct {
    next *Node
    prev *Node
    val  int
}

이 부분을 수정해주고, 이것과 관련되어 있는 것들도 수정해 줍니다.

package dataStruct

import "fmt"

type Node struct {
    Next *Node
    Prev *Node
    Val  int
}

type LinkedList struct {
    Root *Node
    Tail *Node
}

func (l *LinkedList) AddNode(Val int) {
    if l.Root == nil {
        l.Root = &Node{Val: Val}
        l.Tail = l.Root
        return
    }
    l.Tail.Next = &Node{Val: Val}
    Prev := l.Tail
    l.Tail = l.Tail.Next
    l.Tail.Prev = Prev
}

func (l *LinkedList) RemoveNode(node *Node) {
    if node == l.Root {
        l.Root = l.Root.Next
        l.Root.Prev = nil
        node.Next = nil
        return
    }

    Prev := node.Prev

    if node == l.Tail {
        Prev.Next = nil
        l.Tail.Prev = nil
        l.Tail = Prev
    } else {
        node.Prev = nil
        Prev.Next = Prev.Next.Next
        Prev.Next.Prev = Prev
    }
    node.Next = nil
}

func (l *LinkedList) PrintNodes() {
    node := l.Root
    for node.Next != nil {
        fmt.Printf("%d -> ", node.Val)
        node = node.Next
    }
    fmt.Printf("%d\n", node.Val)
}

func (l *LinkedList) PrintReverse() {
    node := l.Tail
    for node.Prev != nil {
        fmt.Printf("%d -> ", node.Val)
        node = node.Prev
    }
    fmt.Printf("%d\n", node.Val)
}

마찬가지로 main.go부분도 수정해 줍니다.

  package main

  import (
    "fmt"

    "./dataStruct"
  )

  func main() {
    list := &dataStruct.LinkedList{}
    list.AddNode(0)

    for i := 1; i < 10; i++ {
      list.AddNode(i)
    }

    list.PrintNodes()

    list.RemoveNode(list.Root.Next)

    list.PrintNodes()

    list.RemoveNode(list.Root)

    list.PrintNodes()

    list.RemoveNode(list.Tail)

    list.PrintNodes()
    fmt.Printf("Tail:%d\n", list.Tail.Val)

    list.PrintReverse()

    a := []int{1, 2, 3, 4, 5}
    a = append(a[0:2], a[3:]...)
    fmt.Println(a)
  }

이제 실행을 해봅시다.

 

 

기존에 했었던 부분과 똑같이 출력되는 것을 알 수 있습니다.

이제 다른 프로그램에서도 저 패키지를 쓸 수 있게 되었습니다. 이제부터 만드는 코드들은 저 패키지 안에 넣으며 진행할 것입니다.

---

이제 Stack과 Queue를 시작해 봅시다. 애네 둘은 구현도 비슷하고, 성격도 비슷하지만 동작은 서로 반대로 동작 합니다.
Stack은 보통 FILO(First In Last Out)으로 표현을 하고, Queue는 FIFO(First In First Out)으로 표현을 합니다.

그러니까 Stack은 제일 먼저 들어간 애가 제일 나중에 나온다는 것이고, Queue는 제일 먼저 들어간 애가 제일 먼저 나온다는 의미인데요.

 

Stack의 구조는 아래와 같은데

들어갈 때는 A-B-C 순서로 들어왔다면 나올 때는 C-B-A순으로 나옵니다.

그러면 Stack을 코드로 어떻게 만들어야 위와 같이 만들면 좋을까요?

FILO(First In Last Out)을 하려면 메모리에서 data를 넣을 때는 맨 처음부터 넣고, 꺼낼 때는 맨 마지막 부터 꺼내면 됩니다.

 

이제 Queue로 넘어가보죠. Queue는 대기열이라고 보면 됩니다.

 

실제 구조는 아래와 같은데

오른쪽에서 들어가서 왼쪽으로 나오기 때문에 들어올 때와 나올 때가 1-2-3-4-5 순으로 나오게 됩니다.

마찬가지로 Queue는 코드로 어떻게 만들어야 좋을까요? 배열이 있으면 넣는것은 뒤로 넣고, 뺄 때는 앞에서 빼면 됩니다.

 

Stack과 Queue를 비교해보면 Stack은 맨 뒤에서부터 넣고, 맨 뒤에서부터 뺴고, Queue는 맨 뒤에서부터 넣고, 맨 앞에서부터 뺍니다. 이러한 차이가 있죠.

이제부터 Stack과 Queue를 만들어보죠. 처음에는 Slice로 만들어 봅시다.

main.go

  package main

  import (
    "fmt"
  )

  func main() {
    stack := []int{}

    for i := 1; i <= 5; i++ {
      stack = append(stack, i)
    }

    for len(stack) > 0 {
      var last int
      last, stack = stack[len(stack)-1], stack[:len(stack)-1]
      fmt.Println(last)
    }
  }

먼저 stack부분부터 만들어 줄 것인데 Slice형태를 가진 stack이라는 변수를 만들어주고, stack에 append로 1 ~ 5까지 데이터를 추가시켜주고, 뺄 때는 맨 마지막부터 빼기 때문에 last와 stack이 바뀌게 됩니다.

last는 맨 마지막에 있는 것이기 때문에 stack의 길이 - 1 한 인덱스 값 이 마지막 값이 되고, stack은 처음부터 시작해서 맨 마지막 값 -1 한 것 까지 스택을 바꿔 줍니다. 이렇게 하면 last가 나오게 됩니다.

그래서 그것을 스택의 길이가 0보다 클 때까지 반복해주고, 맨 마지막 값을 출력시켜 줍니다.

출력이 5,4,3,2,1 순으로 됐고, 들어간 순서도 출력시켜주면

1,2,3,4,5가 들어간 것을 알 수 있습니다.

 

그 아래에 Queue를 만들어보죠.

  package main

  import (
    "fmt"
  )

  func main() {
    stack := []int{}

    for i := 1; i <= 5; i++ {
      stack = append(stack, i)
    }

    fmt.Println(stack)

    for len(stack) > 0 {
      var last int
      last, stack = stack[len(stack)-1], stack[:len(stack)-1]
      fmt.Println(last)
    }

    queue := []int{}
    for i := 1; i <= 5; i++ {
      queue = append(queue, i)
    }

    fmt.Println(queue)

    for len(queue) > 0 {
      var front int
      front, queue = queue[0], queue[1:]
      fmt.Println(front)
    }
  }

마찬가지로 queue 빈 slice로 만들어주고,  queue에 맨 뒤에서 부터 append해서 1 ~ 5까지 추가해 주었습니다. 이 상태를 출력시켜주고, stack과 마찬가지로 queue의 길이가 0보다 클 때 까지 출력을 시켜주는데 front는 맨 첫번째 것인 0번째가 되고, 맨 앞에서 뺐으니 1부터 잘라 줍니다.

그렇게 해서 front가 나오면 front를 출력시켜 줍니다.

 

이제 저장 후에 출력시켜보죠.

위에 것은 stack 밑에 것은 queue입니다. stack은 뺄 때 stack[len(stack)-1], stack[:len(stack)-1]로 해서 맨 뒤에 것 부터 빼주었고, Queue는 queue[0], queue[1:]를 사용하여 맨 앞에 것 부터 빼주었습니다.

 

이 Slice를 잘 봐야 하는데 저번에 설명했을 때 stack[시작포인트:엔드포인트]라고 했었고, 시작포인트 부터 시작해서

엔드를 포함하지 않고 끝낸다고 했었습니다.

그래서 stack[:len(stack)-1] 이렇게 썼으면 시작포인트가 생략되었기 때문에 0부터 시작해서 길이-1까지니까

1	2	3	4
0	1	2	3

이렇게 있다고 가정하면 길이는 4가 됩니다. (위에는 데이터 밑에는 인덱스) 그래서 4-1까지인 3까지인데 3을 포함하지 않게 되어 맨 뒤에 것이 없어지게 됩니다.

1	2	3
0	1	2

그 다음 것은 또 맨 뒤것이 없어지게 되고가 반복되는 식이 됩니다.

Queue는 맨 앞에 것인 queue[0]이 front에 대입되게 되고, 그 다음 queue[1:]를 사용하여 자르는데 뒤에 것이 생략되었기 때문에 1 부터 나머지 입니다.

1	2	3	4
0	1	2	3

이렇게 있다고 가정하면 시작 지점이 1부터 끝까지기 때문에 맨 앞에 있는 0번 값은 사라지게 됩니다.

2	3	4
0	1	2

그 다음에는 2가 인덱스 0을 가지는 첫번째 값이 되기 때문에 2가 사라지게 됩니다.

3	4
0	1

이것이 반복되는 것이 Queue 입니다.

그러면 Stack과 Queue를 위와 같은 배열로 만드는 것과 Linked List로 만들 때 어떤 차이가 있는지 알아보죠.

우선 Stack을 배열로 구현 했을 때를 보죠.

1

2

3

4

이렇게 배열안에 값이 있다고 했을 때 값을 추가하면 맨 뒤에 값이 추가됩니다. 그랬을 때 Capacity가 다 차게 되면 더 큰 배열을 만들고 그 값들 옮겨 담는다고 했었습니다.

그 때 속도는 O(N)이 필요 합니다. (이 때는 Queue도 마찬가지이죠.)

꺼낼 때는 Stack은 맨 뒤에서 부터 하나씩 꺼내기 때문에 Capacity는 그대로 있고, Length만 하나씩 줄어듭니다.

Length만 움직이게 되는 것이기 떄문에 배열을 옮길 필요가 없죠.

그렇기 때문에 꺼내는건 O(1)입니다.

Queue는 꺼낼 때 StartIndex가 하나씩 전진하며 꺼내기 때문에 O(1)이 됩니다.

여기까지 정리하자면 Queue와 Stack은 요소를 추가할 때는 O(1)이지만 Capacity가 다 떨어졌을 때는 O(N)이 되고, 요소를 꺼낼 때는 항상 O(1)이 됩니다.

---

이번에는 Stack과 Queue를 Linked List로 만들었을 때로 넘어가보죠.

Linked List는 넣을 때는 맨뒤로 넣으면 되는데 tail을 알고 있기 때문에 O(1) 입니다.

Stack에서 뺄 때는 그 요소를 빼고 링크만 끊으면 되기 때문에 O(1)입니다. Queue도 마찬가지 입니다.

정리하자면 Slice로 했을 때 데이터를 넣을때는 O(N), 뺄때는 O(1)이고, Linked List로 했을 때는 모두 O(1)입니다.

Linked List가 더 빠르지만 Slice로 해도 크게 무리는 없습니다.

데이터를 넣을때 O(N)이 발생하지만 간혹 간혹 발생하기 때문인데 이 말이 무슨말이냐면 배열이 처음에는 1개, 2개, 4개, 8개..... 로 늘어나서 배열의 크기가 나중에는 엄청 커다랗게 될텐데 배열이 이렇게 어느정도까지 성장할 때 까지는 시간이 걸리지만 한번 성장하고 난 다음에는 시간이 크게 걸리지 않습니다.

하지만 O(N)보다는 느리고 Linked List로 만들면 더 빠를 수 있다. 정도로만 알고 있으면 됩니다.

 

그리고 저번에도 말했듯이 배열하고 리스트는 메모리상의 구획이 틀립니다.

그래서 배열처럼 따닥따닥 붙어있는 상황에서 좋은점은 캐시미스가 덜 나기 때문에 반복문에서 더 빠르게 수행할 수 있다는 점이죠.

이런 차이만 있다. 정도로만 알고 있으면 됩니다. 그래서 Slice로 만드나, Linked List로 만드나 적은 요소에서는 커다란 차이가 없습니다.

 

이제는 Linked List로 이용해서 만들어보죠. 하기 앞서 dataStruct폴더에 stack.go를 추가해 줍니다.

package dataStruct

type Stack struct {
    ll *LinkedList
}

func NewStack() *Stack {
    return &Stack{ll: &LinkedList{}}
}

func (s *Stack) Push(val int) {
    s.ll.AddNode(val)
}

Stack이라는 struct를 추가해주고, LinkedList를 안에 넣어 줍니다.
그 아래에 Stack의 기능을 추가해주는데 먼저 Add 해주는 Push를 추가해 줍니다.
Push()안에 LinkedList.go의 AddNode()를 가져 옵니다.

그 다음에 NewStack()이라는 생성자를 하나 만들어 줍니다. 이 함수는 초기화 시켜주는 것인데 새로운 LinkedList를 하나 만들어서 그 주소를 넣어서 초기화해서 그것을 반환하는 함수입니다.

그 다음 꺼내오는 함수인 Pop()을 만들어주는데 LinkedList.go안에 Pop()에 쓸만한 함수가 없기 때문에 하나 추가해 줍니다.

dataStack/LinkedList.go

func (l *LinkedList) Back() int {
    if l.Tail != nil {
        return l.Tail.Val
    }
    return 0
}

맨 뒤에 값을 반환하는 Back()을 만들어준다. Tail이 nil이 아니면 Tail의 Val를 반환해주고, nil이면 0을 반환 시킵니다.

stack.go로 넘어와서 Pop()코드를 추가 시켜 줍니다.

package dataStruct

type Stack struct {
    ll *LinkedList
}

func NewStack() *Stack {
    return &Stack{ll: &LinkedList{}}
}

func (s *Stack) Push(val int) {
    s.ll.AddNode(val)
}

func (s *Stack) Pop() int {
    back := s.ll.Back()
}

back이라는 변수에 Back()함수를 넣어 저장시켜주고, 맨 뒤에 값을 지워야하기 때문에 LinkedList.go로 넘어와 PopBack()을 추가해 줍니다.

 

LinkedList.go

func (l *LinkedList) PopBack() {
    if l.Tail == nil {
        return
    }
    l.RemoveNode(l.Tail)
}

Tail이 없는 경우에는 지울 필요가 없기 때문에 있는 경우엔 그냥 넘어가고, Tail이 있는 경우엔 Tail을 지워 줍니다.

다시 이것을 stack.go로 넘어와서 Pop()안에 추가 시켜 줍니다.

package dataStruct

type Stack struct {
    ll *LinkedList
}

func NewStack() *Stack {
    return &Stack{ll: &LinkedList{}}
}

func (s *Stack) Push(val int) {
    s.ll.AddNode(val)
}

func (s *Stack) Pop() int {
    back := s.ll.Back()
    s.ll.PopBack()
    return back
}

PopBack() 써서 맨 뒤를 지운 다음에 back을 반환시켜 줍니다.

이렇게 하면 Stack이 만들어질 것입니다. 이제 main.go에서 사용해보죠.

package main

import (
    "fmt"

    "./dataStruct"
)

func main() {
    stack := []int{}

    for i := 1; i <= 5; i++ {
        stack = append(stack, i)
    }

    fmt.Println(stack)

    for len(stack) > 0 {
        var last int
        last, stack = stack[len(stack)-1], stack[:len(stack)-1]
        fmt.Println(last)
    }

    queue := []int{}
    for i := 1; i <= 5; i++ {
        queue = append(queue, i)
    }

    fmt.Println(queue)

    for len(queue) > 0 {
        var front int
        front, queue = queue[0], queue[1:]
        fmt.Println(front)
    }

    stack2 := dataStruct.NewStack()

    for i := 1; i <= 5; i++ {
        stack2.Push(i)
    }
}

Linked List형태의 Stack을 stack2로 지정 했습니다. NewStack()을 사용했기 때문에 새로운 Stack을 만들어서 그 메모리 주소를 반환하기 때문에 새로운 Stack이 stack2에 대입이 될 것입니다.

그 후 마찬가지로 1 ~ 5까지 stack2에다 Push를 해줍니다.

그리고 비었는지 확인하기 위해 stack.go와 dataStack/LinkedList.go 에 Empty()를 만들어 줍니다.

 

dataStack/LinkedList.go

func (l *LinkedList) Empty() bool {
    return l.Root == nil
}

Root가 없으면 Empty()가 True이고, 있으면 False입니다.

 

stack.go

func (s *Stack) Empty() bool {
    return s.ll.Empty()
}

마찬가지로 LinkedList.go의 Empty()를 사용하여 확인해 줍니다.

main.go로 돌아와 계속해서 작성해보죠.

package main

import (
    "fmt"

    "./dataStruct"
)

func main() {
    stack := []int{}

    for i := 1; i <= 5; i++ {
        stack = append(stack, i)
    }

    fmt.Println(stack)

    for len(stack) > 0 {
        var last int
        last, stack = stack[len(stack)-1], stack[:len(stack)-1]
        fmt.Println(last)
    }

    queue := []int{}
    for i := 1; i <= 5; i++ {
        queue = append(queue, i)
    }

    fmt.Println(queue)

    for len(queue) > 0 {
        var front int
        front, queue = queue[0], queue[1:]
        fmt.Println(front)
    }

    stack2 := dataStruct.NewStack()

    for i := 1; i <= 5; i++ {
        stack2.Push(i)
    }

    fmt.Println("newStack")

    for !stack2.Empty() {
        val := stack2.Pop()
        fmt.Printf("%d ->", val)
    }
}

stack2가 비어있지 않을 때까지 Pop()을 해서 출력시켜 줍니다.

그리고 그 위에 새로운 Stack이 시작된다고 알려 줍니다. 이렇게 해서 실행을 시켜보죠.

이 상태에서 실행을 시켜보면 에러가 납니다.

그래서 VS Code안에 디버그 버튼이 있는데 그것을 눌러보면

 

현재 함수가 호출된 상태가 나옵니다.

 

그래서 보게 되면

 

RemoveNode()를 하는데 에러가 난 것입니다.

그 원인을 보면 Root를 다음 것으로 갱신하는데 그 Root가 nil인 상태인 것입니다.

그러니까 아무것도 없는 것에 접근을 하니까 에러가 난 것이죠.

이것이 Access Violation이 난 것인데 이 부분을 고쳐주도록 하죠.

func (l *LinkedList) RemoveNode(node *Node) {
    if node == l.Root {
        l.Root = l.Root.Next
        if l.Root != nil { // 바뀐 부분
            l.Root.Prev = nil
        }
        node.Next = nil
        return
    }

    Prev := node.Prev

    if node == l.Tail {
        Prev.Next = nil
        l.Tail.Prev = nil
        l.Tail = Prev
    } else {
        node.Prev = nil
        Prev.Next = Prev.Next.Next
        Prev.Next.Prev = Prev
    }
    node.Next = nil
}

위와 같이 Root가 nil이 아닌 경우에면 바꾸어 주도록 합니다.

 

그 후 다시 실행을 시켜보죠.

이제 에러 없이 잘 동작하는 것을 알 수 있습니다.

 

이제 Queue도 만들어보자 마찬가지로 dataStruct패키지안에 queue.go를 추가해 줍니다.

package dataStruct

type Queue struct {
    ll *LinkedList
}

func NewQueue() *Queue {
    return &Queue{ll:&LinkedList{}}
}

func (q *Queue) Push(val int) {
    q.ll.AddNode(val)
}

마찬가지로 생성함수인 NewQueue()를 만들어 줍니다.

그리고 데이터를 넣어주는 Push()을 만들어 줍니다.

데이터를 빼오는 Pop()을 만들어주어야 하는데 앞에서부터 빼오기 때문에 linkedList.go에서 Front()를 만들어 줍니다.

 

dataStruct/linkedList

func (l *LinkedList) Front() int {
    if l.Root != nil {
        return l.Root.Val
    }
    return 0
}

Root가 nil이 아니면 Root의 값을 반환하고, nil이면 0을 반환하도록 만들어 줍니다.

다시 dataStruct/queue.go로 넘어와서

func (q *Queue) Pop() int {
    front := q.ll.Front()
    q.ll.PopFront()
    return front
}

queue에서 Front()을 하면 front값을 저장해놓고, 맨 앞에서 하나 지워줘야 하기 때문에 dataStruct/linkedList.go에서 PopFront()를 만들어 줍니다.

 

dataStruct/linkedList.go

func (l *LinkedList) PopFront() {
    if l.Root == nil {
        return
    }
    l.RemoveNode(l.Root)
}

PopFront()는 Root를 없애는 것이니까 Root가 없으면 그냥 반환해주고, Root가 있으면 지워주도록 하죠.

다시 dataStruct/queue.go로 넘어와서 비었는지 확인하는 Empty()를 만들어 줍니다.

package dataStruct

type Queue struct {
    ll *LinkedList
}

func NewQueue() *Queue {
    return &Queue{ll: &LinkedList{}}
}

func (q *Queue) Push(val int) {
    q.ll.AddNode(val)
}

func (q *Queue) Pop() int {
    front := q.ll.Front()
    q.ll.PopFront()
    return front
}

func (q *Queue) Empty() bool {
    return q.ll.Empty()
}

이제 main에 넘어와서 queue.go를 이용해서 만들어보죠.

package main

import (
    "fmt"

    "./dataStruct"
)

func main() {
    stack := []int{}

    for i := 1; i <= 5; i++ {
        stack = append(stack, i)
    }

    fmt.Println(stack)

    for len(stack) > 0 {
        var last int
        last, stack = stack[len(stack)-1], stack[:len(stack)-1]
        fmt.Println(last)
    }

    queue := []int{}
    for i := 1; i <= 5; i++ {
        queue = append(queue, i)
    }

    fmt.Println(queue)

    for len(queue) > 0 {
        var front int
        front, queue = queue[0], queue[1:]
        fmt.Println(front)
    }

    stack2 := dataStruct.NewStack()

    for i := 1; i <= 5; i++ {
        stack2.Push(i)
    }

    fmt.Println("newStack")

    for !stack2.Empty() {
        val := stack2.Pop()
        fmt.Printf("%d ->", val)
    }

    queue2 := dataStruct.NewQueue()

    for i := 1; i <= 5; i++ {
        queue2.Push(i)
    }

    fmt.Println("newQueue")

    for !queue2.Empty() {
        val := queue2.Pop()
        fmt.Printf("%d ->", val)
    }

}

queue2 := dataStruct.NewQueue()에서 마찬가지로 새로운 queue로 초기화 시켜주고, 아까 stack2 했던 부분을 그대로 복사하여 stack2부분을 queue2로 바꾸어 줍니다.

이제 실행 시켜준 뒤 출력을 확인해보죠.

정상적으로 출력되는 것을 확인할 수 있습니다.

---

여기까지 Slice, Linked List로 Stack과 Queue를 만들었습니다.

이것을 어디에 사용하는지 알아보죠. 우선 Stack의 경우 예시 코드를 살펴보면

{
    int a 
        for ... {
            int b
        }
}

이라 할 때 나중에 선언된 b가 먼저 없어지게 된다. 이 경우 a를 만들고, b를 만들었고, 없어지는 순서는 b가 없어지고 그 다음에 a가 사라집니다.

들어간 순서와 반대로 없어지게 되는데 Stack으로 만들면 처음에 a가 만들어지고, 그 다음에 b가 만들어지기 때문에 b가 먼저 없어지고, 그 다음에 a가 없어지는데 이 처럼 맨 마지막에 넣는 것이 맨 처음으로 빼고 싶을 때 Stack을 사용 합니다.

 

Queue는 대기열 입니다. 어떤 줄을 세우고 싶을 때 Queue를 사용합니다.
예를 들면 어떤 번호를 뽑았는데 뽑은 번호 순서대로 실행시키고 싶을 때 Queue를 쓰고, 대기를 시켜 줄을 세워서 그 순서대로 하고 싶을 때도 Queue를 쓰고, LOL 같은 경우에도 게임시작 버튼을 눌러서 매칭할 때도 먼저 누른 사람 순서대로 잡아주는데 그 때도 Queue를 씁니다.

풀소스

---

LinkedList.go

package dataStruct

import "fmt"

type Node struct {
	Next *Node
	Prev *Node
	Val  int
}

type LinkedList struct {
	Root *Node
	Tail *Node
}

func (l *LinkedList) AddNode(Val int) {
	if l.Root == nil {
		l.Root = &Node{Val: Val}
		l.Tail = l.Root
		return
	}
	l.Tail.Next = &Node{Val: Val}
	Prev := l.Tail
	l.Tail = l.Tail.Next
	l.Tail.Prev = Prev
}

func (l *LinkedList) Back() int {
	if l.Tail != nil {
		return l.Tail.Val
	}
	return 0
}

func (l *LinkedList) Front() int {
	if l.Root != nil {
		return l.Root.Val
	}
	return 0
}

func (l *LinkedList) Empty() bool {
	return l.Root == nil
}

func (l *LinkedList) PopBack() {
	if l.Tail == nil {
		return
	}
	l.RemoveNode(l.Tail)
}

func (l *LinkedList) PopFront() {
	if l.Root == nil {
		return
	}
	l.RemoveNode(l.Root)
}

func (l *LinkedList) RemoveNode(node *Node) {
	if node == l.Root {
		l.Root = l.Root.Next
		if l.Root != nil {
			l.Root.Prev = nil
		}
		node.Next = nil
		return
	}

	Prev := node.Prev

	if node == l.Tail {
		Prev.Next = nil
		l.Tail.Prev = nil
		l.Tail = Prev
	} else {
		node.Prev = nil
		Prev.Next = Prev.Next.Next
		Prev.Next.Prev = Prev
	}
	node.Next = nil
}

func (l *LinkedList) PrintNodes() {
	node := l.Root
	for node.Next != nil {
		fmt.Printf("%d -> ", node.Val)
		node = node.Next
	}
	fmt.Printf("%d\n", node.Val)
}

func (l *LinkedList) PrintReverse() {
	node := l.Tail
	for node.Prev != nil {
		fmt.Printf("%d -> ", node.Val)
		node = node.Prev
	}
	fmt.Printf("%d\n", node.Val)
}

 

Queue.go

package dataStruct

type Queue struct {
	ll *LinkedList
}

func NewQueue() *Queue {
	return &Queue{ll: &LinkedList{}}
}

func (q *Queue) Push(val int) {
	q.ll.AddNode(val)
}

func (q *Queue) Pop() int {
	front := q.ll.Front()
	q.ll.PopFront()
	return front
}

func (q *Queue) Empty() bool {
	return q.ll.Empty()
}

 

Stack.go

package dataStruct

type Stack struct {
	ll *LinkedList
}

func NewStack() *Stack {
	return &Stack{ll: &LinkedList{}}
}

func (s *Stack) Empty() bool {
	return s.ll.Empty()
}

func (s *Stack) Push(val int) {
	s.ll.AddNode(val)
}

func (s *Stack) Pop() int {
	back := s.ll.Back()
	s.ll.PopBack()
	return back
}