스택(Stack)
스택은 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입/출력 순서는 후입선출(LIFO) 방식이다.
쉽게 말해 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조이다.
대표적인 스택의 활용으로는 컴퓨터 내부의 프로세스 구조의 함수 동작 방식이 있다.
스택 구조
스택은 LIFO(List In First Out) 형식을 따르기 때문에 가장 최근 추가된 항목이 가장 먼저 제거된다.
- push(item): item 하나를 스택의 가장 윗부분에 추가한다.
- pop(): 스택에서 가장 위에 있는 항목을 제거한다.
- peek(): 스택의 가장 위에 있는 항목을 반환한다.
- isEmpty(): 스택이 비어 있을 때에 true를 반환한다.
- length(): 스택의 길이를 반환한다.
- getBuffer(): 스택 전체를 반환한다.
스택을 사용하는 경우
- 재귀 알고리즘
- 재귀적으로 함수를 호출해야하는 경우에 임시 데이터를 스택에 넣어준다.
- 웹 브라우저 방문기록(뒤로가기)
- 실행 취소(undo)
- 역순 문자열 만들기
- 수식의 괄호 검사
- 후위 표기법 계산
스택 구현 방법
- 배열을 사용하는 방법
- 배열을 사용시 구현이 쉽다.
- 원하는 데이터로의 접근 속도가 빠르다.
- 데이터의 최대 개수가 미리 정해져야 한다.
- 데이터의 삽입 및 삭제에 있어 비효율적이다.
ex)두 번째 위치에 데이터를 삽입하려면 그 보다 먼저 들어간 데이터들을 한칸씩 전부 옮겨줘야 한다.
=> 데이터의 양이 많지만 삽입/삭제가 거의 없고 데이터의 접근이 자주 일어날 때 사용하면 좋다.
- 연결 리스트를 사용하는 방법
- 데이터의 최대 개수가 한정적이지 않다
- 데이터의 삽입 및 삭제에 용이하다.
=> 삽입/삭제가 빈번히 이뤄지고 데이터의 접근이 거의 없을때 사용하는 것이 좋다.
큐(Queue)
스택과 같이 데이터를 임시 저장하는 자료구조이다. 그러나 스택과 반대로 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 구조이다.
큐 구조
큐는 FIFO(Fist In First Out) 형식을 따르기 때문에 항목이 추가된 순서로 제거 된다.
- push(item): 큐에서도 Stack과 동일하게 값을 추가할 때는 맨 뒤에 담기 때문에 똑같이 push를 사용하면 된다.
- splice(): 큐에서 가장 맨 앞의 값을 return 함과 동시에 제거한다.
- peek(): 큐에서 가장 맨 앞의 값을 확인한다.
- isEmpty(): 큐가 비어 있을 때에 true를 반환한다.
- length(): 큐의 길이를 반환한다.
- getBuffer(): 큐 전체를 반환한다.
큐를 사용하는 경우
- 선착순 관련한 경우의 구현이 필요할 때
- 알고리즘에선 우선순위 큐 또는 BFS에서 사용된다.
큐 구현 방법
- 배열을 사용하는 방법
- 자바스크립트의 pop(),shift()를 활용하여 큐를 구현할 수 있지만 삽입과 삭제시 시간복잡도가 O(n)이 된다.
이유는 삽입과 삭제시 배열의 재정렬이 필요하기 때문이다.
따라서 일반적으로 데이터가 1000건 이하인 경우는 shift, pop을 이용한 큐를 사용해도 무방하다고 한다.
