📌 Stack 스택
스택 추상 데이터 타입
top이라고하는 한쪽 끝에서 모든 삽입(push)과 삭제(pop)가 일어나는 순서 리스트
LIFO(Last In First Out) = 후입선출
연산 : push, pop, peek
시스템 스택
프로그램 실행 시 함수 호출을 처리
함수 호출 시 activation record 또는 stack frame 구조를 생성하여 시스템 스택의 톱에 둠 → 이전 스택 프레임에 대한 포인터, 복귀 주소, 지역 변수, 매개 변수 등을 저장
📌 Queue 큐
큐 추상 데이터 타입
한쪽 끝에서 삽입이 일어나고 그 반대쪽 끝에서 삭제가 일어나는 순서 리스트
- rear 리어 : 새로운 원소가 삽입되는 끝
- front 프론트 : 원소가 삭제되는 끝
연산 : enQueue, deQueue
FIFO(First In First Out) 선입선출 리스트
큐의 구현 방법
-
단순 배열 이용 : front를 queue[0]으로 표현한 큐
삭제 pop : queue[0]에 있는 원소를 제거
→ 삭제할때마다 나머지 원소들을 왼쪽으로 이동해야 함
→ 큐에 n개의 원소가 있을때 O(n)시간 걸림
삽입 push : 배열 크기 조절 시간 제외하면 O(1)
-
배열 응용 : front를 queue[front]로 표현한 큐
변수 front를 이용하여 큐의 첫번째 위치를 항상 유지
삭제가 O(1)시간에 가능
문제점 : 배열 queue의 크기가 capacity일 경우, rear가 capacity-1과 같고, front > 0일 때 문제 발생
→ 배열의 크기 확장하지 않고 어떻게 원소 삽입할까?
→ 큐의 모든 원소를 왼쪽끝으로 이동시켜 오른쪽에 공간 만들어야함
→ 배열 이동에 많은 시간 소요 : 큐의 원소 수에 비례
→ 원형큐를 사용하여 문제 해결 : 최악의 경우 삽입, 삭제 시간은 O(1)로
📌 Circular queue 원형 큐
front : 큐에서 첫 원소의 위치보다 시계방향으로 하나 앞 위치를 가리킴
rear : 큐에서 마지막 원소의 위치를 가리킴
큐의 공백 조건 : front == rear
만원이 되기전에 큐의 크기를 증가시켜야함
공백과 포화를 구분하기 위해 최대 원소 수를 capacity가 아니라 capacity-1로 한다
위 그림에서 두번째 상태일때 큐의 크기를 2배로 확장하도록 한다
lastOp 변수를 사용해서 배열 큐의 공간 전부를 사용하도록 할 수도 있음
→ 큐에서 수행된 마지막 연산을 기록해둠 (push/pop)
→ front == rear일때 lastOp가 push면 포화, pop이면 공백
→ 대신 삽입, 삭제 연산 느려짐
📌 미로 문제
1≤i≤m이고 1≤j≤p인 이차원 배열 maze[m][p]로 표현 → 인접행렬로 표현
- 1 : 통로가 막혀있음
- 0 : 통과할 수 있음
- 가장 바깥쪽 i = 1 or m 이거나 j = 1 or p인 경우에는 가능한 방향이 3방향만 존재 이를 위해 미로의 주위를 1로 둘러싸야함 → maze[m+2][p+2]로 선언
- 이동방향은 8개 가능
- 이동시, 현재 위치와 직전 이동방향을 저장한 후 한 방향을 선택
세 배열 maze, mark, move를 사용 시 mark에는 현재위치와 직전이동방향을 스택으로 저장
알고리즘
- 현재 위치에서 이동가능한 모든 방향에 대해 이동 가능 여부 판단
- 처음 발견한 이동방향으로 이동하여 스택에 쌓음
- 이동가능한 곳이 없을 경우, 이동 가능할때까지 pop하여 되돌아감(백트래킹)
- 출구찾은 경우 탐색 종료하고, 만약 탐색 재개 위치를 찾을 수 없다면 경로가 없는 것이므로 경로 탐색 불가
📌 수식의 계산
중위 표기식 : 우리가 주로 쓰는 방식
ex) a * b / c
후위 표기식 : 연산자를 뒤로
ex) a b * c /
괄호가 불필요. 연산자 우선순위가 무의미. 계산 과정 간단
왼쪽 → 오른쪽
전위 표기식 : 연산자를 앞ㅇ로
ex) / * a b c
중위 → 후위 변환 : 스택 구조 이용
알파벳은 바로 출력한다
연산자가 들어오면 스택에 쌓음 → 이때 새로들어오는 연산자가 먼저있던것보다 우선순위 높거나 같으면 pop하고 출력함
+) 추가
자바에서 스택, 큐 사용 예시
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[]args)throws IOException{
Stack<Integer> stack = new Stack<>();
Queue<Integer> queue = new LinkedList<>();
stack.push(1);
stack.pop(1);
stack.peek();
queue.offer(1);
queue.poll(1);
queue.peek();
}
}