자료구조 - 백(Bag), 스택(Stack), 큐(Queue)

백(Bag)

---

'우리는 항상 가방에서 물건을 꺼낼 때 중간에 있는 물건을 잡기 마련이다. 그리고 그 중간의 물건을 꺼내게 된다.'는 발상에 근거하여 Bag 자료구조가 나타나게 되었다. 백은 항목을 삭제할 수 없는 컬렉션으로 항목을 수집하고 수집된 항목들을 순회할 수 있는 도구를 제공한다. 항목들은 서로 어떤 순서로 순회하는지 전혀 상관하지 않는다. 그래서 항목의 순서에 특별히 의미가 없다면 백을 이용한다.

 

📌 백을 사용하는 이유

백을 사용하는 이유는 단순히 데이터를 추가하고자 할 때 사용한다. 예를 들어, 중간에 조작을 하면 안 되는 로그 데이터 등의 경우에 백을 사용할 수 있다. 배열을 사용할 수도 있지만, 추상 데이터 타입은 필요한 연산만 제공하여 중간의 값을 읽거나 삭제할 수 없도록 강제하여 데이터의 완결성을 유지하도록 하는 효과가 있다.

 

📌 백 특징

1. 중복 허용 : Bag 자료구조는 같은 요소를 여러 번 포함할 수 있다. 예를 들어 {apple, apple, banana}와 같은 형태가 가능하다.
2. 순서 없음 : Bag은 데이터 삽입 순서를 유지하지 않는다. 따라서 {apple, apple, banana}와 {apple, banana, apple}은 같은 Bag으로 간주한다.
3. 데이터 추가 및 제거 : 요소를 추가하거나 제거하는 작업이 가능하다. 하지만 특정 요소의 위치나 순서를 고려하지 않기 때문에 요소의 존재 여부나 개수를 관리하는 것이 주된 기능이다.

 

📌 백 기본 연산

Push	원소를 삽입하는 연산으로, 배열내에서 이용가능한 첫 번째 위치를 찾아내어 그 자리에 원소를 삽입한다. 배열이 꽉 찼을 경우, 배열의 크기를 두 배로 확장한다.
Pop	원소를 제거하는 연산으로, 배열의 중앙에 위치한 원소를 찾아 제거하고 뒤따른 원소들의 위치를 한 칸씩 조정한다.

 

Ex.

-1로 초기화 된 Bag Array가 존재한다.

이때 한 칸씩 Push하여 0번 째 배열부터 4번째 배열까지 1~5의 값을 넣게 되었다.

이때 배열의 위치를 가리키는 position이라는 병수는 마지막 값 다음 칸을 가리키고 있다.

해당 배열에서 Pop을 실행하게 되면 처음 시작점의 중간지점인 ((position-1)/2)을 가리키게하여 Pop을 한다.

 

그렇게 되면 세 자리가 공백이 되니 한 칸씩 왼쪽으로 당겨주어 위와 같은 형태의 배열이 된다.

 

 

 

스택(Stack) : LIFO(Last In First Out)

---

스택은 마지막으로 들어간 것이 가장 먼저 나오는 LIFO(Last In First Out) 정책을 가지는 컬렉션이다. 즉, 스택에 삽입 된 마지막 항목이 스택에서 제거될 첫 번째 항목이라는 의미이다.

📌 배열과 스택

스택이 데이터를 저장하는 방법은 배열처럼 단순히 원소들의 리스트이다. 그러나 배열은 어떤 인덱스든 정상적으로 읽을 수 있지만 스택 인터페이스로 배열을 사용하면 마지막 항목만 읽을 수 있다. 배열은 대부분의 프로그래밍 언어에 내장되어 있고 컴퓨터 메모리와 직접 상호작용한다. 그러나 스택은 규칙 집합이며 특정 결과를 얻기 위해 배열과 상호작용하는 방식을 다룬다.

 

사실 스택은 LIFO방식으로 동작하는 데이터 원소들의 리스트인 데이터 구조를 사용하면 된다. 그래서 배열을 쓰든 다른 내장 데이터 구조를 쓰든 실제로 중요하지 않기 때문에 스택은 추상 데이터 타입이다. 보통 오래 사용하는 데이터를 저장할 때는 스택을 사용하지 않고 임시 데이터를 다뤄야 하는 알고리즘에서 사용된다.

 

📌 스택 특징

1. 데이터는 스택의 끝에만 삽입할 수 있다.
2. 데이터는 스택의 끝에서만 삭제할 수 있다.
3. 스택의 마지막 원소만 읽을 수 있다.

 

📌 스택을 사용하는 이유

• 스택처럼 제약을 갖는 데이터 구조를 사용하면 잠재적 버그를 막을 수 있다.
• 스택 같은 데이터 구조는 문제를 해결하는 새로운 사고 모델을 제공한다.

 

📌 스택은 어디에 사용되는가?

• 스택은 데이터의 삽입과 삭제가 한 곳에서만 되도록 강제하기 때문에 특정 알고리즘을 해결할 때 유용하게 사용할 수 있다. (Ex. 실행 취소(undo))
• 스택은 마지막에 들어온 데이터부터 먼저 처리해야 할 때 이상적이다. (Ex. 웹 브라우저 방문기록 (뒤로 가기))

 

📌 스택 기본 연산

Push	스택의 맨 위에 새로운 데이터를 추가하는 연산이다.
Pop	스택의 맨 위에 있는 데이터를 제거하고 반환하는 연산이다.
Peek/Top	스택의 맨 위에 있는 데이터를 제거하지 않고 반환하는 연산이다.
isEmpty	스택이 비어있는지 여부를 확인하는 연산이다.
Size	스택에 들어있는 데이터의 개수를 반환하는 연산이다.

 

 

 

큐(Queue) : FIFO(First In First Out)

---

큐는 먼저 들어간 것이 먼저 나오는 것(First In First Out, FIFO)을 정책으로 하는 컬렉션이다. 즉, 큐에 삽입된 첫 번째로 추가된 항목이 큐에서 제거될 첫 번째 항목이라는 뜻이다. 큐는 임시 데이터를 처리하기 위한 데이터 구조로 스택처럼 컬렉션이다. 그래서 주로 순회하는 데 사용되는데 가장 먼저 넣은 데이터부터 가장 나중에 넣은 데이터 순서대로 순회한다.

 

📌 큐 특징

1. 데이터는 큐의 끝에만 삽입할 수 있다.
2. 데티터는 큐의 앞에서만 삭제할 수 있다.
3. 큐의 앞에 있는 원소만 읽을 수 있다.

 

📌 큐를 사용하는 이유

• 데이터를 컬렉션에 저장하면서 데이터 간의 상대적인 순서를 보존할 수 있다.

 

📌 큐는 어디에 사용되는가?

• 큐는 요청받은 수서대로 요청을 처리하므로 비동기식 요청을 처리하는 완벽한 도구이다. 그래서 순서대로 발생하는 이벤트를 처리해야 할 때 유용하게 사용된다. (Ex. 은행 업무, 대기열 순서와 같은 우선순위의 작업 예약, 서비스 센터의 대기 시간, 프로세스 관리 등..)

 

📌 큐 기본 연산

Enqueue	큐의 뒤쪽 데이터를 추가하는 연산이다.
Dequeue	큐의 앞쪽 끝에서 데이터를 제거하고 반환하는 연산이다.
Front/Peek	큐의 가장 앞에 있는 데이터를 확인하되, 큐에서 제거하지는 않는 연산이다.
isEmpty	큐가 비어있는지를 확인하는 연산이다.