[자바 Do It! 알고리즘]Chapter04 스택과 큐(스택)

[스택]

1. 스택은 데이터를 일시적으로 저장하기 위한 자료구조로 , 가장 나중에 넣은 데이터를 가장 먼저 꺼냅니다.

( LIFO, Last In First Out, 후입선출)

2. 스택에 데이터를 넣는 작업을 푸시 (push) 라 하고, 스택에서 데이터를 꺼내는 작업을 팝 (pop) 이라 합니다.

3. 푸시와 팝을 하는 위치를 꼭대기 (top) 라 하고, 스택의 가장 아랫부분을 바닥 (bottom) 이라 합니다.

4. Java 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용합니다.

​

<스택 만들기>

​

☞ 스택 본체용 배열 : stk

푸시된 데이터를 저장하는 스택 본체의 배열입니다.

인덱스 0인 요소가 스택의 바닥(bottom)입니다.

가장 먼저 푸시된 데이터를 저장하는 곳은 stk[0] 입니다.

☞ 스택 용량 : max

스택의 용량(스택에 쌓을 수 있는 최대 데이터 수)을 나타내는 필드입니다.

이 값은 배열 stk의 요솟수와 같습니다.

☞ 스택 포인터 : ptr

스택에 쌓여 있는 데이터 수를 나타내는 필드입니다.

이 값은 스택 포인터(stack pointer)라고 합니다.

☞ 생성자 IntStack

스택 본체용 배열을 생성하는 등 준비작업을 수행합니다.

생성 시 스택은 비어 있으므로 스택 포인터 ptr 값을 0으로 합니다.

매개변수 capacity 로 전달 받은 값은 스택 용량을 나타내는 max 에 복사하고 요솟수가 max인 배열 stk의 본체를 생성합니다.

☞ 푸시 메서드 push

스택에 데이터를 푸시하는 메서드입니다.

스택이 가득차서 푸시할 수 없는 경우 예외 OverflowIntStackException을 던집니다.

전달받은 데이터 x를 배열 요소 stk[ptr]에 저장하고, 스택 포인터를 증가시킵니다.

​

※ 클래스 IntStack의 생성자와 메서드를 사용하여 스택작업을 수행하면 스택 포인터 ptr 값은 반드시 0 이상 max 이하가 됩니다. 따라서 스택이 가득찼는지에 대한 검사는 관계 연산자(>=)가 아니라 등가 연산자(==)를 사용하여 다음과 같이 수행할 수 있습니다.

if(ptr == max)

그러나 프로그래밍 실수와 같은 원인으로 인하여 ptr 값이 잘못 입력되면 max를 초과할 수도 있습니다. 하지만 위와 같이 부등호로 판단하면 스택 본체 배열의 상한과 하한을 벗어나서 접근하는 것을 막을 수 있습니다. 간단한 코드 수정이지만 이런 노력으로 프로그램의 안정성을 높일 수 있습니다.

​

☞ 팝 메서드 pop

스택의 꼭대기에서 데이터를 팝하고 그 값을 반환하는 메서드입니다.

스택이 비어있어 팝을 할 수 없는 경우 예외 EmptyIntStackException 을 던집니다.

스택포인터 ptr의 값을 감소시키고 그 때 stk[ptr]에 저장되어 있는 값을 반환합니다.

​

☞ 피크 메서드 peek

스택의 꼭대기에 있는 데이터를 "몰래 엿보는" 메서드입니다.

스택이 비어 있는 경우 예외 EmptyIntStackException을 던집니다.

스택이 비어있지 않으면 꼭대기의 요소 stk[ptr - 1]의 값을 반환합니다.