스택이란?
-
LIFO(Last In First Out)으로 마지막으로 입력된 자료가 먼저 출력되는 자료구조
-
함수 콜스택, 역순 출력 등에 활용된다.
-
push : 데이터 삽입
-
pop : 데이터 최상위 값 뺌
-
peek : 데이터 최상위 값 조회
-
isFull : 가득 차있는지 여부
-
isEmpty : 비어있는지 여부
Array로 구현한 스택
- 구현
스택의 크기인 stackSize 만큼 배열을 생성하고.
가장 바깥 인덱스를 top으로 두어, arr[top]에서 삽입 삭제가 일어나도록 하였다.
- 한계
스택의 크기가 한정적이라 스택의 크기를 초과하는 수의 원소가 들어오면 에러가 출력된다.
LinkedList로 구현한 스택
- 구현
data와 next Node를 갖는 클래스 Node를 생성하였다.
Stack 생성시 초기 head와 top을 null로 둔다.
이 때 head는 stack 바닥 노드를, top 은 스택 최상위 노드를 의미한다.
원소가 생성될 때 마다 새로 data를 넣은 node를 생성하여, top의 next로 이어주고 top을 갱신한다.
원소 삭제시 head 부터 탐색해 top 직전 노드를 찾고, top을 제거한다.
유동적인 크기의 stack을 갖는 장점이 있으나, pop의 시간복잡도가 O(N)이다.
Example
0 1 2 3 4 순으로 push 후 pop을 진행하자, 늦게 삽입한 4부터 pop이 되는 것을 확인할 수 있다.
라이브러리 사용
java의 util 패키지에서 stack클래스를 제공한다.
push와 pop으로 삽입삭제가 가능하다.
