[코드스테이츠] 05_12_TIL : 알고리즘/자료구조 _ Stack/Queue

Today I Lean

알고리즘/자료구조 _ Stack/Queue

 

생각보다 개념은 쉬웠지만, 이것을 또 적용하여 문제를 푸는것은 쉬운일이 아니었다.

이전의 개념도 확실히 자리잡지 못해서 더 어려웠던것 같다.

 

 

 

학습목표 및 개념정리

#  자료 구조의 이해

- 자료구조의 기초 개념을 학습한다.

- 자료구조가 무엇인지 설명할 수 있다,

 

# Stack

- Stack의 자료구조에 대해 이해할 수 있다.

- 알고리즘 문제에서 Stack 자료구조를 배열로 대체하여 흉내낼 수 있다.

 

# Queue

- Queue의 자료구조에 대해 이해할 수 있다.

- 알고리즘 문제에서 Queue 자료구조를 배열로 대체하여 흉내낼 수 있다.

 

# 전체 학습 목표

- 각 자료구조가 가진 특징을 학습한다.

- 각 자료 구조를 사용하기 적합한 상황을 이해한다.

- 다른 자료 구조와의 차이점을 이해하기 위해 자료 구조 내부를 직접 구현한다.

- 자료 구조를 구현하며, 자료 구조의 동작 원리를 이해한다.

 

 

 

 

배운 것

# 자료 구조의 이해

1. 자료 구조란?

 : 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의 한 것

 

- 데이터(Data) 란?

 : 실생활을 구성하고 있는 모든 값

• 데이터는 분석하고 정리후, 활용해야만 의미가 있음
• 필요에 따라 데이터의 특징을 잘 파악(분석)해야 함
• 데이터를 체계적으로 정리해서 저장하는것이, 데이터 활용에 유리

 → 데이터를 효율적으로 다루는 방법 "자료구조"

(자료구조는 특정상황의 문제해결에 특화되어 있음, 문제에 적합한 자료구조를 빨리 찾는것이 효율적) 

 

 

 

# Stack

1. Stack의 정의와 구조

: 데이터를 순서대로 쌓는 자료 구조

• 선입후출 (FILO → First In Last Out) == 후입선출 (LIFO → Last In First Out)
• 입력과 출력이 하나의 방향으로 이루어 지는 제한적접근 (막다른 길)
• Stack에 데이터를 넣는것 "PUSH", 데이터를 꺼내는 것 "POP"

 → 브라우저 페이지 "뒤로가기 - 앞으로가기"

 → "Ctrl+Z - Ctrl+Shift+Z"

 

 

 

2. Stack의 특징

- LIFO (Last In First Out)

 : 후입선출의 구조

• 1-2-3-4 의 순서로 데이터를 넣었다면, 4-3-2-1 의 순서로 출력됨
• 데이터는 하나씩 넣고 뺄 수 있음

 → 만약 입출력 방향이 여러개 라면 Stack 자료구조라고 볼 수 없음

 → 말은 다르지만, FILO와 LIFO는 같음

 

 

 

3. Stack의 장단점

장점 (Java 제외 일반적인 스택의 개념)

Stack에 저장된 데이터를 가져오는 속도가 매우 빠름 ▪ 데이터를 중간에 넣거나, 다른 데이터의 위치를 변경할 필요가 없기 때문 ▪ 데이터 삽입, 삭제 모두 Stack의 가장 위에서 처리됨

별도의 라이브러리나 모듈설치가 필요없음 ▪ 자바에서 Stack을 기본 자료구조로 제공

단점 (Java에서만의 단점)

크기 제한이 없음 ▪ 메모리 사용량이 불필요하게 증가할 수 있음 (Stack의 크기를 정해놓거나, 동적으로 조절필요)

Vector 클래스를 상속받아 구현됨 (Java에서 제공하는 Stack클래스 한정) ▪ Vactor 클래스는 내부적으로 배열을 사용하여 구현되기 때문에, 크기를 동적으로 조절할 수 없음 ▪ Stack에 저장되는 데이터의 개수가 배열의 크기를 초과하면, 배열을 새로 만드는 작업이 추가되어 성능이 저하됨

 

 

 

 

 

 

# Queue

1. Queue의 정의와 구조

: 줄을 서서 기다리대, 대기행렬

• 선입선출 (FIFO → First In First Out) == 후입후출 (LILO → Last In Last Out)
• 입력과 출력의 방향이 정해져 있는 (일방통행)
• Queue에 데이터를 넣는것 "enqueue", 데이터를 꺼내는 것 "dequeue"

 → 대기고객의 순서를 결정하는 경우

 → 채팅 메세지를 보내는 순서를 결정하는 경우

 

 

 

2. Queue의 특징

- FIFO (First In First Out)

 : 선입선출의 구조

• 1-2-3-4 의 순서로 데이터를 넣었다면, 1-2-3-4 의 순서로 출력됨
• 데이터는 하나씩 넣고 뺄 수 있음

 → 만약 입출력 방향이 같다면 Queue자료구조라고 볼 수 없음

 → 말은 다르지만, FIFO와 LILO는 같음

 

 

 

3. Queue의 장단점

장점 (Java 제외 일반적인 큐의 개념)

Queue에 저장된 데이터의 순서대로 데이터를 꺼낼 수 있음 ▪ 처리해야 할 데이터나 작업을 차례대로 처리할 수 있음 (효율적인 처리 가능) ▪ 데이터를 삽입하는 순서와 삭제하는 순서가 동일

Queue에서의 삽입과 삭제는, 다른 자료구조에 비해 상대적으로 빠름 ▪ 각각의 Queue의 양 끝단에서 이뤄지기 때문에, 중간의 요소를 삭제하는 연산이 없음 ▪ 삽입은 Queue의 맨 끝, 삭제는 Queue의 맨 앞 ▪ 데이터의 순서 수정 및 변경이 빈번한 환경이나, 차례대로 처리해야 하는 상황에서 효과적임

별도의 라이브러리나 모듈설치가 필요없음 ▪ 자바에서 Queue를 기본 자료구조로 제공

단점

중간에 위치한 데이터를 조회, 수정하는 연산이 힘듦 ▪ 순서대로 데이터를 처리 하기 때문에 중간에 있는 데이터를 변경하거나, 조회하는 것이 불가능

remove(Object o) 메서드의 동작이 불명확함 (Java에서 제공하는 Queue인터페이스 한정) ▪ remove(Object o) 메서드는 해당 객체를 큐에서 삭제하지만, 해당객체가 중복일 경우 어떤 객체가 삭제되는지 명확하지 않음. ▪ 대신 poll() 메서드를 사용하여 원하는 객체를 삭제 가능

크기 제한이 없음 (Java에서 제공하는 Queue인터페이스 한정) ▪ 메모리 사용량이 불필요하게 증가할 수 있음 (Queue의 크기를 정해놓거나, 동적으로 조절필요)

iterator() 메서드가 지원되지 않음 (Java에서 제공하는 Queue인터페이스 한정) ▪ Queue 인터페이스가 FIFO의 구조를 갖기 때문 ▪ 따라서 큐의 데이터를 순회 할 때는 peek()메서드와 poll()메서드를 사용하여 각각의 데이터를 차례로 가져와야 함

 

 

 

 

 

*****

- 각 Stack 클래스의 메서드와 사용 가능한 코드 (예시는 Stack 클래스 파일에)

메서드	코드	설명
push()	▪ listStack.add(data) ▪ this.add(data)	listStack이라는 ArrayList에 data를 추가 현재 객체에 data를 추가
pop()	▪ listStack.remove(index) ▪ this.remove(index)	listStack이라는 ArrayList에서 값을 제거 현재 객체에서 값을 제거
size()	▪ listStack.size() ▪ this.size()	listStack이라는 ArrayList의 크기를 반환 현재 객체의 크기를 반환
peek()	▪ listStack.get(index) ▪ this.get(index)	listStack이라는 ArrayList에서 값을 가져옴 현재 객체에서 값을 가져옴
show()	▪ listStack.toString() ▪ this.toString()	listStack이라는 ArrayList를 문자열로 변환 현재 객체를 문자열로 변환
clear()	▪ listStack.clear() ▪ this.clear()	listStack이라는 ArrayList를 비움 현재 객체를 비움

 

 

 

- 각 Queue 클래스의 메서드와 사용 가능한 코드 (예시는 Queue 클래스 파일에)

메서드	코드	설명
offer()	▪ queue.offer(data) ▪ this.offer(data)	queue라는 Queue에 data를 추가 현재 객체에 data를 추가
poll()	▪ queue.poll() ▪ this.poll()	queue라는 Queue에서 첫 번째 요소를 제거하고 반환 현재 객체에서 첫 번째 요소를 제거하고 반환
size()	▪ queue.size() ▪ this.size()	queue라는 Queue의 크기를 반환 현재 객체의 크기를 반환
peek()	▪ queue.peek() ▪ this.peek()	queue라는 Queue에서 첫 번째 요소를 반환 현재 객체에서 첫 번째 요소를 반환
toString()	▪ queue.toString() ▪ this.toString()	queue라는 Queue를 문자열로 변환하여 반환 현재 객체를 문자열로 변환하여 반환
clear()	▪ queue.clear() ▪ this.clear()	queue라는 Queue를 비움 현재 객체를 비움

 

 

 

 

Tomorrow Chapter

# Tree

# Graph

 

 

 

---

 

 

↓ 이전 글 ↓

 

[코드스테이츠] 05_11_TIL : 알고리즘 / 자료구조 _ 재귀함수 실습과제

↓ 코트스테이츠 부트캠프 관련 글 한번에 보기 ↓

'IT/코드스테이츠 부트캠프' 카테고리의 글 목록