Stack, Queue

Stack

Stack 과정

• 데이터를 일시적으로 저장하기 위해 사용되는 자료구조로, 데이터의 삽입과 삭제가 한쪽 끝에서만 일어나는 선형 자료구조이다.
• 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되는 후입선출(Last-In-First-Out, LIFO)의 구조를 가지고 있다.
• 스택은 배열이나 연결 리스트로 구현할 수 있다.
• 스택은 일상 생활에서 쉽게 떠올릴 수 있는 예시로, 책을 쌓아놓는 책상이나, 접시를 쌓아놓는 상태에서 가장 위의 접시를 사용하는 것과 같은 구조를 가지고 있다.

Stack의 활용

• 스택은 주로 함수 호출, 괄호 검사, 수식 계산 등에서 사용
• 수식 계산시 후위 표기법을 이용하여 수식을 스택에 쌓아 계산 가능

Stack의 연산

• 데이터 삽입 - push
• 데이터 삭제 - pop
• 데이터 반환 - top

Stack의 장단점

장점

• 구현이 간단하고, 메모리를 효율적으로 사용할 수 있다.
• 접근 시간이 매우 빠르며, O(1)의 시간 복잡도를 갖는다.
• 재귀 알고리즘 등에 활용할 수 있다.
• 함수의 호출 스택, 웹 브라우저 방문 기록 등 다양한 분야에서 활용된다.

단점

• 크기가 고정되어 있지 않아서 동적으로 메모리를 할당하는 경우에는 메모리를 할당해제하는 과정이 빈번해질 수 있어 비효율적이다.
• 배열로 구현할 경우, 삽입/삭제 연산이 맨 앞에 위치할 때, 모든 원소의 위치를 옮겨줘야 하는 단점이 있다.
  • 이 경우, O(n)의 시간 복잡도를 가지게 되는데, 이를 해결하기 위해 링크드 리스트로 구현할 수 있다.
• 후입선출(LIFO)의 특성 때문에, 선입선출(FIFO)이나 우선순위 큐와 같은 다른 자료구조와는 다르게, 특정 문제를 해결하기 어려울 수 있다.

Queue

• 선입선출(FIFO: First-In, First-Out) 원칙을 따르는 자료구조로, 데이터가 들어오는 순서대로 저장되고 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조를 가지고 있다.

Queue의 연산

• 데이터 삽입 - Enqueue
• 데이터 삭제 - Dequeue
• 일상생활에서 대기줄을 예로 들 수 있다. 먼저 대기열에 들어온 사람이 먼저 서비스를 받고 나가는 것과 같다.
• 큐는 가장 먼저 들어온 데이터를 먼저 처리해야 하는 경우, 예를 들어 작업 큐에서 작업 처리 순서를 정할 때, 유용하게 사용된다. 또한, 네트워크 트래픽이나 메시지 큐 등에서도 사용된다.

Queue의 종류(일반, 데크, 동기화)

일반 Queue

• 가장 일반적으로 선입 선출 구조를 가지는 큐
• 구현이 간단하고 특별한 제약이 없는 경우에 사용하기 적합

데크

• Double Ended Queue의 약자
• 양쪽 끝에서 삽입과 삭제가 가능한 자료구조
• 큐와 스택의 속성을 모두 가지고 있기 때문에 큐와 스택이 모두 필요한 경우에 사용

동기화 Queue

• 여러 개의 스레드에서 큐를 공유할 때 사용
• 동시성 문제를 해결하기 위한 동기화 기능이 추가된 큐
• 성능 저하 문제가 발생할 수 있으므로 가능한 비동기적으로 큐를 처리하는 것이 좋음

원형 Queue

• 배열의 처음과 끝이 연결되어 원형 구조를 가진 큐.
• 선형 큐의 문제점을 해결하기 위해 고안 됨
• 배열에서 큐의 삭제 과정을 보면 앞의 데이터가 삭제되고 출구 데이터는 그 다음 인덱스를 가리키게 된다. 이 경우 앞에 삭제된 인덱스의 데이터 공간은 낭비되는 현상이 발생된다. 원형큐를 사용하면 앞에 낭비되는 데이터 공간을 효율적으로 사용할 수 있게된다.
• 원형 큐의 장점은 다음과 같다.
  • 큐의 공간을 최대한 활용할 수 있다.
  • 선형 큐의 문제점을 해결할 수 있다.
• 원형 큐의 단점은 다음과 같다.
  • 원형 큐는 크기가 고정되어 있다. 만약 큐의 크기를 동적으로 변경하려면 새로운 큐를 만들어야 한다.
  • 배열의 처음과 끝이 연결되어 있기 때문에, 배열의 끝에서 다음 원소로 이동하는 작업이 더 복잡하다.

Queue의 장단점

장점

• 선입선출 원칙에 따라 데이터 처리가 공정하고, 데이터 누락이나 중복 없이 처리됨
• 구현이 간단하고, 데이터 삽입 및 삭제 시간 복잡도가 O(1)이므로 빠른 처리가 가능
• 우선순위 큐를 이용하면 정렬된 데이터 처리가 용이

단점

• 큐에 저장된 모든 데이터를 순회하면서 특정 데이터를 찾아내는 것은 비효율적
• 큐에 데이터가 쌓이면 메모리 사용량이 늘어나는 단점이 있음
• 우선순위 큐를 이용할 때는 구현 방식에 따라 힙 구조를 이용하는 등 추가적인 구현이 필요할 수 있음

Stack과 Queue의 활용 사례

Stack

• 함수 호출 스택
  • 함수가 호출될 때마다 해당 함수의 정보를 스택에 저장하고, 함수가 종료될 때마다 스택에서 해당 함수 정보를 꺼내는 방식으로 동작한다.
• 괄호 매칭 문제
  • 문자열에서 여는 괄호를 스택에 넣고 닫는 괄호가 나오면 스택에서 pop하여 스택에서 나온 괄호와 닫는 괄호가 매칭이 되는지 확인하여 유효성 검사를 한다.

Queue

• 프로세스 스케줄링
  • CPU를 사용하기 위해 대기하는 프로세스는 큐에 저장되며, 우선 순위에 따라 처리 순서가 결정된다.
• 버퍼링, 캐시구현
  • 데이터의 연산 및 저장을 할 때 버퍼에 데이터를 저장하고 버퍼에 들어온 task 순서대로 처리를 진행한다.
• 너비 우선 탐색
  • 너비 우선 탐색은 그래프 탐색 알고리즘 중 하나로, 시작점에서 거리가 가까운 정점부터 우선적으로 방문하는 알고리즘이다. 이때 방문한 정점을 큐에 저장하고 해당 정점과 인접한 정점을 큐에 넣어 지속적으로 탐색을 진행하는데, 이때 큐 자료구조가 사용된다.

---

출처

[자료구조][Javascript] Stack 이란?. 스택이란? Stack : 자료의 입출력이 한 방향에서만 이루어지는… | by Jae-young Song | Medium

열혈 자료구조(윤성우)

이것이 취업을 위한 코딩 테스트다 with 파이썬(나동빈)