[자료구조] Chapter 02 스택(스택ADT, 배열로 구현하는 스택)

스택 ADT

데이터를 바닥에서부터 쌓아 올리는 구조이다.

스택에서 데이터의 입력과 출력은 오로지 스택의 꼭대기에서만 이루어진다.

마찬가지로 요소의 삽입과 삭제는 한쪽 끝에서만 이루어진다.

• LIFO(Last In-First Out) 가장 마지막에 들어간 데이터가 가장 먼저 나온다.
• FILO(First In-Last Out) 가장 먼저 들어간 데이터는 가장 나중에 나온다.

 

스택의 핵심 기능: 삽입과 제거 연산

그림과 같이 삽입 연산은 새로운 노드 위에 새로운 노드를 쌓는 것이다.

반대로 제거 연산은 스택에서 최상위 노드를 걷어내는 것이다.

 

 

배열로 구현하는 스택

배열을 이용한 스택은 용량을 동적으로 할당한다는 점에서 변경하는 비용이 크다는 단점이 있다. 그러나 구현이 간단하다는 장점이 있다.

배열 기반의 스택은 각 노드를 동적으로 생성하고 제거하는 대신 스택 생성 초기(사용자가 부여한 만큼)에 노드를 한 번에 생성한다.

 

배열로 기반 스택과 스택의 노드 표현

배열을 기반으로 한 스택은 데이터만 담는 구조체이다.

노드가 존재하는 위치는 배열의 인덱스로 접근할 수 있기 때문에, 링크드 리스트처럼 이전 노드나 다음 노드에 대한 포인터가 필요 없다.

typedef int ElementType;

typedef struct tagNode
{
	ElementType Data;
}

이를 기반으로 스택 구조체를 만들 수 있다.

배열 기반의 스택은 1) 용량, 2) 최상위 노드의 위치, 3) 노드 배열의 정보를 담고 있어야 한다.

1. 용량은 스택이 얼마만큼의 노드를 담을 수 있는지 알기 위해,
2. 최상위 노드의 위치는 삽입/제거 연산을 할 때 최상위 노드에 접근하기 위해,
3. 노드의 배열은 스택에 쌓이는 노드를 보관하기 위해 사용된다.

typedef struct tagArraryStack
{
	int Capacity;
	int Top;
	Node* Nodes;
} ArraryStack;

위의 코드에서 Node* (노드 포인터)는 자유 저장소에 할당한 배열의 첫 번째 요소를 가리키기 위해 사용된다.

 

배열 기반 스택의 기본 연산

스택 ADT는 삽입과 삭제 연산을 기본적으로 갖춘다. 차례로 두 가지의 연산과 스택을 구축하는 코드를 알아보자.

1) 스택 및 노드 생성/소멸 연산

void AS_CreateStack(ArraryStack** Stack, int Capacity)
{
		// 스택을 자유 저장소에 생성
    (*Stack)            == (ArraryStack*)malloc(sizeof(ArraryStack));

		// 입력된 Capacity만큼의 노드를 자유 저장소에 생성
    (*Stack) -> Nodes     == (Node*)malloc(sizeof(Node)*Capacity);

    // Capacity 및 Top 초기화
    (*Stack) -> Capacity  == Capacity;
    (*Stack) -> Top = -1;
}

• 처음 호출된 malloc()은 ArraryStack을 자유 저장소에 쌓기 위해 사용된 것이다.
• 두 번째 호출된 malloc()은 매개 변수로 입력된 개수만큼 노드를 미리 생성하기 위해 사용된 것이다.
• 추가적으로 최상위 노드의 위치를 가리키는 Top을 -1로 초기화했는데 배열의 경우 인덱스가 0부터 시작하는데 이보다 작아야 하기 때문이다.

사용이 끝난 자유 저장소의 경우 직접 정리를 해줘야 하며, free()를 통해 정리할 수 있다.

void AS_DestoryStack(ArraryStack* Stack)
{
		// 노드를 자유 저장소에서 해제
    free(Stack -> Nodes);

		// 스택을 자유 저장소에서 해제
    free(Stack);
}

 

2) 노드 삽입 연산

삽입 연산의 경우 최상위 노드의 인덱스(Top)에서 1을 더한 곳에 새 노드를 입력하는 것이다.

void AS_Push(ArraryStack* Stack, ElementType Data)
{
    Stack -> Top++;
    Stack -> Nodes[Stack -> Top].Data = Data;
}

 

3) 노드 제거 연산

삽입 연산과 반대로 값을 1만큼 낮추면 된다.

하지만! 제거 연산의 경우 최상위 노드에 있던 데이터를 호출자에게 반환해야 한다.

ElementType AS_Pop(ArraryStack* Stack)
{
    int Position = Stack -> Top;
    return Stack -> Nodes[Position].Data
}

 

위의 말이 잘 이해되지 않아 gpt의 도움을 빌렸다.

위의 궁금증에 관한 gpt의 답변..

데이터 구조 내에서 노드를 제거하는 동작을 수행할 때, 해당 노드에 저장된 값을 삭제하기 전에 그 값을 먼저 반환해야 한다는 것을 의미합니다.

일반적으로 많은 데이터 구조에서 노드나 요소를 제거할 때, 제거한 데이터를 반환하면서 동시에 해당 노드나 요소를 삭제하는 경우가 많습니다. 그러나 "하지만! 제거 연산의 경우 최상위 노드에 있던 데이터를 호출자에게 반환해야 한다." 문장은 다르게 작동해야 함을 나타냅니다.

예를 들어, 트리 자료구조에서 특정 노드를 제거할 때, 그 노드에 저장된 값을 반환하면서 노드를 삭제해야 할 수 있습니다. 이렇게 하면 호출자는 제거된 데이터를 사용하거나 저장할 수 있으며, 동시에 데이터 구조를 업데이트할 수 있습니다.