자료구조

Stack과 Queue

becomeweasel 2022. 9. 18. 16:24

Stack

선형자료구조의 일종으로 LIFO의 특성을 가지고 있다. 가장 처음 들어간 원소가 가장 나중에 접근 가능 하고, 다시 말해서 호출 시에 가장 최근의 원소에 접근 할 수 있다. O(n)의 공간복잡도를 가진다.

링크드 리스트를 이용한 구현과 배열을 이용한(정확히는 Dynamic Array) 두가지 버전이 있다. 링크드 리스트는 일관적인 시간복잡도 O(1)를 보여주는 대신에 추가적인 메모리 사용량(Node 구조를 유지하는데 드는)과 메모리 할당에 추가적인 비용이 들 수 있다.

  • 조회 : Top에 있는 원소를 조회할때는 O(1), 하지만 특정한 데이터를 찾고자 할때는 O(n)이다.
  • 삽입 : 링크드 리스트를 이용한 구현에서는 단순히 기존의 Top 원소를 새 원소의 next 로 연결시켜주고 head 의 포인터에 새로운 원소를 연결시켜주면 되기 때문에 O(1)이다.
    배열을 이용한 구현에서도 특정 상황(Dynamic array의 팽창)을 제외하고는 O(1)이니 amoritezd\ O(1)이다.
  • 삭제 : 링크드 리스트와 배열 모두 O(1)이다.

활용

  • Stack Usage : JVM stack, 컴파일러에서 문법 체크(matching parentheses)

💡 프로그램의 함수 호출과 실행 순서는 아래와 같으니

스택프레임에 지역변수,매개변수,복귀주소등의 정보를 저장하고

함수의 실행이 끝나면 stack frame의 top을 pop한 후 복귀 주소로 복귀한다
가장 마지막에 호출된 함수를 가장 먼저 처리하고 복귀하는 후입선출의 구조를 처리하기 위해서 스택을 이용해서 관리한다.

Queue

선형자료구조로 FIFO의 특성을 가지고 있다. 먼저 들어간 원소가 가장 먼저 나오는 구조를 가지고 있다. O(n)의 공간복잡도를 가진다.

배열을 이용해 구현할때는 단순 배열보다 원형 구조 (circular queue)를 이용해서 구현한다. 혹은 링크드 리스트를 이용해서 구현할수 도 있는데 이때는 head 와 tail 에 대한 정보를 기록해야 한다.

  • 조회 : 가장 끝에 있는 원소를 조회할때는 O(1).
  • 삽입 : 링크드 리스트를 이용한 구현해서는 O(1). 동적 배열을 이용할때는 amoritezd\ O(1)이다. 원형 배열을 이용할때는 O(1).
  • 삭제 : 모두 O(1).

스택과 큐 모두 배열을 이용하거나 링크드 리스트를 이용해 구현가능한데, 배열을 사용하는 경우에는 Dynamic array의 팽창을 고려해야하기 때문에 최악의 경우에는 느리지만, 전반적인 성능이 좋다. 반대로 링크드 리스트를 이용한 구현에서는 일관된 성능(O(1))을 보여주지만, 메모리 할당에 들어가는 추가적인 비용 때문에 런타임 성능이 낮을 수 있다.

활용

  • Queue Usage : 스케쥴링,키보드 버퍼 → 두 개 모두 데이터 혹은 요청이 입력된 시간 순서대로 처리해야할 필요가 있을 경우에 사용한다.

문제들

  • 두 개의 스택으로 큐를 구현하기
    1. in 에 A,B,C를 차례로 push. 그러면 in 에는 [A,B,C] 의 순서대로 데이터가 쌓일 것이다.
    2. 그 후 in 의 데이터를 각각 pop하면 C,B,A의 순서대로 나올것이다. 그 후 out 으로 push해보자. out : [C,B,A]
    3. 이후 out 의 원소들을 순서대로 pop하면 출력은 A,B,C가 나오고 out: []
  • 생각보다 엄청 간단하다. 두 개의 스택을 각각 in과 out으로 구분하고, A,B,C 세개의 데이터가 입력으로 주어진다고 해보자. 출력은 A,B,C가 나와야 한다.
  • 스택에서 min을 O(1)에 작동하도록 하기삽입
    1. 만약 스택이 비어있다면 x 를 삽입할때, minEle=x 로 할당한다.
    2. 그렇지 않다면, x 와 minEle 의 대소를 비교해야하는데 두가지 경우가 존재한다.
      1. x가 minEle 보다 크거나 같다면, 그냥 삽입한다.
      2. minEle 보다 작다면, 2x-minEle 를 스택에 삽입하고, minEle 를 x 로 초기화해준다.
      삭제
    3. y 가 min 보다 크거나 같으면, y 를 그냥 삭제한다. 여전히 최소값은 minEle 다. 그리고 그 값은 스택이 아닌 minELe 에 있다고 보는것이 맞다.
    4. y 가 minEle 보다 작을 경우에, minEle 를 2*minEle-y 로 변경해준다.minEle 보다 작은 원소가 삽입될때 우리는 2x-minEle 를 삽입하는데, 언제나 그것은 x 보다는 작다는 것이다.
    5. 원리
  • 일단 최소 요소를 기록하는 minEle 변수를 stack 내부에 구현한다. 그 후 아래와 같은 사고방식대로 접근한다.