스택 (stack)
물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조
스택에 저장된 자료는 선형 구조를 갖는다.
선형 구조 : 자료 간의 관계가 1대 1의 관계를 갖는다.
비선형 구조 : 자료간의 관계가 1대 N관계를 갖는다. ex) 트리
스택에 자료를 삽입하거나 자료를 꺼낼 수 있다.
후입선출구조(LIFO - Last In First Out)
마지막에 삽입한 자료를 가장 먼저 꺼낸다.
주요 연산
top : 저장된 원소 중 마지막 원소
push : 저장소에 자료를 저장한다.(삽입)
pop : 저장소에서 자료를 꺼낸다.(삭제)
peek : 스탯의 top에 있는 item(원소)를 반환한다. 삭제가 일어나지 않는다.
java.util.Stack
push()
pop()
isEmpty()
size()
Function call
프로그램에서의 함수 호출과 복귀에 따른 수행 순서 관리
가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀 하는 후입선출 구조
후입선출 구조의 스택을 이용하여 수행순서 관리
함수호출이 발생하면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임(stack frame)에 저장하여 시스템 스택에 삽입
함수 실행이 끝나면 시스템 스택의 top 원소(스택 프레임)를 삭제(pop)하면서 프레임에 저장되어 있던 복귀주소를 확인하고 복귀
함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 된다.
후위 표기법의 수식을 스택을 이용하여 계산
- 피연산자를 만나면 스택에 push
- 연산자를 만나면 필요한 만큼의 피연사를 스택에서 pop하여 연산하고, 연산결과를 다시 스택에 push
- 수식이 끝나면 마지막으로 스택을 pop하여 출력
큐(Queue)
스탯과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조
선입선축구조(FIFO : First In First Out)
큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입(Fisrt In)된 원소는 가장 먼저 삭제(First Out)
머리(front) : 마지막으로 삭제된 원소
꼬리(rear) : 마지막으로 들어온 원소
원소 삽입 : enQueue
원소삭제 : deQueue
java.util.Queue
큐에 필요한 연산을 선언해 놓은 인터페이스
LinkedList 클래스를 Queue 인터페이스의 구현체호 많이 사용
주요 메서드
offer()
poll()
isEmpty()
size()
버퍼
데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역
버퍼는 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용
순서대로 입력/출력/전달 되어야 하므로 FIFO 방식의 자료구조인 큐가 활용
<.div>'Coding Test > Reference' 카테고리의 다른 글
| 백트래킹 (backtracking) (0) | 2022.10.02 |
|---|---|
| 분할 정복(Divide and Conquer) (1) | 2022.08.29 |
| 힙(heap) (0) | 2022.08.29 |
| 너비 우선 탐색(BFS) / 깊이 우선 탐색(BFS) (0) | 2022.08.29 |
| 트리(tree) (0) | 2022.08.29 |