스택(Stack)
Stack은 한 쪽 끝 (top) 에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)로 데이터를 저장하는 형식을 말합니다.
가장 먼저 들어온 데이터가 마지막으로 나가게 됩니다.
뷔페에 접시를 쌓아두면, 손님이 제일 위 접시부터 가져가는 맥락입니다. 새로운 접시가 쌓일 때도 맨 위에서 쌓이고, 접시를 가져갈 때도 맨 위에서 가지고 가는 것과 같습니다.
스택 활용 예시
- 프링글스 감자칩
- 하노이의 탑
- 재귀 함수
- 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여줍니다.
- 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소합니다.
- 후위 표기법 계산 : 기계가 사용하는 계산법
스택 property
- Array를 사용한 Stack
top(데이터 삽입/삭제하는 위치), maxSize(배열의 최대크기), stackArray(배열)
- Linked list를 사용한 Stack
top(데이터 삽입/삭제하는 위치), Node(스택을 구성하는 요소)
스택 메서드
- push(element)
요소를 스택의 최상단에 추가합니다.
- pop()
스택의 최상단에서 요소를 제거하고 반환합니다.
- size()
스택의 현재 요소 개수를 반환합니다.
- peek()
스택의 최상단에서 요소를 제거하지 않고 반환합니다.(pop은 제거하지만, peek은 제거하지 않습니다.)
- isEmpty()
스택이 비어 있으면 true, 그렇지 않으면 false로 반환합니다.
스택 구현
class Stack {
constructor() {
this.arr = [];
}
push(item) {
this.arr.push(item);
}
pop() {
return this.arr.pop();
}
peek() {
return this.arr[this.arr.length - 1];
}
}
const stack = new Stack();
큐 (Queue)
Queue는 자료를 뒤(rear)로 넣고 앞(front)으로 뺄 수 있는 (FIFO - First In First Out)구조로 데이터를 저장하는 형식을 말합니다.
먼저 집어 넣은 데이터가 먼저 나오게 됩니다.
삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정합니다.
놀이공원에서 서는 줄과 같이 작동합니다. 사람들이 맨 끝에 줄을 서고, 맨 앞에서부터 놀이기구에 탑승하는 것과 같습니다.
큐 활용 예시
- 은행 업무
- 캐시(Cache) 구현
- 선입선출이 필요한 대기열 (티켓 카운터)
- 프로세서 처리
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
큐 property
- Array를 사용한 Queue
front(데이터 삭제하는 위치), rear(데이터 삽입하는 위치), size, arrQueue(배열)
- Linked list를 사용한 Queue
front, rear
큐 메서드
- enqueue(element)
요소를 큐의 뒤에 추가합니다.
- dequeue()
요소를 큐의 앞에서 제거하고 반환합니다.
- size()
큐의 현재 요소 개수를 반환합니다.
- peek()
스택의 front 요소를 제거하지 않고 반환합니다.
- isEmpty()
스택이 비어 있으면 true, 그렇지 않으면 false로 반환합니다.
큐 구현
class Queue {
constructor() {
this.arr = [];
}
enqueue(item) {
this.arr.push(item);
}
dequeue() {
return this.arr.shift();
}
}
const queue = new Queue();
- 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우(put할 수 없는 경우)를 오버플로우(overflow),
큐가 비어 있어 자료를 꺼낼 수 없는 경우 (get 할 수 없는 경우)를 언더플로우(Underflow)라 합니다.