스택 개념을 이해하고, 이를 바탕으로 스택의 ADT를 작성하고 구현해봅시다. 스택을 활용해 주어진 문제도 풀어봅시다.
1. 스택 개념
스택(Stack) 어원은 ‘쌓는다’입니다. 스택은 어원에서 짐작할 수 있듯이 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조입니다. 스택은 우리 주변에서도 쉽게 찾아볼 수 있습니다. 티슈를 생각해봅시다. 티슈를 만들 때는 먼저 넣은 티슈가 가장 아래에 위치합니다. 그래서 티슈를 사용할 때는 가장 위에 있는 티슈부터 사용할 수 있죠. 이렇게 먼저 들어간 것이 마지막에 나오는 규칙을 선입후출 또는 FILO(First In Last Out)라고 합니다. 이때 스택에 삽입하는 연산을 푸시(Push), 꺼내는 연산을 팝(Pop)이라고 합니다.
1.2 스택의 동작 원리 이해하기
다음 그림을 통해 스택에서 원소가 이동하는 과정을 이해해봅시다.
01단계 초기에는 빈 스택이 있습니다.
02단계 여기에 데이터 ‘1’을 푸시해봅시다. 그럼 다음과 같을 겁니다.
03단계 그럼 여기에 데이터 ‘2’를 또 푸시하면 어떻게 될까요? ‘1’ 위로 ‘2’가 올라갑니다.
04단계 그럼 팝을 하면 어떻게 될까요? 가장 위에 있는 데이터인 ‘2’가 빠져나옵니다.
05단계 그리고 다시 데이터 ‘3’을 푸시를 하면? 다시 ‘1’위에 ‘3’이 위치하게 되었습니다.
06단계 팝을 2번 연속으로 하면 ‘3’, ‘1’ 순서로 데이터가 빠져나올 겁니다.
이를 통해 스택에서 데이터가 이동하는 원리를 잘 이해했기 바랍니다.
2. 스택의 정의
스택이 어떤 방식으로 동작하는지는 이해했을 겁니다. 이제 스택의 ADT라는 것을 정의해보고 실제 스택이 동작하는 원리를 설명하겠습니다. ADT는 우리말로 추상 자료형(Abstract Data Type)인데요. 추상 자료형이란 인터페이스만 있고 실제로 구현은 되지 않은 자료형입니다. 일종의 자료형의 설계도라고 생각하면 됩니다. 그렇다면 스택은 어떤 정의가 필요한 자료구조일까요?
※ 언어에 따라 표준 라이브러리에서 스택 제공 여부는 다릅니다. 자바는 컬렉션 프레임워크에서 Stack 클래스를 제공하기 때문에 Stack 클래스의 객체를 생성해서 사용하면 됩니다.
※ 덱(deque)은 한쪽으로만 데이터 삽입, 삭제할 수 있는 스택과 다르게 양쪽에서 데이터를 삽입하거나 삭제할 수 있는 자료구조입니다. 이런 덱의 특징을 조금만 응용하면 스택처럼 사용할 수 있습니다.
2.1 스택의 ADT
우선 스택에는 ➊ 푸시(Push), ➋ 팝(Pop), ➌ 가득 찼는지 확인(isFull), ➍ 비었는지 확인(isEmpty)과 같은 연산을 정의해야 합니다. 그리고 스택은 최근에 삽입한 데이터의 위치를 저장할 변수인 ➎ 톱(Top)도 있어야 합니다. 표와 그림으로 정리하면 다음과 같습니다.
※ 여기서는 스택의 내부 데이터를 배열로 관리하는 모습을 예로 들었습니다. 하지만 스택의 원소는 배열이 아니라 다른 자료구조로 관리할 수도 있습니다.
그림은 스택의 ADT를 나타낸 겁니다. 스택 외부와 내부에 네모 모양으로 표현한 연산과 상태가 보입니다. 그림에서는 연산 시 해야 할 동작과 상태가 가지고 있어야 할 값을 정의하고 있기는 하지만 세부 구현 내용, 즉, 프로그래밍 언어는 무엇을 사용해야 하고 데이터는 이렇게 저장해야 한다는 등의 내용은 없습니다. data 배열을 보면 최대 크기는 maxsize이므로 인덱스의 범위는 0부터 maxsize – 1입니다. top은 가장 최근에 추가한 데이터의 위치를 참조합니다. 지금 그림에서는 아무 데이터도 없으므로 top에 -1이 들어 있습니다. 만약 top이 0이면 데이터가 1개 있는 것이므로 초깃값을 0이 아니라 -1로 했음에 주목하세요.
그렇다면 우리는 스택을 공부를 할 때 ADT만 알면 되고 세부 구현은 몰라도 될까요? 사실은 세부 구현을 알아두면 도움이 됩니다. 왜냐하면 어떤 문제도 ‘스택으로 푸세요’라고 대놓고 알려주지는 않기 때문입니다. 만약 여러분이 어떤 문제를 보고 ‘스택으로 푸는 게 좋겠다’라는 생각이 떠오르려면 스택의 세부 동작을 충분히 아는 것이 좋습니다.
💡합격 조언_자료구조의 세부 동작을 공부하면 큰 도움이 됩니다
자료구조의 세부 동작을 이해하면 코딩 테스트뿐 아니라 면접에도 큰 도움이 됩니다. 왜냐하면 자료구조의 세부 동작을 공부하면 그 자료구조의 성능 및 특성을 이해하는 것이고, 이는 효율적인 알고리즘을 떠올릴 수 있게 해주기 때문입니다. 실제로 자료구조의 이해도를 요구하는 문제가 출제되기도 합니다. 꼭 한 번은 자료구조의 세부 동작을 공부하기 바랍니다.
2.2 스택 세부 동작에 대해 조금 더 자세히 알아보기
스택에 데이터를 추가하는 경우를 생각해봅시다. 이번에 설명할 내용은 이 푸시 연산을 수행할 때 스택 내부에서 일어나는 과정입니다. 그림은 push(3) 연산을 수행하며 데이터 3이 추가되는 모습을 보여줍니다.
연산 과정은 push(3)을 호출하면 내부적으로 ➊ isFull( )을 수행해 우선 data 배열에 데이터가 가득 찼는지 확인하고, ➋ 그렇지 않다면 top을 1만큼 증가시킨 후 top이 가리키는 위치 ➌ data[0]에 3을 추가합니다.
반대로 pop( ) 연산을 수행한다면 어떨까요?
그림에서 보듯 pop( ) 함수를 수행하면 내부적으로 ➊ isEmpty( ) 함수를 우선 수행해 data 배열에 데이터가 없는 건 아닌지 확인하고, 데이터가 있다면 ➋ top을 1만큼 감소시키고 ➌ 데이터 ‘3’을 반환합니다. 여기서 ‘3이 남아 있는데?’라고 생각할 수도 있습니다. 앞서 정의한 스택의 ADT에서 top은 최근에 삽입한 데이터의 위치라고 했습니다. 즉, top이 가리키는 위치는 -1이므로 실제 data 배열에 데이터가 남아 있더라도 스택은 비어 있다고 봐도 됩니다.
2.3 Stack 클래스 사용하기
코딩 테스트에서는 문제에 적용할 자료구조 혹은 알고리즘을 파악하는 능력이 중요합니다. 문제에서 의도한 데이터 흐름이 스택에 딱 맞는지 알아차리는 것이 중요하죠. 예를 들어 데이터를 그냥 저장하고 순서와 상관 없이 임의 접근하기만 해도 되면 배열을 사용하면 되지만 최근에 삽입한 데이터를 대상으로 뭔가 연산해야 한다면 스택을 떠올리는 것이 좋습니다. 본격적인 문제를 풀기 전에 앞서 자바에서 Stack을 사용하는 방법에 대해 코드로 알아보겠습니다.
Stack<Integer> stack = new Stack<>(); // 스택 객체 생성
// 스택에 데이터 푸시
stack.push(1);
stack.push(3);
// 스택이 비어 있는지 확인
System.out.println(stack.isEmpty()); // false
// 스택에서 팝
System.out.println(stack.pop()); // 3
System.out.println(stack.pop()); // 1
System.out.println(stack.isEmpty()); // true
그러나 자바의 Stack 클래스는 크기를 동적으로 관리하므로 max_size나 isFull( ) 메서드는 없습니다. 다만 size( ) 메서드를 제공하여, 스택에 들어 있는 데이터의 수를 알 수 있습니다. 또한 추가적으로 스택에서 가장 최근에 push한 데이터를 꺼내지 않으면서 반환만 하는 peek( ) 메서드를 제공합니다.
Stack<Integer> stack = new Stack<>();
stack.push(6);
stack.push(5);
// 스택에 가장 최근에 푸시한 값(peek)
System.out.println(stack.peek()); // 5
System.out.println(stack.pop()); // 5
// 스택에 들어 있는 데이터의 개수(size)
System.out.println(stack.size()); // 1
stack.push(7);
stack.push(4);
System.out.println(stack.pop()); // 4
System.out.println(stack.pop()); // 7
System.out.println(stack.pop()); // 6
System.out.println(stack.size()); // 0
스택의 개념 자체는 크게 어렵지 않으므로 비교적 쉽게 이해할 수 있습니다. 하지만 실전에 들어가 문제를 풀다 보면 스택을 몰라서 풀지 못하는 것이 아니라 ‘이 문제는 스택을 활용해야 풀 수 있다’라는 생각 자체를 못해서 풀지 못하는 경우가 대부분입니다. 따라서 스택 관련 문제를 많이 풀어보며 ‘이 문제는 스택을 사용하는 게 좋겠다’라는 감을 익히기를 권합니다.
다음편에서 계속 됩니다.
자료구조, 알고리즘, 빈출 97 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(자바 편)
저자 김희성
현 42dot 백엔드 개발자. 이전에는 삼성SDS에서 소프트웨어 개발자, 쿠팡에서 풀스택 개발자로 근무했다. 특히 삼성SDS 시절에는 사내 SW역량테스트 강사로 활약했다. 귀찮은 거 싫어하고 집에서 자는 게 가장 좋은 백엔드 개발자다. 어려운 문제와 맞닥뜨렸을 때 더욱 불타오르는 타입. 새벽 시간에 코드짜는 걸 좋아하며 주말에 밤새 코딩하는 일을 즐기는 ESTJ.
