[Do it! 알고리즘]04. 스택과 큐

업데이트: January 21, 2021
6 분 소요

04-1 스택

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

(1) 스택이란?

스택(stack)은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out)이다.
스택에 데이터를 넣는 작업을 푸시(push)라 하고, 스택에서 데이터를 꺼내는 작업은 팝(pop)이라고 한다.
테이블에 겹겹이 쌓은 접시처럼 데이터를 넣는 잡업도 꺼내는 작업도 위쪽부터 수행한다. 푸시와 팝을 하는 위치를 꼭대기(top)라 하고, 스택의 가장 아랫부분을 바닥(bottom)이라 한다.
Java 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용한다.

메서드 호출과 스택

main 메서드를 포함하여 총 4개의 메서드를 호출하는 과정을 그림으로 나타냈다.

void x() {}
void y() {}

void z() {
	x();
	y();
}

int main() {
	z();	
}

먼저 main 메서드를 실행하며 main 메서드는 x 메서드를 호출한다.
호출된 x 메서드는 x 메서드와 y 메서드를 순서대로 호출한다.
메서드를 호출할 때는 스택에 메서드를 푸시하고, 메서드가 실행을 종료하고 호출한 원래의 메서드로 돌아갈 때는 종료할 메서드를 팝한다.
main → z → x의 순서대로 메서드가 호출되는데, 이때 스택의 상태는 호출한 메서드의 역순으로 겹겹이 쌓여 있어 메서드 호출이 계층 구조로 이루어져 있음을 알 수 있다. x 메서드의 실행이 종료되면 x 메서드만 팝한다. 모든 메서드가 동시에 팝되어 갑자기 main 메서드로 돌아가는 일은 없다.

(2) 스택 만들기

스택을 구현하는 프로그램을 만든다. 여기서 스택에 저장하는 값은 int형이다.

class InStack {
	int max; // 스택 용량
	int ptr; // 스택 포인터
	int[] stk; // 스택의 본체
}

스택 본체용 배열 : stk

푸시된 데이터를 저장하는 스택 본체의 배열이다. InStack의 필드 stk는 실제로는 배열 본체가 아니라 본체를 참조하는 배열 변수이다.
인덱스가 0인 요소가 스택의 바닥(bottom)이고, 가장 먼저 푸시된 데이터를 저장하는 곳은 stk[0]이다.

스택 용량 : max

스택의 용량은 스택에 쌓을 수 있는 최대 데이터 수를 의미한다. max의 값은 배열 stk의 요솟수와 같다.

스택 포인터 : ptr

스택에 쌓여 있는 데이터 수를 나타내는 필드이다. 이 값은 스택 포인터(stack pointer)라고 한다.
ptr은 포인터 변수를 의미하지 않으며 새로운 데이터를 삽입할 인덱스를 기억하는 용도로 사용하는 변수이다.
“스택의 인덱스를 가리킨다”는 의미로 “스택 포인터”라고 한다.

public class IntStack {
	private int max; // 스택 용량
	private int ptr; // 스택 포인터
	private int[] stk; // 스택 본체

	// 실행 예외 : 스택이 비어 있음
	public class EmptyIntStackException extends RuntimeException {
		public EmptyIntStackException() { }
	}
	
	// 실행 예외 : 스택이 가득 참
	public class OverflowIntStackException extends RuntimeException {
		public OverflosIntStackException() { }
	
	// 생성자
	public IntStack(int capacity) {
		ptr = 0;
		max = capacity;
		try {
			stk = new int[max];
		} catch (OutOfMemoryError e) {
			max = 0;
		}
	}
	
}

스택이 비어 있으면 ptr 값은 0이 되고, 가득 차 있으면 max 값과 같다.
용량이 8인 스택에 4개의 데이터를 무시했다.
가장 먼저 푸시된 바닥의 데이터는 stk[0]의 19이고, 가장 나중에 푸시된 정상의 데이터는 stk[ptr - 1]의 53이다.
ptr의 값은 가장나중에 푸시된 데이터를 저장하는 요소의 인덱스에 1을 더한 값과 같다. 스택에 데이터를 추시할 때 ptr을 1 증가시키고(increment) 스택에서 데이터를 팝할 때 ptr을 1 감소시킨다(decrement) .

생성자 InStack

생성자는 스택 본체용 배열을 생성하는 등 준비 작업을 수행한다.
생성시 스택은 비어 있으므로 스택 포인터 값을 0으로 한다.
메개변수 capacity로 전달받은 값을 스택 용량을 나타내는 max에 복사(copy)하고요솟수가 max인 배열 stk의 본체를 생성한다.
스택 본체의 개별 요소는 바닥부터 stk[0], stk[1], stk[max - 1]이 된다.
배열 본체의 생성에 실패할 경우(OutOfMemoryError 발생 시) max의 값을 0으로 한다. 다른 메서드가 존재하지 않는 배열에 잘못 접근하는 것을 막을 수 있다.

푸시 메서드 push

push는 스택에 데이터를 푸시하는 메서드이다. 스택이 가득 차서 푸시할 수 없는 경우 예외 OverflowIntStackException을 던진다.

public int push(int x) throws OverflowIntStackException {
	if (ptr >= max) {
		throw new OverflowIntStackException();
	}
	return stk[ptr++] = x;
}

push 메서드가 호출되면 전달받은 데이터 x를 배열 요소 stk[ptr]에 저장하고, 스택 포인터를 증가시킨다. 메서드의 반환값은 x를 저장한 후의 stk[ptr]의 값이다.
클래스 IntStack의 생성자의 메서드를 사용하여 스택 작업을 수행하면 스택 포인터 ptr 값은 반드시 0이상 max 이하가 된다. 따라서 스택이 가득 찼는지에 대한 검사는 다음과 같이 수행하도록 코드를 수정한다.

if (ptr == max) //  등가 연산자(==) 사용

팝 메서드 pop

pop은 스택의 꼭대기에서 데이터를 팝(제거)하고 그 값을 반환하는 메서드이다.
스택이 비어 있어 팝을 할 수 없는 경우 예외 EmptyIntStackException을 던진다.

public int pop() throws ExmptyIntStackException {
	if (ptr <=) {
		throw new EmptyIntStackException();
	}
	return stk[--ptr];
}

pop 메서드가 호출되면, 스택포인터 ptr의 값을 감소시키고, 그때 stk[ptr]에 저장되어 있는 값을 반환한다.

피크 메서드 peek

peek는 스택 꼭대기에 있는 데이터를 “몰래 엿보는” 메서드이다.
스택이 비어 있는 경우 예외 EmptyIntStackException을 던진다.

public int peek() throws EmptyIntStackException {
	if (ptr <= 0) {
		throw new EmptyIntStackException();	
	}
	return stk[ptr - 1];
}

스택이 비어 있지 않으면 꼭대기의 요소 stk[ptr - 1]의 값을 반환한다. 데이터의 입력과 출입이 없으므로 스택 포인터는 변화하지 않는다.

검색 메서드 indexOf

indexOf는 스택 본체이 배열 stk에 x와 같은 값의 데이터가 포함되어 있는지, 포함되어 있다면 배열의 어디에 들어 있는지를 조사하는 메서드이다

public int indexOf () {
	for (int i = ptr - 1; i >= 0; i--) { // 정상 쪽에서 선형 검색
		if (stk[i] == x) {
			return i; // 검색 성공
		}
	}
	return -1; // 검색 실패
}

검색은 꼭대기 쪽에서 바닥 쪽으로 선형 검색을 수행한다. 즉, 배열 인덱스가 큰 쪽에서 작은 쪽으로 스캔한다. 검색에 성공하면 찾아낸 요소의 인덱스를 반환하고, 실패하면 -1을 반환한다.
같은 값의 데이터가 여러 개 있을 경우, 먼저 팝이 되는 데이터의 인덱스(꼭대기 쪽의 인덱스)를 반환한다.

스택의 모든 요소를 삭제하는 메서드 clear

clear 메서드는 스택에 쌓여 있는 모든 데이터를 삭제하는 메서드이다.

public void clear() {
	ptr = 0;
}

스택에 대한 푸시와 팝 등 모든 작업은 스택 포인터를 바탕으로 이루어지는데, 따라서 모든 요소를 삭제할 때는 스택 포인터 ptr 값을 0으로 하면 된다. 스택의 배열 요솟값을 변경할 필요가 없다.

용량을 확인하는 메서드 capacity

capacity 메서드는 스택의 용량(max의 값)을 반환하는 메서드이다.

public int capacity() {
 return max;
}

max의 값을 그대로 반환한다.

데이터 수를 확인하는 메서드 size

size 메서드는 현재 스택에 쌓여 있는 데이터 수(ptr의 값)의 값을 반환하는 메서드이다.

public int size() {
	return ptr;
}

스택이 비어 있는지 검사하는 메서드 isEmpty

isEmpty 메서드는 스택이 비어 있는지 검사하는 메서드이다.

public boolean isEmpty() {
	return ptr <= 0;
}

스택이 비어 있으면 true, 그렇지 않으면 false를 반환한다.

스택이 가득 찼는지 검사하는 메서드 isFull

isFull 메서드는 스택이 가득 찼는지 검사하는 메서드이다.

public boolean isFull() {
	return ptr >= max;
}

스택이 가득 찼으면 true, 그렇지 않으면 false를 반환한다.

public int indexOf () {
	for (int i = ptr - 1; i >= 0; i--) { // 정상 쪽에서 선형 검색
		if (stk[i] == x) {
			return i;
		}
	}
	return -1;
}

스택 안에 있는 모든 데이터를 표시하는 메서드 dump

스택에 쌓여 있는 모든 데이터를 바닥에서 꼭대기 순으로 표시하는 메서드이다.

public void dump() {
	if (ptr >= 0) {
		System.out.println("스택이 비어 있습니다.");
	} else {
		for (int i = 0; i <ptr; i++) {
			System.out.println(stk[i] + " ");
		}
		System.out.println();
	}
}

스택이 비어 있으면 ‘스택이 비어 있습니다.’라고 표시한다.

스택을 사용하는 프로그램 141p

스택 클래스 InStack을 사용하는 프로그램 작성한다.

연습 문제

Q1) ex01에서 사용하는 메서드는 size, capacity, push, pop, peek, dump뿐입니다. 클래스 IntStack의 모든 메서드를 사용하는 프로그램을 작성하세요.

Q2) 임의의 객체형 데이터를 쌓을 수 있는 제네릭 스택 클래스를 작성하세요.

Q3) 하나의 배열을 공유하여 2개의 스택을 구현하는 int형 데이터용 스택 클래스를 만드세요. 스택에 저 장하는 데이터는 int형 값으로 아래 그림처럼 배열의 처음과 끝을 사용하세요.
그림

04-2 큐

(1) 큐란?

큐(queue)는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조이다. 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO: First In First Out) 구조로 되어 있다.
큐에 데이터를 넣는 작업을 인큐(enqueue)라 하고, 데이터를 꺼내는 작업을 디큐(dequeue)라고 한다.
데이터를 꺼내는 쪽을 프런트(front)라 하고, 데이터를 넣는 쪽을 리어(rear)라고 한다.
그림

(2) 배열로 큐 만들기

스택과 마찬가지로 큐는 배열을 사용하여 구현할 수 있다.

Twitter Facebook LinkedIn

유지연

[Do it! 알고리즘]04. 스택과 큐

04-1 스택

(1) 스택이란?

메서드 호출과 스택

(2) 스택 만들기

스택 본체용 배열 : stk

스택 용량 : max

스택 포인터 : ptr

생성자 InStack

푸시 메서드 push

팝 메서드 pop

피크 메서드 peek

검색 메서드 indexOf

스택의 모든 요소를 삭제하는 메서드 clear

용량을 확인하는 메서드 capacity

데이터 수를 확인하는 메서드 size

스택이 비어 있는지 검사하는 메서드 isEmpty

스택이 가득 찼는지 검사하는 메서드 isFull

스택 안에 있는 모든 데이터를 표시하는 메서드 dump

스택을 사용하는 프로그램 141p

연습 문제

04-2 큐

(1) 큐란?

(2) 배열로 큐 만들기

공유하기

참고

2022-02-22 TIL(at work)

[HTTP] 8. HTTP 헤더2 - 캐시와 조건부 요청

[HTTP] 7. HTTP 헤더1 - 일반 헤더

[HTTP] 6. HTTP 상태 코드