2주차(2) - Stack(1)

Stack

LIFO(Last In First Out)의 특성을 갖는 linear list

여기서 LIFO라는 표현은 'Last In First Out'의 줄임말로서 가장 마지막에 들어간 원소가 가장 먼저 나오는 형태의 구조를 가진 선형 자료구조를 말한다. 즉, stack은 사람들이 한 줄로만 탑승할 수 있으며, 앞문으로만 내릴 수 있는 버스를 생각하면 된다.

 

Stack에 적용하는 2가지 연산

해당 용어들은 stack에만 적용되는 전용 용어라고 봐도 무방하다.

1. push
2. pop

1. push (= insert)

stack에 한 개의 원소를 저장하는 연산

2. pop (= delete)

stack으로부터 한 개의 원소를 추출하는 연산

즉, Stack으로부터 원소를 추출하면(pop 연산), 그 원소가 가장 최근에 추가된 원소임을 보장한다.

 

구현방식

선형 리스트의 한쪽 끝위치(top)에서 push와 pop이 이루어지는 형식

stack을 유지하기 위해서는 "top"이라는 변수를 사용하게 되는 데 이 "top"을 통해서 가장 최근에 추가된 원소의 위치 또는 다음에 추가될 원소의 위치를 가리키게 되며, 이는 구현하는 방식에 따라서 적절히 선택하여 구현하면 된다.

 

(여기에 각각의 경우에 대해서 설명하는 글을 추가할 것)

 

 

stack이 실제로 사용되는 부분

실제로 프로그램을 작성하다보면 Stack이 가지는 LIFO 특성이 필요한 경우가 빈번하게 발생하게 된다. 대표적인 예시 중 하나가 바로 Function의 Call과 Return이다. 컴퓨터 내부적으로 Function Call과 Return을 구현하기 위해서는 현재 함수가 호출된 지점을 기억하는 것이 필요한데 바로 이것을 Stack을 통해서 구현할 수 있게 된다. 그래서 Function Call은 현재 위치를 Stack에 넣는 push, Function return은 가장 최근에 넣은 위치를 꺼내는 pop 연산을 의미한다.

 

이 외에도 관련된 예시들이 많이 있지만 일반적으로 어떠한 작업을 수행하고 이를 다시 복원하는 작업, 예를 들어서 기기를 분해했다가 재조립하는 논리가 필요한 경우 마찬가지로 Stack을 사용하여 처리할 수 있다.

 

 

Stack의 구현 및 관련연산

그래서 이러한 stack을 구현하기 위해서는 다음 5가지 연산을 고려하게 된다.

1. Create_Stack : stack을 생성, 초기 empty 상태
2. Push : stack에 원소를 추가
3. Pop : stack으로부터 원소를 한 개 가져옴, stack에서 해당 원소는 제거됨.
4. Full_Stack : 현재 stack이 Full인지 여부를 확인
5. Empty_Stack : 현재 stack이 empty인지 여부를 확인

정수를 저장하는 정수형 배열을 사용하여서 아래와 같이 stack을 구현할 수 있다.

create_stack

array를 선언하고 top의 값을 초기화 하는 부분

int myStack[SIZE];
int top = 0; // top이 원소가 저장될 위치를 가리키는 경우
// int top = -1; (top이 가장 최근에 원소가 저장된 위치를 가리키는 경우)

(위에서 SIZE는 사전에 정의되어 있는 상수에 해당함.)

여기서 top의 값을 무엇으로 초기화 할지는 top이 무엇을 가리키도록 할 것 이냐에 따라서 달라지는 데 만약 top이 "stack에서 가장 최근에 원소가 저장된 위치"를 가리키고 싶은 경우 -1로, "stack에서 다음에 원소가 추가될 위치"를 가리키고 싶은 경우 0으로 초기화 하게 된다. 이는 개인이 구현하는 성향에 따라서 자유롭게 선택할 수 있으며, 이 중 어떤 방식을 선택하느냐에 따라서 push, pop연산을 구현하는 방식이 달라지게 되므로 이를 적절히 선택하는 것이 중요하다.

 

push

stack에 원소를 추가하는 부분

stack에 새로운 원소를 추가하는 push 연산에 대한 알고리즘의 경우 아래와 같이 구상해볼 수 있다.

(top이 원소가 저장될 위치를 가리키는 경우)

1. top의 위치에 주어진 원소를 넣는다.
2. top의 값을 1 증가시킨다.

(단, 원소를 추가하기 이전에 Stack이 Full 상태여서 더 이상 저장이 불가능한 경우 error로 처리한다.)

(top이 가장 최근에 원소가 저장된 위치를 가리키는 경우)

1. top의 값을 1 증가 시킨다.
2. top의 위치에 주어진 원소를 넣는다.

(단, top의 값을 증가하기 이전에 Stack이 ful 상태여서 더 이상 증가가 불가능한 경우 error로 처리한다.)

그리고 각각의 알고리즘을 아래와 같이 구현해볼 수 있다.

(여기서 변수 top과 myStack의 경우 전역 변수로 선언된 경우라고 가정한다.)

// top이 원소가 저장될 위치를 가리키는 경우

void push(int n)
{
    if(top > SIZE)
        // error 처리...
    myStack[top] = n;
    top++;
}

// top이 가장 최근에 원소가 저장된 위치를 가리키는 경우

void push(int n)
{
    if(top >= SIZE)
        // error 처리...
    top++;
    myStack[top] = n;
}

 

pop

stack에 가장 마지막으로 추가한 원소 1개를 추출하는 부분

stack에 가장 마지막으로 추가한 원소 1개를 추출하는 push 연산에 대한 알고리즘은 아래와 같이 구상해볼 수 있다.

(top이 원소가 저장될 위치를 가리키는 경우)

1. top을 1감소 시킨다.
2. top 위치의 원소를 return 한다.

(단, 원소를 pop하기 전에 stack이 empty 상태인 경우 error로 처리한다.)

(top이 가장 최근에 원소가 저장된 위치를 가리키는 경우)

1. top 위치의 원소를 return 한다.
2. top을 1감소 시킨다.

(단, 원소를 pop하기 전에 stack이 empty 상태인 경우 error로 처리한다.)

그리고 각각의 알고리즘들을 아래와 같이 구현할 수 있다.

// top이 원소가 저장될 위치를 가리키는 경우

int pop()
{
    if(top == 0)
        // error로 처리
    top--;
    return myStack[top];
}

// top이 가장 최근에 원소가 저장된 위치를 가리키는 경우

int pop()
{
    return myStack[top--]
}

 

full_stack

stack이 지정된 크기를 모두 사용하였는 지를 판단하는 부분

이전에 push에 대해서 구현하는 부분에서는 stack이 full 상태인지 판단하는 부분에 대해서 직접 내부에서 구현하여 사용하였는 데 다음과 같이 해당 역할을 수행하는 함수를 별도로 구현하여 사용하는 것이 나중에 확장성 측면에서 더 유리하다. 그리고 해당 기능을 아래와 같이 구현해볼 수 있다.

bool stack_full()
{
    if(top >= SIZE)
        return true;
    else
        return false;
}

 

empty_stack

stack이 empty 상태인지를 확인하는 부분

이전에 pop에 대해서 구현하는 부분에서는 stack이 empty 상태인지 판단하는 부분에 대해서 직접 내부에서 구현하여 사용하였는 데 다음과 같이 해당 역할을 수행하는 함수를 별도로 구현하여 사용하는 것이 나중에 확장성 측면에서 유리하다. 그리고 해당 기능을 아래와 같이 구현해볼 수 있다.

// top이 원소가 저장될 위치를 가리키는 경우

bool stack_empty()
{
    if(top == 0)
        return true;
    else
        return false;
}

// top이 원소가 가장 최근에 저장된 위치를 가리키는 경우

bool stack_empty()
{
    if(top == -1)
        return true;
    else
        return false;
}

 

지금까지 살펴본 것처럼 알 수 있듯이 top에 대한 초기화 값과 push, pop 연산에 대한 일관성에 주의해야 한다.