[DS] 3. 스택

스택(Stack)?

std::stack<int> s;

데이터의 입출력이 후입선출로 일어나는 자료구조.

---

추상 자료형

데이터 : 후입선출(LIFO, Last-In First-Out)의 형태를 갖는 요소들의 모음.

연산 :

함수	설명
push(x)	주어진 데이터 x를 스택의 맨 뒤에 추가.
pop()	맨 뒤에 있는 요소를 삭제+반환. (스택이 비어있지 않으면)
peek()	맨 뒤에 있는 요소를 반환. (스택이 비어있지 않으면)
isEmpty()	스택이 비어있다면 true, 아니라면 false 반환.
isFull()	스택이 가득 찼으면 true, 아니라면 false 반환.
size()	데이터들의 갯수를 반환한다.
display()	모든 데이터들을 출력한다.

---

사용법 (std::stack)

메서드

함수	설명
push(x)	맨 뒤에 데이터 x를 삽입한다.
emplace(x)	맨 뒤에 데이터 x를 삽입한다. 단, 내부에서 객체를 생성하여 할당한다.
pop()	맨 뒤의 데이터를 삭제한다. 반환 타입 void.
size()	데이터들의 갯수를 반환한다.
empty()	스택이 비어있다면 true, 아니라면 false 반환.
top()	맨 위에 있는 요소를 반환. (스택이 비어있지 않으면)
swap(s)	인자로 스택 s를 받아, 서로가 가리키는 주소 정보(포인터)를 서로 맞바꾼다.

emplace는 push와 다르게, 인자를 받아 직접 내부에서 객체 생성 후 할당한다. 때문에, 상수를 인자로 받게 되면 불필요한 복사/이동 연산의 과정이 생략되어 오버헤드가 적다.

다만 내부적으로 생성자에 직접 인자를 전달하기에, explicit 키워드가 걸려있어도 생성자를 정상적으로 호출한다. 이로 인해 의도치 않은 타입 생성이 일어날 수 있기에 사용에 주의가 필요하다.

예제 코드

Stack

#include <iostream>
#include <stack>

int main() {
  std::stack<int> s;

  s.push(10);                      // 데이터 삽입
  s.push(20);
  s.push(30);

  while (!s.empty())               // 데이터 추출(삭제)
  {
      std::cout << s.top() << " "; // 출력
      s.pop();                     // 삭제
  }

  return 0;
}

30 20 10 

---

구현

아래는 고정 배열을 통해, 스택을 유사하게 구현한 예제 코드이다.

예제 코드 (고정 배열 기반)

#include <iostream>
constexpr int MAX_STACK_SIZE = 5; // 최대 데이터 수

template<typename T>
class ArrayStack
{
  int top;                       // 현재 맨 뒤 데이터의 index 값
  T data[MAX_STACK_SIZE];        // 저장할 배열
public:
  ArrayStack()    { top = -1; }  // 생성자
  ~ArrayStack()   {}             // 소멸자
  bool isEmpty()  { return (top == -1); }
  bool isFull()   { return (top == MAX_STACK_SIZE - 1); }
  int size()      { return (top + 1); }

  void push(T inputData)
  { // (가득 차지 않았다면) 데이터를 맨 뒤에 넣는다.
    if (isFull())  { std::cout << "Stack is Full" << std::endl; return; }
    data[++top] = inputData;
  }

  T pop()
  { // (비어있지 않다면) 맨 뒤의 데이터를 삭제+반환한다. 정확히는 삭제가 아닌 없는취급.
    if (isEmpty()) { std::cout << "Stack is Empty" << std::endl; return T(); }
    return data[top--];
  }

  T peek()
  { // (비어있지 않다면) 맨 뒤의 데이터를 반환한다.
    if (isEmpty()) { std::cout << "Stack is Empty" << std::endl; return T(); }
    return data[top];
  }

  void display()
  { // 모든 데이터를 출력한다.
    std::cout << "Data : ";
    for (int i = 0; i <= top; i++)
      std::cout << data[i] << " ";
    std::cout << std::endl;
  }
};

ArrayStack push

ArrayStack pop

예제 코드 (연결 리스트 기반)

포인터의 선행학습 이후 보기를 권장한다.

연결 리스트는 크기 제한이랄게 없기에, isFull()이 없다.

#include <iostream>

template <typename T>
class ListStack
{
  struct Node
  { // 노드 구조체.
    Node(T inputData, Node* nextNode = nullptr) : data(inputData), next(nextNode) {}
    T data;      // 데이터
    Node* next;  // 다음 노드의 주소
  };
  Node* topNode; // 현재 맨 뒤 노드의 주소값.
  int count;     // 현재 데이터 갯수. 매 삽입/삭제시 갱신.

public:
  ListStack()  { topNode = nullptr; count = 0; }    // 생성자
  ~ListStack() { while (!isEmpty()) pop(); }        // 소멸자 (반복문으로 모두 메모리해제)
  
  bool isEmpty() { return (topNode == nullptr); }
  int size()     { return count; }

  void push(T inputData)
  { // 받아온 데이터로 새 노드를 만들고, 이를 맨 뒤 노드로 갱신한다.
    Node* newNode = new Node(inputData, topNode); // 새 노드 생성
    topNode = newNode;              // 맨 뒤 노드 갱신
    count++;                        // 갯수 갱신
  }

  T pop()
  { // (비어있지 않다면) 맨 뒤의 노드를 삭제 및 갱신한다.
    // 단, 삭제 이전에 원본 데이터를 먼저 깊은복사 해둔 뒤, 이를 return한다.
    if (isEmpty()) { std::cout << "Stack is Empty" << std::endl; return T(); }

    Node* nextNode = topNode->next; // 삭제 이전에 다음 노드 주소 저장
    T returnData = topNode->data;   // 삭제 이전에 원본 데이터 깊은 복사
    delete topNode;                 // 삭제
    topNode = nextNode;             // 맨 뒤 노드 갱신
    count--;                        // 갯수 갱신
    
    return returnData;
  }

  T peek()
  { // (비어있지 않다면) 맨 뒤의 노드 내 데이터를 return한다.
    if (isEmpty()) { std::cout << "Stack is Empty" << std::endl; return T(); }
    return topNode->data;
  }

  void display()
  { // 모든 데이터를 출력한다.
    std::cout << "Data : ";
    for (auto curr = topNode; curr != nullptr; curr = curr->next)
      std::cout << curr->data << " ";
    std::cout << std::endl;
  }
};

Linked-List push

Linked-List pop

---

특징

삽입/반출의 시간복잡도가 $O(1)$으로 상당히 빠르다. 당연하게도, 기준점이 되는 맨 뒤의 노드를 항상 알고 있기 때문이다.

표준 라이브러리의 std::stack은 내부적으로 deque를 사용해 구현된다. 이는 std::queue도 마찬가지.

deque는 stack과 queue의 특성을 동시에 가지는 자료구조이며, std::deque 기준으로 내부적으로 일반 배열의 데이터로 이루어진, 청크 단위의 노드를, 중앙 포인터 배열로 관리하는 형태로 구현되어있다. 이로 인해 메모리를 조금 더 쓰는 대신, 캐시 효율성을 얻는다. 자세한 것은 이후에 다룬다.

사용례

• 프로그램에서 사용되는 되돌리기(Undo) 기능
• 깊이 우선 탐색 알고리즘 (DFS, Depth-First Search)
• 연속적인 함수 호출 시의 복귀 주소 기억
• 코드 에디터에서의 괄호 쌍 검사