반응형
Stack 이란?
Stack 의 사전적 의미는 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있다. 마치 접시를 쌓아놓은 형태와 비슷한 자료구조로 직역 그대로, 데이터를 순서대로 쌓는 자료구조이다. Stack의 특징은 아래와 같다.
- 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근에 있다.
- 이런 Stack 자료 구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out) 이라고 한다.
- Stack에 데이터를 넣는 것을 Push, 데이터를 꺼내는 것을 Pop 이라고 한다.
LIFO(Last In First Out)
먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조를 가지고 있다.
예1) 1, 2, 3, 4를 스택에 차례대로 넣습니다.
Stack<Integer> stack = new Stack<>(); //Integer형 스택 선언
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
---------------------------
1 <- 2 <- 3 <- 4
---------------------------
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.
예2) 스택이 빌 때까지 데이터를 전부 빼냅니다.
stack.pop();
stack.pop();
stack.pop();
stack.pop();
---------------------------
---------------------------
4, 3, 2, 1
제일 마지막에 있는 데이터부터 차례대로 나오게 됩니다.
예3) 스택이 비어 있는지 확인할 때는 empty 연산을 사용합니다.
stack.empty(); // true 반환
Stack 자료구조 특징
데이터가 아무리 많이 있어도 하나씩 데이터를 넣고 뺀다. 한꺼번에 여러 개를 넣거나 뺄 수 없다. 또한 데이터 입출력 방향이 같다.
Stack 자료 구조의 장점
- 스택은 후입선출(LIFO)구조를 가지기 때문에 스택에 저장된 데이터를 가져오는 속도가 매우 빠르다.
스택은 후입선출 구조를 가지고 있기 때문에 삽입과 삭제가 항상 스택의 맨 위에서 이루어진다. 따라서 스택에서 데이터를 삽입하거나 삭제할 때 다른 데이터의 위치를 변경할 필요가 없다. 예를 들어 스택에서 삽입 연산을 수행하면, 새로운 데이터는 스택의 맨 위에 추가된다. 스택의 다른 데이터들은 그대로 놔둔 채로 새로운 데이터가 맨 위에 추가된다. 이와 마찬가지로 스택에서 삭제 연산을 수행하면 맨 위에 있는 데이터가 삭제되고, 다른 데이터의 위치는 변경되지 않는다. 이 과정은 스택의 크기와는 상관 없이 항상 매우 빠르게 처리된다. 데이터를 삽입, 삭제하는 모든 데이터를 순회할 필요가 없기 때문이다. - 자바에서는 스택을 기본 자료 구조로 제공하기 때문에 별도의 라이브러리나 모듈을 설치할 필요가 없다.
자바에서 따로 스택을 구현하지 않아도 이미 Stack 클래스가 구현되어 있다. 자료 구조의 특징과 메서드를 활용할 수 있다면 구현된 Stack 클래스를 바로 사용할 수 있다.
Stack<Integer> stack = new Stack<>(); //Integer 타입을 요소로 가지는 스택 선언
stack.push(1); // 스택에 새로운 데이터를 추가할 때는 push 연산을 사용합니다.
---------------------------
stack -> [1]
---------------------------
stack.push(2);
---------------------------
stack -> [1, 2]
---------------------------
stack.push(3);
---------------------------
stack -> [1, 2, 3]
---------------------------
stack.pop(); // 스택에서 가장 위에 있는 데이터를 제거할 때는 pop 연산을 사용합니다.
---------------------------
stack -> [1, 2]
---------------------------
stack.pop();
---------------------------
stack -> [1]
---------------------------반응형
Stack 자료 구조의 단점
- 크기 제한이 없다.
스택은 데이터를 저장할 때 크기가 제한되지 않기 대문에 메모리 사용량을 불필요하게 증가시킬 수 있다. 이러한 문제를 해결하기 위해 스택의 크기를 미리 정해놓거나, 동적으로 크기를 조절하는 방법을 사용해야 한다. - Stack 클래스는 Vector 클래스를 상속받아 구현되어 있어, 크기를 동적으로 조정하지 않는다.
Vector 클래스는 내부적으로 배열을 사용하여 구현되어 있다. 이 배열의 크기는 처음 지정된 크기만큼 할당되고, 스택에 저장되는 데이터의 개수가 배열의 크기를 초과하면 새로운 배열을 할당하고, 기존 데이터를 새로운 배열로 복사하는 작업을 수행한다. 이 작업은 성능에 영향을 미치기 때문에 크기가 자주 변하는 스택에서는 다른 자료 구조를 사용하는 것이 더 효율적일 수 있다. 아래는 Vector 클래스의 생성자 코드이다.
public Vector(Collection<? extends E> c) {
Object[] a = c.toArray();
elementCount = a.length;
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, elementCount, Object[].class);
}
}- Stack 클래스는 Vector 클래스를 상속받아 구현되어 있어 중간에서 데이터를 삽입, 삭제할 수 있게 된다.
Stack 클래스는 Vector 클래스를 상속받아 구현되어 있어 Vector 클래스의 모든 메서드를 상속받아 사용할 수 있다. 하지만 Stack 클래스에서는 Vector 클래스에서 상속받은 메서드 중에서 일부 메서드를 오버라이딩하여 구현하고 있다. 이러한 구현 방식은 스택의 의도된 동작을 방해할 수 있기 때문에 해당 클래스를 사용할 때 주의가 필요하다.
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.get(1); // 특정 인덱스 원소 찾기
stack.set(1, 1); // 특정 인덱스에 원소 넣기
stack.remove(1); // 특정 인덱스 원소를 삭제
Stack의 실사용 예제
Stack이 사용되는 대표적인 예로 브러우저의 뒤로가기, 앞으로 가기 기능을 구현하기 위해 Stack이 활용된다. 브라우저에서 자료 구조 Stack이 사용될 때에는 다음과 같은 순서를 거친다.
- 새로운 페이지로 접속할 때 현재 페이지를 Prev Stack에 보관한다.
- 뒤로가기 버튼을 눌러 이전 페이지로 돌아갈 때에는 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져온다.
- 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때에넌 Next Stack의 가장 마지막으로 보관된 페이지를 가져온다.
- 마지막으로 현재 페이지를 Prev Stack에 보관한다.
반응형