스택이란
•
한쪽 끝에서만 데이터를 넣고 뺄 수 있는 제한적으로 접근할 수 있는 선형 자료구조
스택의 작동원리
•
스택은 후입선출(LIFO, Last In First Out) 구조로 이루어져 있다.
•
위 그림과 같이 가장 먼저 들어온 a 데이터가 가장 마지막에 쌓여있고 가장 나중에 들어온 c 데이터가 가장 위에 놓여져 있다. 데이터를 넣고 빼는 입구가 하나뿐인 스택은 가장 위에 쌓인 데이터를 먼저 꺼내도록 작동한다.
스택의 구조
•
Bottom : 가장 밑에 있는 데이터 또는 인덱스
•
Top : 가장 위에 있는 데이터 또는 인덱스
•
Capacity : 스택에 담을 수 있는 데이터의 총 용량
•
Size : 현재 스택에 담겨져있는 데이터의 갯수
스택 사용법 (java)
스택의 시간복잡도
•
삽입 및 삭제 : O(1)
◦
맨 위의 데이터를 삭제하기 때문에 늘 O(1)
•
탐색 : O(n)
◦
데이터를 찾을 때 까지 순차적으로 수행해야 하므로 O(n)
스택의 활용 사례
•
함수 호출
◦
컴퓨터 프로그램에서 함수를 호출할 때, 호출된 함수의 주소는 스택에 저장되며 함수 실행이 끝나면 스택에서 주소를 꺼내 돌아간다.
•
재귀 알고리즘
◦
재귀적으로 함수를 호출하는 경우에 임시 데이터를 스택에 넣어 주고, 빠져나와 백 트래킹을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 주는 형식으로 사용하면 된다.
•
기타 등등
◦
괄호의 짝 검사 - 괄호의 짝, 괄호의 순서 검사
◦
웹 브라우저 방문기록 - 가장 나중에 열린 페이지부터 다시 보여준다.
◦
역순 문자열 만들기 - 가장 나중에 입력된 문자부터 출력
◦
실행 취소(undo) - 가장 나중에 실행된 것부터 실행을 취소
◦
수식의 괄호 검사 - 연산자 우선순위 표현을 위한 괄호검사
스택의 구현
•
배열
◦
고정된 크기의 배열을 사용하여 스택을 구현
◦
스택의 크기가 고정되어 있어 확장이 어렵다.
•
연결 리스트
◦
동적으로 요소를 추가하고 제거할 수 있는 연결 리스트를 사용하여 스택을 구현
◦
스택의 크기가 유동적으로 변할 수 있다.
스택의 장단점
•
장점
◦
구현이 간단하고 사용하기 쉽다.
◦
함수 호출과 같은 시스템 수준의 기능을 구현하는데 필수적이다.
•
단점
◦
배열을 사용한 구현의 경우, 크기가 고정되어 있어 유연성이 떨어진다.
◦
데이터의 중간 삽입이나 삭제가 불가능하다.
그럼 더 유연성있는 연결 리스트를 사용하여 구현하는게 맞는거 아닌가?
