[Algorithm] 스택/큐?

이번에는 스택과 큐에 대해 알아보도록 하겠습니다.

스택/큐

 

스택/큐

 

스택과 큐는 메모리 안에 데이터들을 효율적으로 관리하게 도와주는 처리 방식입니다. 

 

 

스택

스택은 한국말로 쌓아 올리다라는 말로 스택이라는 자료 구조 안에 데이터를 쌓아올리는 방식입니다. LIFO(Last In First Out)방식으로 처음 들어온 데이터가 맨 마지막에 나가는 구조입니다. 대표적으로 스택을 구현하는 방법은 정적인 1차원 배열로 하는 방식과 동적인 리스트를 이용한 배열이 있습니다.

 

정적인 1차원 배열로 구현하면 구현하기는 쉬우나 input size를 미리 알아야한다는 단점이 존재하고 동적인 리스트를 이용한 배열로 구현하면 정적인 1차원 배열에 비해 구현하기 어렵지만 input size에 제한이 없다는 장점이 있습니다.

 

스택 주요 기능

• pop: 스택에서 데이터를 빼내는 기능
• push: 스택에서 데이터를 삽입하는 기능 

 

스택에서 맨 위에 있는 데이터를 top, peek 혹은 head라고 말합니다. 스택의 특성 상 맨 마지막에 들어온 데이터를 추적할 필요가 있기 때문에 맨 위 데이터를 알고 있을 필요가 있습니다. 

스택 시간복잡도

삭제나 삽입시 맨 위에 데이터를 삽입하거나 삭제하기 때문에 시간복잡도는 O(1) 을 가지지만 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하므로 O(n) 의 시간 복잡도를 가집니다.

 

스택 활용 사례

• 실행취소
• 웹브라우저 뒤로가기
• 계산기

등에 사용되고 컴퓨터의 사칙연산에서 사람은 눈으로 사칙연산의 우선순위를 판단하여 계산하지만 컴퓨터는 스택을 이용하여 계산합니다. 이때 후위표기법이 사용되는데 관련 내용은 추후 다루도록 하겠습니다.

---

큐

큐는 스택과 반대로 가장 먼저 들어온 데이터가 가장 먼저 나가는  FIFO(First Input First Out)방식의 자료 구조입니다. 그렇기 때문에 한쪽 끝에서는 데이터의 삽입 연산만, 다른 한쪽 끝에서는 삭제 연산만 수행하게 됩니다. 보통 삽입과 관련된 변수를 rear, 삭제 관련된 변수를 front라고 합니다.

 

큐를 구현하는 방법은 정적인 array로 구현하는 방법과 동적인 array로 구현하는 방법이 있습니다. 정적인 array는 구현하기 쉽지만 고정된 큐 사이즈로 인해 지정된 사이즈보다 넘으면 에러가 발생하고 동적인 array는 유동적으로 큐 사이즈를 조절할 수 있으나 정적인 array보다 구현하기 어렵다는 단점이 있습니다. 리스트로 구현하는 것도 가능하지만 효율적이지 않습니다. 리스트 끝에 원소를 삽입하거나 끝에서 삭제하는 작업은 빠르지만 맨 처음에 원소를 삽입하거나 삭제하는 것은 다른 원소들을 모두 한 칸씩 이동시켜야되기 때문에 느리다는 단점이 있습니다. 이때는 스택과 큐를 합친 자료구조인 deque를 사용하여 구현할 수 있습니다.

 

큐 주요 기능

• Enqueue: 큐에서 값을 집어 넣는 함수
• Dequeue: 큐에서 값을 뽑는 함수
• Empty: 큐가 비어있는지 확인  
  
  • front 포인터와 rear 포인터가 같은 장소를 가리키면 즉, 같은 값이면 Empty 상태라고 함. 

큐 시간복잡도

삭제 연산의 복잡도는 O(1)로 항상 일정한 시간을 보장하지만 삽입 연산의 시간 복잡도는 O(n)이 됩니다. 

 

큐 활용 사례

• 파일 입출력
• 프로세스 스케줄링

 

스택과 큐를 활용한 프로그래머스 문제_주식투자