CS/💾 자료구조

스택(stack)과 큐(Queue)

늦은산책 2023. 5. 25. 11:10

스택(Stack)

스택의 특징

  • LIFO(후입선출)의 자료구조이다.
  • pop() 을 통해 데이터를 빼고
  • push()를 통해 데이터를 넣는다.
  • 활용 예시로는 후위표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문 기록, 깊이 우선 탐색(DFS) 가있다
  • 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출형식으로 데이터를 저장한다
  • 데이터를 넣고 빼는데는 O(1)의 시간 복잡도가 필요하다.
  • 재귀적인 특징이 있다

큐(Queue)

큐의 특징

  • FIFO(선입선출)의 자료구조이다
  • enqueue와 dequeue로 구성되어있다. 
  • 활용예시로는 프린터, CPU task scheduling, Cache 구현, 프로세스 관리, 너비우선 탐색(BFS) 등이 있다.
  • 구현 방식에는 두가지가 있다.
    1. Array - Based queue
      • 배열을 이용한 queue로 en과 de를 하는 과정에 메모리의 낭비가 생긴다 그것을 보안하기 위해 Circular queue라는 방식을 이용하는데 이를 작동하는 방식은 데이터가 나가면서 생긴 빈 공간을 다음으로 들어오는 데이터가 차지하면서 마치 빙빙 돈다는 이미지를 그리면 편하다. 만약 en이 너무 많아 배열의 빈공간이 없다면 Dynamic array처럼 resize를 해주어야한다. 그리고 그곳에 데이터를 옮기고 다시 진행하는데 이는 시간복잡도가 증가하는 단점이 있다 하지만 amortized O(1) 이라고 할수있다.
    2. Linked - Base queue
      • 말 그대로 Linked List를 이용한 queue이다 딱히 공간의 제약을 받고 있지 않기때문에 Array-Base의 단점이 사라지고 시간복잡도 또한 그저 데이터를 넣고 빼는 수준에는 O(1)을 유지한다.
    3. 둘의 차이점은 Array-Base는 Perfomance는 좋지만, worst-case의 경우에는 훨씬 더 느리고 List-Base의 경우에는 enqueue를 할때마다 메모리를 할당해주어야 하기때문에 상대적으로 느릴수 있다.
  • 큐를 확장한 방식에는 우선순위 큐(Priority queue)와 deque(double ended queue)가 있다.
    • dequeue는 들어오고 나가는 방향이 정해져있는것을 타파하기 위해 만들어진 자료구조이다. 즉 양쪽 모두 들어오고 나갈수있다는 뜻이다.
    • 우선순위 큐(priority queue)는 데이터를 뺄때 시간순서로 들어온 것이 아닌 우리가 원하는 우선순위를 정해두어 그것을 가장 먼저 뽑을수 있게 하는것이다. 이를테면 최대수와 최솟수를 예로 들수 있다.

 

우선순위 큐(priority queue) 와 Heap 

갑자기 왠 힙이냐 할 수 있겠지만 우선순위 큐를 배우면서 힙은 땔수없는 관계이기 때문이다

우선 위에서 말한 우선순위 큐와 큐의 차이점 부터 알아보자

1. 위에서 말한대로 시간 순서가 아닌 우선순위를 다룬다는것이다.

2. 시간 복잡도가 push O(logn), pop(logn) 이다

 

자 위에 말이 좀 이상하다 우선순위를 다룬다? 갑자기 시간 복잡도가 logn이 된다? logn은 대부분 트리 형태를 가진 자료구조에서 많이 나타난다. 심지어 그 자료구조 형태를 힙이 나타내고 있는데 힙은 완전 이진트리를 가지고 있으며 이는 우선순위 큐가 이용하기 너무 좋은 상황이다 즉, 우선순위 큐를 만들겠다! 라고 생각하는것은 힙을 구현하겠다! 하고 같은말이다.

 

이를 통해 최대와 최소를 우선순위로 잡는 방법이 눈에 보일수 있는데

  • 각 node에 저장된 값은 child node들에 저장된 값보다 크거나 같다 = 최대힙
    • root node에 저장된 값이 가장 크다
  • 각 node에 저장된 값은 child node들에 저장된 값보다 작거나 같다 = 최소힙
    • root node에 저장된 값이 가장 작다

 

트리는 보통 Linked List로 구현이 된다 하지만 Heap은 특이하게도 tree구조를 가지고 있으면서 array를 기반으로 구현해야 한다. 그이유는 새로운 node를 Heap의 마지막 위치에 추가해야하는데 이때 array기반으로 구현해야 이 과정이 수월해진다. Linked list의 경우에는 마지막의 위치가 너무 애매하다  

 

이제 push() 와 pop() 을 설명할텐데 ArrayList 로 구현한 가장 큰 이유가 여기서 나온다

최대힙을 예로 들어 설명해보겠다 최소힙은 이것의 반대니깐

  • 추가하기( push() )
    • 노드들은 각각 완전 이진 트리형태를 갖춰있고 거기에 마지막 노드에 추가된다.
    • 그렇다면 그 노드는 자신의 부모의 노드와 비교할테고 더 크다면 위로 올라갈텐고 아니라면 멈출것이다.
  • 빼기 ( pop() )
    • 우리가 원하는 노드는 가장 위에(root node)에 있을것이다. 그럼 가장 위가 빠지면서 그 빈 공간을 가장 마지막에 있는 노드가 들어간다. 그럼 거기서 또 비교가 시작되며 자리를 다시 잡는다.
  • 여기서 ArrayList의 장점이 나오는데 '부모와 자식의 비교' 이게 말이 쉽지 코드로 생각해보면 규칙을 찾아야 하는 일이다. 그럼 어떤 규칙이 있을까? 배열로 보자 나란히 index를 기준으로 서있는 배열을 기준으로 생각했을때 
    • 부모는 자식의 노드에 2를 나눈위치에 서있을것이다 = parent node = child node / 2
    • 왼쪽 자식은 부모의 두배 인덱스에 서있을것이다 = left child node = parent node * 2
    • 오른쪽 자식은 부모의 두배 인덱스에서 한칸더 간 자식일 것이다. = right child node = parent node * 2 + 1
  • 이러한 규칙이 생기는데 이것을 Linked List로 구현하기는 굉장히 어려워보인다 그래서 ArrayList를 사용하는것이다.
  • 이처럼 우선순위큐는 힙을 이용한 구현을 하게 되고 이렇게 사용된다.