#. 스택(Stack)
##1. 스택(Stack)이란?
스택은 LIFO(Last In First Out) 원칙을 따르는 자료구조이다.
즉, 가장 마지막에 들어온 데이터가 가장 먼저 나가는 구조를 가진다. 생활에서 책을 쌓아두는 모습이나, 식당에서 접시를 쌓아두는 것을 생각하면 이해하기 쉽다.
##2. 스택의 특징
-
데이터의 삽입과 삭제가 한 방향(스택의 맨 위 혹은 맨 아래)에서만 일어난다.
-
데이터의 입력 순서를 유지한다.
들어온 순서대로 데이터가 쌓이고, 마지막에 들어온 데이터부터 차례대로 나간다.
##3. 스택의 장점과 단점
###3.1 장점
데이터의 삽입과 삭제가 맨 위에서만 이루어지므로 구현이 간단하고, 데이터를 관리하기 쉽다.
###3.2 단점
스택의 크기가 정해져 있으면,
그 크기를 초과하는 데이터를 삽입하려하면 스택 오버플로우(Overflow)가 발생할 수 있다.
반면, 스택이 비어있는 상태에서 데이터를 꺼내려고 하면 스택 언더플로우(Underflow)가 발생합니다.
오버플로우(Overflow) : 스택이 완전히 꽉 찬 상태
언더플로우(Underflow) : 스택이 완전히 비어 있는 상태
##4. 스택의 추상자료형
###4.1 Top/Peek (스택 포인터)
스택의 맨 위의 데이터를 조회하는 연산이다.
###4.2 isEmpty
스택이 비어있는지 확인하는 연산이다.
###4.3 isFull
스택이 가득 차 있는지 확인하는 연산이다.
###4.4 getSize
스택에 있는 요소 수를 반환하는 연산이다.
###4.5 Push
스택의 맨 위에 데이터를 추가하는 연산이다.
이미지 출처
push의 단계를 간단하게 설명하자면, 아래와 같이 정리할 수 있다.
① : isFull을 통해 스택에 데이터가 가득찼는지 확인 후 가득 차지 않았다면
② : Top(스택 포인터)을 다음 위치로 이동시킨다.
③ : 이동한 Top(스택 포인터) 위치에 데이터를 저장한다.
###4.6 Pop
스택의 맨 위에서 데이터를 제거하고, 그 데이터를 반환하는 연산이다.
이미지 출처
Pop의 단계를 간단하게 설명하자면, 아래와 같이 정리할 수 있다.
① : isEmpty을 통해 스택에 데이터가 존재하는지 확인 후 존재 한다면
② : Top(스택 포인터)이 가리키는 데이터를 반환한다.
③ : Top(스택 포인터)을 이전 위치로 이동한다.
##5. 스택의 시간복잡도
스택의 주요 연산인 Push(삽입)과 Pop(삭제) 모두 데이터의 개수에 상관없이 맨 위에서 연산이 이루어지므로 O(1)의 시간복잡도를 가진다.
##6. 스택의 사용
###6.1 프로그램 실행 시 메모리 구조
컴퓨터에서 프로그램을 실행할 때, 메모리에서 스택 영역은 함수의 호출과 관련된 지역 변수, 매개 변수, 반환 값 등을 저장하는 데 사용된다. 이는 함수의 실행을 관리하는 데 필수적인 역할을 한다.
###6.2 컴퓨터의 히스토리 관리
웹 브라우저에서 뒤로 가기 기능을 구현할 때 스택이 사용된다.
방문한 웹 페이지의 URL을 스택에 푸시하고, 사용자가 뒤로 가기를 누르면 팝하여 이전 페이지로 이동한다.
###6.3 문자열 역순 출력
문자열을 역순으로 출력하는 데 스택을 사용할 수 있다.
문자열의 각 문자를 스택에 푸시하고, 팝하여 문자열을 역순으로 만들 수 있다.
###6.4 괄호 검사
프로그래밍에서 괄호가 올바르게 닫혀 있는지 검사하는 데 스택을 사용할 수 있다.
여는 괄호를 만나면 스택에 푸시하고, 닫는 괄호를 만나면 스택에서 팝하여 괄호를 검사한다.
References
