스택이란?
자료구조 중, 선형구조에 해당하는 자료구조이다.
제한적으로 접근할 수 있는 나열구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다.
끝먼저내기 목록이라고 한다. (Pushdown list)
또한, 컴퓨터에는 참조지역성이라는 것이 있습니다. 간략히 설명하자면 참조지역성은 한 번 참조된 곳은 또 참조될 확률이 굉장히 높다는 것입니다. 그 참조지역성의 원리 중에서 시간지역성의 원리라는 것이 있는데 시간지역성은 '최근' 참조된 데이터가 다시 참조될 확률이 높다는 겁니다. 스택은 그 시간지역성을 최고로 활용할 수 있는 자료구조입니다.
스택의 특징?
- 제일 위의 데이터만 알 수 있다.
- 쌓여가는 와중에도 스택에 쌓인 데이터 갯수는 알 수 있다.
- 중간의 데이터 절대 알 수 없다. 만약 알고 싶다면 제일 위부터 하나씩 꺼내보면서 확인해야한다.
- 제일 처음 들어간 데이터는 모든 데이터를 꺼내기 전까지 확인할 수 없고, 반대로 제일 마지막에 들어간 데이터는 바로 꺼낼 수 있다.
스택의 시간복잡도?
일단 대표 스택의 기능은 5가지가 있습니다.
push - 제일 마지막(위) 위치에 데이터를 삽입합니다.
-> O(1) : 제일 위에 데이터를 삽입하니 상수 시간이 나옵니다.
pop - 제일 마지막(위) 위치에서 데이터를 꺼내와서 삭제를 합니다. 즉, search + delete 입니다.
-> O(1) : 제일 위에 걸 빼니깐 상수 시간이 나옵니다.
peek - 제일 마지막(위) 데이터를 삭제만 하지 않고, 확인할 수 있습니다. search 개념
-> O(1) : 제일 위에 걸 빼니깐 상수 시간이 나옵니다.
emtpy - 스택이 비어있는지를 확인하는 함수 리턴은 boolean 입니다.
-> O(1) : Null 인지 확인만 하니, 복잡도가 1 나옵니다.
size - 스택의 크기(데이터 개수)를 확인합니다.
-> O(1) or O(n) : 스택은 배열과 리스트로 구현하여 사용할 수 있는데, 배열로 사용할 경우에는 O(1), 리스트로 사용할 경우에는 O(n)입니다.
스택 구현 방법 ( 배열 / 리스트 ) ?
배열 : 데이터 집합을 배열에 저장, Top 위치를 저장하는 멤버 필요, 생성자에서 디폴트 배열 크기를 정해준다.
리스트 : 단일 연결리스트 자체가 스택이다, 연결리스트에 저장하고 연결리스트 특성상 스택의 크기가 자유롭다.
[Java]
[참조 블로그 : https://monsieursongsong.tistory.com]
스택 메모리 구조 ?
스택은 높은 주소에서부터 낮은 주소로 흐르며, 반대로 Heap 영역은 낮은 주소에서 높은 주소로 흐르게 되는데,
이러한 이유는 운영체제의 접근 불가지역인 Kernel 영역을 절대 침범할 수 없도록 하기 위함이다.
또한, 스택과 힙이 공유 라이브러리 영역을 가운데에 두고 서로 마주보게 되어 메모리를 효율적으로 사용할 수 있다.
스택을 사용하는 곳은?
- 스택을 활용하면 "재귀함수"를 필요로하는 소스코드에 "재귀함수" 를 사용하지 않고 구현이 가능합니다.
- 웹 브라우저의 방문기록에서도 스택의 특징을 사용하여, "뒤로가기" 를 구현할 수 있습니다.
- 프로그램 실행취소(Undo)에서 활용됩니다.
- 후위표기 계산식에서 활용합니다.
- 수식의 괄호 검사 ( 연산자 우선순위 표현을 위한 괄호 검사) ex. VPS
- 부 프로그램 호출 시, 복귀주소를 저장할 경우
- 함수의 호출순서를 컨트롤 할 경우
- 인터럽트가 발생하여 복귀주소를 저장할 경우
- 자바 언어에서 JVM은 스택 기반의 가상 기계 코드로 모든 연산을 스택에서 수행 함.
안드로이드 또는 IOS 쪽,
stack을 사용하는 예로, Navigation Stack 을 들 수 있습니다.
Navigation Stack을 사용하여 다른 뷰 컨트롤러를 관리하게 됩니다.
- Push : UIViewController의 인스턴스를 생성해서 Navigation Stack을 추가함을 의미합니다.
- Pop : UIViewController를 메모리에서 해제하고, Navigation Stack에서 제거함을 의미합니다.
스택 프레임( Stack Frame )?
메모리의 스택(stack) 영역은 함수의 호출과 관계되는 지역변수와 매개변수가 저장되는 영역입니다.
스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸합니다.
함수가 호출되면, 스택에는 매개변수, 호출이 끝난 뒤 돌아갈 반환 주소값, 함수에서 선언된 지역 변수 등이 저장됩니다.
이렇게 스택 영역에 차례대로 저장되는 함수의 호출 정보를 스택프레임(Stackframe) 이라고 합니다.
스택 프레임 덕분에 함수의 호출이 모두 끝난뒤에, 해당 함수가 호출되기 이전 상태로 되돌아갈 수 있습니다.
[+Other]
스택 Overflow : 스택으로 할당받은 메모리 부분의 마지막주소가 'A' 라 할 때, 제일 위에있는 Pointer 의 주소값이 'A' 보다 커지면 스택의 모든 기억장소가 꽉 채워져 있는 상태이므로 더 이상 자료를 삽입할 수 었어, stackOverFlow를 발생 시킨다.
반대로,
스택 Underflow : 제일 위에있는 Pointer 주소값이 '0' 을 가지고 있다면 스택에는 삭제할 자료가 없으므로, stackUnderFlow를 발생시킨다.
> 즉, Stack은 기억되어 있는 자료를 삭제 시킬 때, 제일 먼저 삭제할 자료가 있는지 없는지부터 확인합니다.
스택 기본 구조?
Buffer + sfp[4byte] + ret[4byte]
1) 버퍼는 데이터가 저장되는 공간이다.
2) sfp 는 스택 베이스 값을 뜻한다. 스택 주소값을 계산할 때 현재 스택값의 기준으로 필요한 스택프레임 포인터 값을 저장 함.
-> sfp가 필요한 이유는, ebp 레지스터는 한 개이기 때문에 함수가 시작할때마다 ebp 값이 바뀌는데 그 전의 ebp 값을 스택에다가 저장해야하기 때문이다.
3. ret 는 return의 약자로 반환 주소값을 뜻한다.
-> 다음에 실행해야 하는 명령이 위치한 메모리 주소값이 ret이기 때문이다.
스택의 기본 구조가 어떻게 동작하는 지를 보기 위해서는? 어셈블리 레지스터가 뭐가 있고, 어떤 역할을 하는 지를 알아볼 필요가 있다.
[스택 관련한 레지스터]
1. ESP : 하나의 스택프레임(StackFrame)의 끝 지점 주소가 저장된다. Push/ Pop 명령어에 의해 값이 4씩 변한다.
2. EBP : 하나의 스택프레임(StackFrame)의 시작 지점 주소가 저장된다. 현재 스택프레임동안에는 절대로 값이 바뀌지 않다가, 현 재 스택 프레임이 소멸되면, 이전 스택 프레임을 가르키게 된다.
3. EIP : 다음에 실행할 명령의 주소를 가지고 있는 레지스터이다. 현재 실행하고 있는 명령어가 종료되면 EIP 레지스터에 있는 명령어 를 실행하게 된다. (EIP레지스터에는 어떤 명령어가 있냐면, 다음 CPU가 해야하는 일 메모리에 등록되어있어, 다음 명령어를 할 수 있게 한다.EIP란 무엇인가?
'CS > Datastructure & Algorithm' 카테고리의 다른 글
| 버블 정렬(Bubble sort)이란? (0) | 2022.03.13 |
|---|---|
| 그래프 탐색이란? (0) | 2022.03.11 |
| 깊이 우선 탐색(Depth-First-Search) (0) | 2022.03.11 |
| 완전탐색이란? (0) | 2022.03.08 |
| 큐(Queue) 란? (0) | 2022.03.06 |
