Data Structure Ⅰ - Stack & Queue

데이터 타입이란 하나의 데이터를 어떤 식으로 해석할지 정의한 것이다. 숫자, 문자, Boolean처럼 데이터 타입을 설정함으로 인해 해당 데이터가 메모리에 어떻게 저장되고, 또 어떻게 처리되는지를 구분할 수 있다. 그렇다면 자료구조란 무엇일까? 자료구조(Data Structure)란 이런 여러 데이터들의 묶음을 어떻게 저장하고 사용할지를 정의한 것이다. 자료구조에는 여러 종류가 있는데, 이번 주는 각 자료구조에 대한 개념 및 각 자료구조가 주는 장단점에 대해 알아보려고 한다. 우선 오늘은 그중에서도 가장 간단하다고 할 수 있는 Stack과 Queue에 대해 정리해보려고 한다.

---

📎 Stack

쉽게 생각해서 Stack은 고리 던지기 게임의 논리와 같다. 막대에 먼저 들어간 고리는 가장 밑에 쌓이기 때문에 가장 마지막에 꺼낼 수 있고, 반대로 막대에 가장 마지막에 들어간 고리는 가장 위에 쌓이기 때문에 가장 먼저 꺼낼 수 있다.

위 그림을 보았을 때 storage는 고리가 들어가는 기둥이고, storage에 들어가있는 블록들은 고리라고 볼 수 있다. 가장 먼저 추가된 블록1은 storage의 가장 밑에 쌓이고, 가장 마지막에 추가된 블록4는 가장 위에 쌓이기 때문에, storage에서 블록을 하나 가져오게 된다면 가장 마지막에 추가된 블록4를 가져오게 되는 것이다.

🏷️ Stack의 주요 속성

• top : value의 현재 위치를 할당
• size() : 스택의 현재 요소 갯수를 반환
• push() : 스택의 마지막에 요소를 추가
• pop() : 스택의 마지막에 추가된 요소를 제거 후 반환
• peek() : 가장 위에 있는 요소를 반환 (제거하지 않고 내용만 확인)
• empty() : 스택에 요소가 있는지 여부를 반환

🏷️ 수도코드로 작성해보기

1. 요소를 넣어줄 객체 storage와 요소의 index를 할당해줄 top을 선언해준다.
2. 스택에 현재 남아있는 요소 갯수를 리턴해줄 메서드를 만들어준다.
   요소 추가
3. 초기값의 top이 0이라고 가정할 경우, 요소 추가 시 top에 1씩 더해준다.
4. 그리고 storage에 요소의 index를 key로, 요소를 value로 하여 푸쉬해준다.
   요소 제거
5. 현재 남아있는 요소의 갯수가 0보다 클 경우를 가정한다.
6. 새로운 변수에 storage 객체에서 마지막에 추가된 속성을 할당해준다.
7. 해당 객체를 제거해준 뒤 top에서 1씩 빼준다.
8. 가장 마지막 요소가 제거된 변수를 리턴해준다.

🏷️ Stack의 장단점

• 장점 : 원하는 데이터로 접근하기가 빠르다.
• 단점 : 스택의 크기가 정해져 있어 공간이 꽉 차면 더이상 데이터를 추가할 수 없다.

---

📎 Queue

Queue는 데이터를 순서대로 실행시키기 위해 사용한다. 우리가 흔히 일상에서 볼 수 있는 정수기 옆 종이컵홀더의 원리와 동일하다고 볼 수 있다. 종이컵을 채울 때에는 위에서 밑으로 채워넣고, 종이컵을 사용할 때에는 가장 먼저 채워진 종이컵부터 사용한다. Queue도 이와 같이 요소를 storage의 가장 뒤에 추가하고, 제거 시 가장 처음에 추가된 요소가 가장 먼저 제거된 후 반환된다.

위 그림처럼 Queue는 enqueue 메서드를 통해 블록을 storage 가장 마지막에 추가하고, dequeue 메서드를 통해 가장 앞에 있던 블록을 storage로부터 제거한다. Queue는 주로 데이터의 우선 순위가 필요한 경우나, 순서대로 처리해야 하는 데이터를 대기시켜 놓는 경우에 많이 사용된다.

🏷️ Queue의 주요 속성

• front : 큐의 처음에 저장된 요소 index를 확인
• rear : 큐의 마지막에 저장된 요소 index를 확인
• size() : 큐의 현재 요소 갯수를 반환
• enqueue() : 큐의 마지막에 요소를 추가
• dequeue() : 큐의 처음에 있는 요소를 제거하고 반환

🏷️ 수도코드로 작성해보기

1. 요소를 넣어줄 객체 storage를 만들어준다.
2. 첫 요소의 인덱스인 front와 마지막 요소의 인덱스인 rear를 선언해준다.
3. 큐에 현재 남아있는 요소 갯수를 리턴해줄 메서드를 만들어준다.
   요소 추가
4. 빈 객체 storage에 요소의 index를 key로, 요소를 value로 쌍으로 하는 객체를 만든다.
5. 요소 추가 시 top에 1씩 더해준 것을 푸쉬해준다.
   요소 제거
6. 현재 남아있는 요소의 갯수가 0보다 클 경우를 가정한다.
7. 새로운 변수에 객체 storage 가장 처음에 있는 front 속성을 할당해준다.
8. 해당 객체를 제거해준 뒤 front 값을 1씩 더해준다.
9. 가장 처음 요소가 제거된 변수를 리턴해준다.

🏷️ Queue의 장단점

• 장점 : 데이터가 입력된 시간순대로 처리해야 할 경우 편리하다.
• 단점 : 앞 부분이 비어있어도 데이터를 추가할 수 없다.