스택/큐 (Stack | Queue)

| 스택 (Stack)

스택은 LIFO (Last In Last Out) 즉 후입선출의 원칙으로 만들어진 자료구조이다.

주로 프링글스 통이 예시로 사용된다.

프링글스를 제조할 때 여러개의 감자칩을 하나하나 넣는다면 소비자의 입장에서는 제일 늦게 들어간 감자칩을 먼저 먹을것이다.

자바스크립트에서는 스택과 큐를 내장으로 지원하지 않는다.

 

스택은 배열로 구현하거나 Class를 만들어서 직접 구현할 수 있다.

 

| Array(배열) 로 구현

 

배열의 내장함수인 push와 pop으로 구현할 수 있다.

push는 배열의 마지막 요소 다음에 값을 추가한다.

pop은 배열의 마지막 요소를 삭제한다.

그래서 LIFO 구조를 구현할 수 있는것이다.

 

| Class 로 구현

 

Stack을 클래스화 해서 직접 구현할 수도 있다.

첫번째와 마지막 요소, 그리고 배열의 size까지 선언을 하고 push와 pop 메서드가 실행 될때

값들을 변경 시켜주며 구현할 수 있다.

 

| Stack에서의 Big-O

| insert = 시간복잡도는 O(1) 상수시간을 가지며 데이터가 무수히 많아도 삽입은 한번만 이루어 진다.

| delete = 마지막값이 삭제되므로 스택의 크기와 상관없이 시간복잡도는 O(1) 이다.

| Access = top을 통해서만 접근이 가능한 Stack 이기에 n번째를 찾기까지에는 top -> n 까지 순회할 수 밖에 없다. 그래서 O(n) 의 시간복잡도를 가진다.

| Search = 최상단의 값을 찾는다면 시간복잡도는 O(1)이다 하지만 찾고자 하는 데이터가 가장 밑에 있다면 하나하나 순회를 할 수 밖에 없다. Search 또한 상황에 따라 O(1)의 시간복잡도를 가질 수 있으나 거의 O(n)의 시간복잡도를 가진다.

| 큐 (Queue)

큐는 스택과 비슷한 데이터 구조이다.

스택과 같이 주로 데이터를 추가하고 제거하는데에 사용된다.

스택과의 가장 큰 차이점은 FIFO(First In First Out) 선입선출의 원칙으로 만들어진다.

놀이공원에서 줄을 기다릴때 줄을 먼저 선 사람이 제일 먼저 놀이기구에 탑승한다.

줄을 생각하면 제일 빠르게 이해할 수 있을것이다.

큐도 역시 자바스크립트에서는 내장으로 지원하지 않지만 직접 구현을 하는데에 어려움이 없으며

배열을 사용해서 구현할 수 있다.

 

| Array(배열) 로 구현

첫번째 요소가 들어가고 제거 하도록 unshift와 shift로 구현할 수 있다.

unshift는 배열의 첫번째 요소 앞에 값을 추가한다.

shipt는 배열의 첫번째 요소를 삭제한다.

 

unshift와 shift의 문제점은 동작 하나하나에 모든 요소의 인덱스가 변경이 된다.

 

| Class 로 구현

 

Queue 클래스의 enqueue는 값을 추가하는 메서드이다.

dequeue는 값을 삭제하는 메서드이다.

삭제 시 첫번째 요소를 다음 요소로 교체해준다.

 

| Queue에서의 Big-O

| insert = 큐에서의 데이터 삽입도 마지막요소 혹은 첫번째 요소에 값을 추가함으로 O(1)의 시간복잡도를 가진다.

| delete = 스택과 달리 배열의 첫번째 요소를 삭제하지만 무조건 첫번째 요소를 삭제함으로 O(1)의 시간복잡도를 가진다.

| Access = 큐 또한 한쪽으로만 데이터를 넣고 뺄수있다. 그래서 n번째 요소를 삭제/추가 하려면 첫 번째 데이터 부터 순회하기에 O(n)의 시간복잡도를 가진다.

| Search = 스택과 같이 검색하려는 값이 첫번째 요소라면 O(1)의 시간복잡도를 가지지만 아니라면 O(n)의 시간복잡도를 가진다.