[자료구조 | 기초] Stack & Queue

Stack

Stack 이란?

• Stack 은 LIFO 원칙에 기반한 선형 자료 구조입니다.

Stack의 주요 연산

• Push
• Pop
• Top / Peek
• IsEmpty

Stack의 사용 사례

• Undo / Reso 
• 백스페이스 
• 최근 작업 순서로 되돌아가기
• 프로그램의 함수 호출을 관리 (Call Stack)
• 그 외
  • 문자열 역순으로 바꾸기, 괄호의 짝 확인하기, 후위 표기법 변환하기 등에 활용

장점

1. 상수 시간의 기본 연산 O(1)
2. 메모리 효율성
3. [...]

 

Stack Overflow / Underflow

Stack Overflow

• 스택이 할당된 메모리 용량을 초과하여 아이템을 추가하려고 할 때 발생하는 현상
• 스택이 가득 찼는데 더 많은 데이터를 푸시하려고 시도하면 발생

Stack Underflow

• 스택이 비어 있을 때 아이템을 제거하려고 할 때 발생하는 현상
•  스택에서 아무것도 없는 상태에서 팝 연산을 수행하려고 시도하면 스택 언더플로우가 발생

Stack Overflow / Underflow 가 발생하면 시스템에 어떤영향을 미치나요?

• backend application에서 client의 요청을 처리하는 과정에서 stack overflow / underflow가 발생한다면 여러가지 문재가 발생할 수 있습니다.스프링 부트 애플리케이션은 내부적으로 여러 스레드를 사용하여 작업을 처리합니다. 특히 웹 어플리케이션의 경우 http 요청을 처리하기위한 워커 스레드, 데이터베이스 연결을 관리하는 스레드, 스케줄링 된 작업을 실행하는 스레드 등 다양한 스레드가 있습니다.이때 stack overflow는 스레드별로 할당된 스택 메모리 영영에서 발생하는데, 주로 재귀 함수 호출이 너무 깊게 들어가거나, 스택 프레임의 크기가 너무 커져서 스택 메모리의 한계를 초과 할 때 발생합니다.

스프링 부트 애플리케이션에서 메인 스레드에서 stack overflow가 발생

• 애플리케이션의 초기화나 빈 생성 과정에서 재귀적 호출이 발생할 경우, 메인 스레드에서 stack overflow 가 발생 할 수 있는데, 메인 스레드에서 에러가 발생하면, 애플리케이션 전체가 시작되지 않거나 중간에 중단될 수 있습니다.그러나 이러한 경우들은 흔하지 않으며, 대부분의 stack overflow는 웹 요청 처리나 비즈니스 로직 수행중에 발생하는 경우가 많습니다.

 

스프링 부트 애플리케이션에서 메인스레드에서 stack overflow가 발생

• 웹 요청 처리나 비즈니스 로직 수행 중에 발생하는 경우, 해당 쓰레드만 종료되고, 다른 스레드는 영향을 받지 않습니다.

 

Overflow / Underflow를 방지하기 위해 어떤 방법들이 있을까요?

• 재귀함수 제한
  • 재귀 함수의 깊이를 제한하거나 반복문을 사용하여 반복접인 작업을 수행하도록 코드를 재작성
• 예외처리
  • 스택 오버플로우나 언더플로우가 발생할 가능성이 있는 코드 부분에서는 예외처리를 통해 해당 오류가 발생했을때 적절한 대응을 할 수 있도록 합니다.

 

[...]

 

Queue

Queue란?

• Queue는 FIFO원칙에 방식의 자료 구조입니다.

Queue의 주요 연산

• Enqueue
• Dequeue
• Peek
• isEmpth

Queue의 사용 사례

• 프린터 대기열
• Breadth-First Search
• 주문처리 시스템
• Data Streaming
• Load Balancing
• Messaging

Queue의 종류와 특징

• 선형 큐
• 순환 큐
  • 배열을 기반으로 하는데, 배열의 마지막 요소 다음에는 배열의 첫번째 요소가 옵니다.
• 우선순위 큐
  • 각 항목이 우선순위 함께 저자오디는 큐입니다.
  • 큐에서 요소를 꺼낼 때 가장 높은 우선순의 요소가 먼저 나옵니다.
  • 힙 같은 특별한 자료구조를 사용하여 구현 될 수 있습니다.
  • ex) 응급실의 환자 대기열, OS 프로세스 스케쥴링
• 덱