코딩 테스트 스터디 - 06, 07 스택과 큐

스택

Last In First Out, 나중에 넣은 애가 먼저 나오는 자료 구조.
특정 문제에서 스택을 필요로 하는 경우 스택을 선택하면 된다.

이 문제가 스택 문제인지 알아야 함 ->

1. 가장 최근에 들어온 원소를 알 수 있다.
2. 가장 최근에 들어온 원소순으로 나온다. (가장 최근에 들어온 원소에 대해 작업해야 할 때)

ADT란?

Abstract Data Type.
세부 사항 (내부 자료구조, 언어, 공간 크기) 숨기고 필요한 기능만 명시 (연산, 입력, 출력)

스택의 ADT

구분	정의	역할
연산	boolean isFull()	데이터 개수가 maxSize면 t, 아니면 f
	boolean isEmpty()	비었으면 t, 아니면 f
	void push(ItemType item)	데이터 푸시
	ItemType pop()	데이터 팝, 이후 반환
상태	int top	최근에 푸시한 데이터 위치
	ItemType data[maxSize]	데이터 관리 배열

사용 예시 1

메모리 입장에서, 끝나야 메모리에서 사라지므로.

사용 예시 2

웹 페이지를 전환할 때 스택에 푸시. 이전 페이지로 가면 팝.

사용 예시 3

괄호 짝 맞추기 : 우리가 어떻게 짝이 맞다 틀리다 판단하는가?
개발자에게 필요한 것 : 직관 이전 어떻게 생각이 되는지 세세하게 과정을 나타내야 함.
-> 열린 괄호는 가장 가까운 닫힌 괄호와 매칭됨.
닫힌 괄호 기준 가장 최근의 열린 괄호와 매칭되게 해야 한다! -> 가장 최근에 들어온 원소(괄호)
반복

• 여는 괄호는 push
• 닫는 괄호는 pop.
• -> 문자열 끝까지 수행하고 남아있는 게 없으면 Success!

큐

First In First Out. 먼저 넣은 애가 먼저 나오는 자료 구조.

큐 ADT

구분	정의	역할
연산	boolean isFull()	큐의 데이터 개수가 maxsize인지?
	boolean isEmpty()	큐 데이터가 없는지
	void push(ItemType item)	큐에 데이터 푸시
	ItemType pop()	큐에서 처음에 푸시한 데이터를 팝하고 데이터 반환
상태	int front	가장 먼저 푸시된 원소의 위치
	int rear	최근에 푸시한 위치
	ItemType data[maxsize]	큐 데이터 관리 배열

사용 예시

줄 서기

오세푸스 문제

1. N명의 사람들이 원형으로 둘러앉음. 번호는 1~N.
2. 시작부터 K번째 사람 제거.
3. 제거한 위치부터 K번째 사람 제거.
4. 한 명이 남을 때까지 1~3 제거

-> 제거 방향 바뀌고, 배열로 한다면 제거 시 제거한 뒤 원소가 모두 이동해야 함. N개 원소 N번 땡겨야 하므로 O(N^2)
k번째 원소 제거 : k-1번째까지는 팝, 푸시 해서 뒤로 뺀다. 팝한 걸 다시 푸시. (앞에 있던 게 뒤로 간다.) 시간 복잡도 O(N*K)

? 원형 큐랑 다른 건가?

정리

• 스택 : LIFO. 함수 호출 관리. 페이지 탐색. 괄호 짝 : 가장 최근 원소를 봐야할 때, DFS
• 큐 : FIFO. 줄 서기. 요세푸스. : 들어온 순서대로 나갈 때, BFS

그래프에서도 방금 방문한 노드를 방문한다고 하면 (백트래킹) : DFS 스택으로 해야 한다.

출처 : 코딩 테스트 합격자 되기 - 박경록