data structures

내가 스택과 큐를 이해하고자 한 이유는 컴퓨터의 동작원리를 본 뒤에 다른 것을 보고 그것을 이해하려면 data structures를 배워야 할 것 같아서! 컴퓨터의 동작원리는 내용이 너무너무 많아서 조금 더 정리를 한 뒤에 포스팅을 하려고 한다. Stack(스택)과 Queue(큐)는 가장 기본적인 개념이다. 추가로 Heap(힙)에 대해서 알아보자!

👋 이 포스팅은 복습하려고 쓰는 것이기에 개념을 다지기엔 괜찮을지 몰라도, 더 깊은 내용을 알기에 적합하지 않는 포스팅 입니다!

 

Stack

스택의 특징을 우선적으로 들어보자면

1. 메모리 크기가 정해져있다 (정적이다.) 추가는 ⭕️, 메모리가 줄어들진 않는다.
2. 입구와 출구가 나눠져있지 않다.
3. 메모리 부족 할 수도
4. int, boolean, double

'쌓는다'의 의미를 가짐 이는 곧 데 이터를 차곡차곡 쌓아올린 형태의 자료이다. 아래 나올 Heap과 비교했을 때 빠르다.

👽책상에 쌓아둔 책이나 주방에 쌓아둔 접시를 예로 든다.

스택은 후입선출(Last-In First-Out, LIFO) 혹은 (First-In Last-Out, FILO)로 이는 "마지막에 들어온 것이 먼저 나간다. 입출구가 하나 밖에 없는 입구와 출구가 같은" 자료 구조 라고 한다.

데이터의 삽입과 삭제가 한 방향에서만 이뤄지는 것으로 스택에서는 흔히 데이터의 삽입 연산을 push, 삭제 연산을 pop이라고 칭한다. 출입구가 같으니 삽입과 삭제가 일어나는 위치(top)는 하나이다.

👽브라우저에서 뒤로가기를 하거나, 문서작업에서 컨트롤 Z를 한 경우 처럼 이전 상태로 되돌리는 캐시 같은 느낌.

스택 언더플로우 & 스택 오벌플로우

• stack overflow : 요소를 전체 스택으로 push하려는 경우, 스택 메모리보다 데이터를 더 넣었을 때 발생하는 에러이다.
• stack underflow : 빈 스택에서 요소를 pop하려는 경우

 

Queue

큐의 특징은?

1. 순서를 가지고 있다. 먼저 들어온 것이 먼저 나간다.
2. 시간순/입력순으로 처리해야 할때
3. 입구와 출구가 나누어져있다.

스택과 비슷하지만 스택의 반대의 개념이다. 스택은 후입선출 구조를 가졌었지만, 큐는 선입선출 구조를 가진다(First-in Frist-out, FIFO) 먼저 들어온 것이 먼저 나가는 구조이다. 삽입 연산을 enQueue 라고 하며, 삭제 연산을 deQueue라고 한다. FIFO구조를 실현하기 위해 입구와 출구가 나뉘어져있다. 출구는 front라고 하고 입구는 rear라고 한다.

👽콜센터 대기순

 

Heap

Heap의 특징

1. 트리구조를 가졌다.
2. 데이터 외에 다른 형태의 데이터를 관리하기 위한 빈 공간으로 힙의 메모리 영역은 스택 참조 형식이다.
   메모리가 정적이지 않고 동적이다.
3. 메모리 크기가 유동적으로 변할 수 있어 효율적이다. Stack의 주소를 거쳐야해서 상대적으로 느리다.
4. 메모리 조각화
5. String, Object, Array

전역변수를 저장하기 위해 사용하며, 모든 전역변수는 힙 메모리 공간에 저장된다. 메모리가 할당이 동적이기 때문에 사용자 관리가 가능하다. 스택과 다르게 자동으로 관리되지 않아 CPU에 엄격하지 않다. 위에서 스택은 빠르다고 했는데 힙은 스택 주소를 거쳐가기 때문에 느리다.

 

그래서 언제 사용하는데?

큰 구조 상대적으로 작은 변수일 땐, 함수 블록 안에서만 사용하면 되니까 Stack, 큰 메모리 블록을 할당해야하는 경우 Heap을 사용하자!

 

그러면, 메모리 조각화는 뭐야?

스택은 차곡차곡 쌓인다. 반면 힙은 뭉탱이로 랜덤으로 차지한다. 스택 바로 뒤에 힙이 할당되지 않고 뭉탱이로 충분한 공간에 주는데, 그 사이에 남은 메모리는 스택이 쓰기도 힙이 쓰기도 모호한 크기라, 사이사이에 남아버린 것들이 많아져서 메모리를 쓰진 않지만, 못쓰는게 메모리 조각화이다.

현대에 이르러 메모리 크기가 커졌기에 메모리 누수는 신경써도 조각화를 잘 신경쓰지 않는다.

 

추가로 공부해야 할 것

• [ ] concat 메모리 정적할당
• [ ] StringBuffer, StringBuilder 동적할당

 

혼자 끄적인 것

가비지 콜렉터 (메모리 누수/조각화)

이 경우 4K에 3K를 넣으면 1K가 남으니까 남는 공간에 1K를 넣는 걸 내부 단편화라고 하는게 맞는가? = 통합기법이라고 한다. 그러면 조각화된 부분 사용하면 되는거 아닌가?

• 통합기법은 근접한 애들 합치는거고
• 압축기법은 기억장소 재배치해서 사용하는 것. 큰 빈 공간 확보

Q. 안쓰는 메모리 잘 활용해보자 이런 느낌인거 알겠는데 얘랑 조각화랑 뭔 차이예요? : 메모리 조각화 또는 단편화 같은 말.

 

그럼 왜 C++은 빠르고

자바나 C#은 느릴까?

• C++의 경우에는 가비지가 없어 개발자가 일일이 메모리 조작을 해줘야한다.

 

여기서 그럼 리소스란 뭐야?

리소스 = 자원으로 사용이 가능한 어떤 항목을 이야기 한다. 프로그램이 무겁다라고 표현하는 프로그램은 실행하는데 많은 리소스가 필요한 프로그램이다. 반대로 프로그램이 가볍다는 것은 리소스를 작게 차지하는 프로그램이다.