[펌_JAVA를 이용한 자료구조] 스택 (Stack)

참고서적 : Data Structures & Other Objects Using JAVA

강좌를 시작하며

안녕하세요. 이번 강좌에서는 Stack에 대해서 공부해 보도록 하겠습니다. 이번 강좌를 잘 이해하시면 나중에 배우실 Recursive(재귀)호출에 많은 도움이 되실 듯 하네요. 시스템 내부적으로도 스택이라는 구조는 많이 쓰이고 있기 때문에, 굳이 자료구조에 한하는 내용이라 생각치 마시고, 여러 방면에서 두루 쓰이는 구조임을 알아두시고 보시면 많은 도움이 될 것 같습니다.

Stack 이란

Stack이란 "어떠한 자료들(숫자, 문자, 문자열, 신상명세 등...)을 일정한 규칙에 의해서 모아놓은 것" 이라고 말할 수 있습니다. 추가와 삭제가 가능합니다. 하지만 위에서 방금 말씀드린것과 같이 일정한 규칙 이라는게 존재하죠. 그 규칙은 바로 맨 위에서만 추가, 삭제가 가능하다는 것입니다. LIFO(Last In First Out) 라고도 합니다. 말그대로 풀어보자면, '마지막으로 들어간 것이 가장 먼저 나온다' 정도 일까요?


[그림 1] Stack

Stack을 도식화 해보면 위와 같은 모양으로 생각할 수 있습니다. 층의 개념이 있는 '통' 이라고 할까요? 한 층에는 하나의 원소만이 들어갈 수 있습니다.

만약에 여러분들이 Element 6을 Stack에 넣으려고 한다고 가정해 보겠습니다. 한번에 Stack의 맨 밑에 넣으실 수 있을까요? 불가능하죠. Element 1, 2, 3, 4, 5를 다 꺼내고서야 Element 6을 맨 밑에 넣을수 있겠죠. 이처럼 원소를 Stack에 추가할 때는 Stack의 맨 위에만 넣을 수 있습니다. 이 동작을 push라고 부릅니다.

이번엔 여러분들이 Element 2를 꺼내려고 합니다. 한번에 꺼낼 수 있을까요? 무리죠. Element 5, 4, 3을 꺼내고 나서야 Element 2를 꺼낼 수 있죠. 하지만 Element 5를 꺼내려면 한번이면 되겠죠. 추가와 같이 Stack에서 한 원소를 빼내려면 맨 위에서 빼 내야만 합니다. 맨 위의 원소가 아니라면 여러번의 작업이 필요하겠죠.

맨 처음 집어넣은 Element 1이 가장 나중에 나오게 됩니다. 반면에 가장 나중에 넣은 Element 5가 가장 먼저 나오게 되겠죠? 이게 바로 LIFO 랍니다.

Array로 Stack 구현

Stack을 Java로 구현하려면 두가지 방법이 있습니다. 이번 강좌의 목차처럼 Array를 이용하는 방법과, Linked List를 이용하는 방법이죠. 이 강좌에서는 Array를 이용하여 정수를 넣을 수 있는 Stack을 구현을 해 보겠습니다.

Stack의 기능들은 5가지 정도가 있습니다. push(), pop(), peek(), is_empty(), is_full()이 바로 그것이죠. 하나하나 차례대로 작성해 보겠습니다.

일단 Stack의 클래스를 만들고 그 안에 들어갈 멤버 변수들을 생각해 볼까요. Stack에는 꼭 필요한 변수가 하나 있습니다. top 이라는 변수로써 stack의 맨 위를 가리키고 있지요. 배열로 구현한다는 전제조건 하에 top은 stack이 비어 있을 때는 -1의 값을 가지게 됩니다.

class integer_stack {     private int[] data;     private int top;     private int many_items;     private int stack_size; }

위와 같은 변수들이 필요합니다. data라는 정수형 배열이 보이죠. 이 배열을 이용하여 자료들을 저장하게 됩니다. 구조는 당연히 Stack 이구요. top는 위에서 설명 드렸죠. many_items 는 현재 Stack에 몇 개의 원소가 있는지를 저장해놓은 변수이구요, stack_size 는 Stack의 전체 크기를 나타냅니다.

이 클래스의 인스턴스를 이용하여 Stack을 만들게 됩니다. 이제 생성자를 한번 살펴보죠.

integer_stack(int size) {     data = new int[size];     stack_size = size;     top = -1;     many_items = 0; }

Stack의 인스턴스가 생성 될 때 해주는 작업이므로 여러 가지 초기화 루틴들이 들어가게 됩니다. 생성자는 하나의 정수형 인자를 받게되며 그 인자는 Stack의 크기를 나타냅니다.

push() 함수를 작성해 보겠습니다. 작성하기 전에 하나 알아놓아야 할것은, push()는 Stack의 맨 위에 쌓아놓을 수 있다는 것이죠.

public void push(int number) {     data[++top] = number;     many_items++; }

data배열에 숫자를 집어넣게 되죠. ++top연산을 통해서 top은 push 함수를 호출할 때마다 하나씩 위로 올라가서 Stack의 맨 위를 언제나 가리키게 됩니다. 배열로 구현을 했으니 제일 나중에 집어넣은 원소의 Index를 보유하고 있게 되겠죠.

그 다음은 pop() 함수입니다. 이 함수 역시 맨 위에서만 빼낼 수 있다는것만 아시면 됩니다.

public int pop() {     many_items--;     return data[top--]; }

pop를 하면 Stack의 맨 위에 있는 원소가 하나 튀어나오게 됩니다. 위의 코드에서인덱스에 top--를 이용했는데 만약에 top-- 가 아닌 --top로 하면 어떻게 될까요? 맨위의 원소가 튀어나오는게 아니고, 맨위의 바로 밑에 있는 어떠한 원소가 튀어나오게 되겠죠? --를 앞에다 붙이느냐 뒤에다 붙이느냐가 중요합니다. 초보자분들은 자주 하는 실수중에 하나죠.

다음은 peek() 함수입니다. pop 함수와 매우 유사합니다. 하지만 pop 함수와 다른점은 맨위에 뭐가 있는지 보기만 한다는 것이죠. pop 함수는 아예 빼내게 되죠. 하지만 peek 함수는 보기만 하기 때문에, Stack에 있는 원소의 갯수에 영향을 미치지 않습니다.

public int peek() {     return data[top]; }

몇줄 되지도 않죠? pop함수의 코드와 비교해서 보시면 어디가 어떻게 틀린지 금방 눈에 들어오시게 될 것입니다.

다음은 is_empty() 함수입니다. 이 함수는 Stack이 현재 비어있는지 아닌지를 검사하는 함수입니다. 알아보는 방법으로는 top값을 검사하는 방법과, many_items 변수를 검사하는 방법이 있겠죠. Stack에서는 top이라는 변수가 꼭 필요하므로 top를 이용해서 검사하는게 일반적인 방법입니다. 하지만 이 스택에서는 many_items라는 변수를 사용하기로 했으므로 그것을 이용하여 작성해 보겠습니다.

public boolean is_empty() {     if( many_items == 0 )       return true;     else       return false; }

true 또는 false를 반환하게 됩니다. top이 -1이면 Stack이 빈 것이고 아니면 Stack이 빈게 아니고 원소가 하나라도 있는 것이 되겠죠?

마지막으로 is_full() 함수입니다. is_empty 함수는 Stack 이 비었는지를 검사하지만 is_full 함수는 Stack이 꽉 차 있는지를 검사합니다. 멤버 변수중에 stack_size와 top 변수를 이용하여 알아보면 됩니다. top은 배열의 인덱스를 가리키고 있으므로 적절히 변형하여 서로를 비교해보면 꽉차 있는지 여부를 판별할 수 있게 되겠죠?

public boolean is_full() {     if( many_items == stack_size )       return true;     else       return false; }

이렇게 몇가지의 함수만 작성해 주면 Stack클래스의 인스턴스를 가지고 얼마든지 Stack을 주무를 수 있습니다. 독자여러분들도 눈으로만 익히지는 마시구요, 귀찮아도 직접 해보시면 도움이 될 것입니다.

강좌를 마치며...

이번 강좌에서는 Stack에 대하여 알아보았습니다. Array를 이용하여 Stack을 구현을 해봤습니다. 앞에서도 말씀드렸듯이 Linked List로도 물론 구현이 가능합다. Array로 짠 스택은 코드가 간단하고 보기 쉬워서 간단한 스택에는 좋지만, 사이즈가 정적이라서 스택의 전체 사이즈를 변경하려면 사이즈가 다른 객체를 따로 생성해야 한다는 문제점이 있습니다. 하지만 Linked List로 Stack을 구현하면 크기가 동적으로 조절을 할 수 있게 됩니다. 원소의 갯수에 따라서 스택의 전체 크기는 계속해서 변하게 되겠죠.

그리고 9회에서 배우게될 Recursion(재귀)을 이해하시는데 Stack이 큰 도움이 될 것입니다. 자세한건 Recursion편에서 얘기 하도록 하겠습니다. 쉬운 강좌였지만 개념 정도는 머리에 익혀두시길 바랍니다. 그럼 독자분들 좋은하루 되시구요, 다음 강좌때 뵙도록 하겠습니다.