스택

개요

스택은 영어로 뭔가를 쌓아놓은 '더미'라는 뜻이며 가장 먼저 들어간 데이터가 가장 마지막에 나오는 구조를 일컫는다. 요소의 삽입과 삭제가 자료구조의 한쪽 끝에서만 이루어진다는 것이 특징이다.

배열로 구현하는 스택

배열을 이용한 구현은 동적으로 스택의 용량을 조절하기가 어렵다는 단점이 있지만, 한편으로는 구현이 간단하다는 장점이 있다.

배열 기반의 스택은 각 노드를 동적으로 생성하고 제거하는 대신, 스택 생성 초기에 사용자가 부여한 용량만큼의 노드를 한꺼번에 생성한다.
그리고 최상위 노드의 위치를 나타내는 변수를 이용하여 삽입과 제거 연산을 수행한다.

• 쉽게말해, 사용자가 스택에 저장할 데이터의 개수를 미리 예상하여 용량을 부여하면, 이때 용량만큼의 노드를 한꺼번에 생성한다. 그리고 스택의 가장 상단에 위치한 노드를 가리키는 변수(top)를 생성하면, 이 변수는 삽입(push)과 제거(pop) 연산을 수행할 때 사용된다.
    삽입 연산을 수행할 때는 새로운 데이터를 저장하는 노드를 생성하고, 이 노드를 top 변수가 가리키는 노드의 위에 위치하도록 만든다.
    제거 연산을 수행할 때는 top 변수가 가리키는 노드를 삭제하고, top 변수가 이전 노드를 가리키도록 업데이트 한다.

위의 그림처럼 topIndex의 최초 위치는 -1이며, 데이터를 추가할때마다 1씩 증가한다.

스택의 각 층을 구성하는 노드의 모습

class StackNode {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

배열을 기반으로 구현되는 스택의 노드는 위처럼 데이터만 담는 구조체로 표현된다.

스택의 구조체

배열 기반의 스택은 다음 세 가지 필드를 가지고 있어야한다.

• 용량 : 스택이 얼마만큼의 노드를 가질 수 있는지에 대한 한계를 알기위해 사용된다.
• 최상위 노드의 위치 : 삽입/제거 시에 최상위 노드에 접근할 수 있게 돕는다.
• 노드 배열 : 스택에 쌓이는 노드를 보관하는 데에 사용된다.

스택의 기본연산

스택을 생성하고 노드를 받아들일 수 있게 준비하는 함수

function createStack(stack, capacity) {
  // 스택을 자유 저장소에 생성
  stack = {
    nodes: [],
    capacity: capacity,
    top: 0
  };

  // 입력된 capacity만큼의 노드를 자유 저장소에 생성
  for (let i = 0; i < capacity; i++) {
    stack.nodes.push(null);
  }

  return stack;
}

이 코드는 createStack 함수를 정의하며, 이 함수는 Stack과 Capacity를 인자로 받아 스택을 생성합니다.
이를 위해 먼저 자유 저장소에 Stack 객체를 생성합니다. 그리고 Stack 객체 내부에 nodes, capacity, top 등의 필드를 초기화합니다. 이후 입력된 Capacity만큼의 노드를 자유 저장소에 생성합니다.

위 코드는 입력으로 받은 인자로 스택을 생성하며, 스택 객체를 반환합니다. 이때, 반환된 객체는 Stack, Nodes, Capacity, Top 등의 필드를 포함합니다.

스택 내의 노드와 스택을 제거하는 함수

function AS_DestroyStack(Stack) {
  // 노드를 자유 저장소에서 해체
  Stack.Nodes = null;
  // 스택을 자유 저장소에서 해체
  Stack = null;
}

삽입(Push) 연산

function AS_Push(Stack, Data) {
  let Position = Stack.Top;

  Stack.Nodes[Position].Data = Data;
  Stack.Top++;
}

Position 변수를 선언하고, Stack.Top을 대입하여 Position 변수에 현재 스택의 맨 위에 위치한 인덱스 값을 저장합니다.

Stack.Nodes[Position].Data = Data;은 Data 값을 스택의 맨 위에 위치한 요소의 데이터 필드에 저장합니다.

마지막으로 Stack.Top을 증가시켜 스택의 맨 위에 있는 요소의 인덱스 값을 업데이트합니다.

제거(Pop) 연산

function AS_Pop(Stack) {
  let Position = --(Stack.Top);

  return Stack.Nodes[Position].Data;
}

링크드 리스트로 구현하는 스택

링크드 리스트(linked list)로 구현하는 스택(stack)은 데이터를 저장하는 노드들이 서로 연결된 구조를 가지고 있다. 각 노드는 데이터와 다음 노드를 가리키는 포인터(pointer)를 저장한다.

링크드 리스트로 스택을 구현하면 좋은 점은 스택의 용량에 제한을 두지 않아도 된다는 점이다.

• 스택에 데이터를 삽입할 때는 새로운 노드를 생성하고, 이 노드를 이전 노드의 다음 노드로 연결한다.
  스택에서 데이터를 제거할 때는 마지막에 삽입된 노드를 제거하고, 이전 노드를 마지막 노드로 설정한다.

스택과 스택의 노드 표현하기

링크드 리스트로 스택을 구현하려면 노드는 자신의 위에 위치하는 노드에 대한 포인터를 갖고 있어야한다.

class Node {
  constructor() {
    this.Data = null;
    this.NextNode = null;
  }
}

JavaScript에서는 구조체가 없으므로, 클래스를 사용하여 Node를 정의한다. 클래스는 객체를 생성하기 위한 템플릿이며, constructor() 메서드를 사용하여 클래스의 인스턴스를 초기화한다.

C 언어와 마찬가지로 Node 구조체에는 데이터와 다음 노드를 가리키는 포인터 필드가 있습니다. JavaScript에서는 포인터 대신 참조를 사용하므로, this.Data와 this.NextNode는 모두 null로 초기화됩니다.

스택의 기본연산

스택의 생성과 소멸

다음은 LinkedListStack 구조체를 자유 저장소에 할당하는 함수이다.

function LLS_CreateStack(Stack) {
    Stack = {
        List: null,
        Top: null
    };
}
// 주의: 매개변수로 Stack이 전달되지만, 이는 C에서의 이중포인터와 같은 개념이 아니므로 Stack이 생성되고 반환되도록 구현해야 함

다음 함수는 메모리를 해제하는 함수이다.

function LLS_DestroyStack(Stack) {
    while (!LLS_IsEmpty(Stack)) {
        let popped = LLS_Pop(Stack);
        /* 노드를 스택에서 제거한 다음 /
LLS_DestroyNode(popped); / 자유 저장소에서 해제한다.*/

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

스택 노드의 생성과 소멸

링크드 리스트 스택의 노드를 생성하는 LLS_CreateNode()의 구현은 약간 복잡하다. 노드를 자유 저장소에 생성할 때, 문자열을 저장할 공간도 함께 생성해야하기 때문이다.

function LLS_CreateNode(NewData) {
  // 자유 저장소에 노드 할당
  const NewNode = {
    Data: null,
    NextNode: null,
  };
  NewNode.Data = newData.slice(); // 입력받은 문자열 복사
  NewNode.NextNode = null; // 다음 노드에 대한 포인터는 null로 초기화

  return NewNode; // 노드의 객체를 반환한다
}

노드를 메모리에서 꺠끗이 제거하는 코드

function LLS_DestroyNode(_Node) {
  free(_Node.Data);
  free(_Node);
}

free()함수가 두번 호출되는데, 한 번은 노드의 Data 필드를 자유 저장소에서 해체하기 위해, 나머지 한 번은 노드를 해체하기 위해서이다.

※ JavaScript에는 C 언어처럼 free 함수가 내장되어 있지 않기 때문에 해당 함수가 어떤 형태로 구현되어 있는지에 따라 다르게 작성될 수 있다.
만약 해당 함수가 없다면, 다른 메모리 해제 함수로 대체하여 작성해야 한다.

삽입(Push)연산

링크드 리스트 버전의 삽입은 링크드 리스트의 추가 연산과 비슷하다. 먼저 최상위 노드를 찾은 다음, 여기에 새 노드를 얹기만 하면 된다. 이렇게 하면 새 노드가 최상위 노드가 된다.
이 새로운 최상위 노드의 주소를 LinkedListStack 구조체의 Top 필드에 등록하는 것으로 LLS_Push() 함수의 임무는 완료된다.

function LLS_Push(Stack, NewNode) {
    if (Stack.List === null) {
        Stack.List = NewNode;
    } else {
        /* 최상위 노드를 찾아 NewNode를 연결한다 (쌓는다) . /
        let OldTop = Stack.List;
        while (OldTop.NextNode !== null) {
        OldTop = OldTop.NextNode;
        }
        OldTop.NextNode = NewNode;
        }
        / 스택의 Top 필드에 새 노드의 주소를 등록한다.. */
        Stack.Top = NewNode;
    }

제거(Pop)연산

링크드 리스트 기반의 스택에서 제거(Pop) 연산은 다음 네 단계로 수행된다.

① 현재 최상위 노드의 주소를 다른 포인터에 복사해 둔다.
② 새로운 최상위 노드, 즉 현재 최상위 노드의 바로 이전(아래) 노드를 찾는다.
③ LinkedListStack 구조체의 Top 필드에 새로운 최상위 노드의 주소를 등록한다.
④ ①에서 포인터에 저장해둔 옛 최상위 노드의 주소를 반환한다.

다음 코드는 제거 연산을 수행하는 LLS_Pop() 함수이다.

function LLS_Pop(Stack) {
    /* 현재 최상위 노드의 주소를 다른 포인터에 복사해 둔다. /
    let TopNode = Stack.Top;
    if (Stack.List == Stack.Top) {
    Stack.List = null;
    Stack.Top = null;
    } else {
    / 새로운 최상위 노드를 스택의 Top 필드에 등록한다. */
    let CurrentTop = Stack.List;
    while (CurrentTop != null && CurrentTop.NextNode != Stack.Top) {
        CurrentTop = CurrentTop.NextNode;
    }
    Stack.Top = CurrentTop;
    CurrentTop.NextNode = null;
}
return TopNode;
}

뇌를 자극하는 알고리즘

https://velog.io/@polynomeer/스택Stack-자료구조#배열-기반의-스택-구현