본문으로 바로가기

스택은 데이터를 순차적으로 저장하고 가장 최근에 입력된 데이터를 반환하는 후입선출(Last In First Out)의 대표적인 자료구조다. 때문에 스택의 입출력은 스택의 상단(top)에서만 일어나고 스택의 중간 지점이나 하단에서는 데이터의 입출력이 일어나지 않는다.

이번 포스트에서는 배열을 사용하여 스택을 구현한다. 스택의 최대 사이즈를 인자로 받아 스택에 데이터를 순차적으로 저장하고 스택의 상단에서 데이터의 입출력을 담당하는 메소드를 정의한다.

Implementation

class Stack {

public:
  Stack(const int = 10);
  ~Stack();

  bool empty() const;// 스택이 비어있는지 유무를 반환
  bool full() const;// 스택이 가득차있는지 유무를 반환
  int size() const;// 스택에 저장된 데이터의 개수를 반환
  int top() const;// 가장 최근에 입력된 데이터를 반환

  void push(const int);// 스택에 데이터를 삽입
  int pop();// 가장 최근에 입력된 데이터를 삭제하고 반환

  void display() const;

private:
  int _top;// 가장 최근에 입력된 데이터의 인덱스
  int _size_of_array;// 데이터를 저장할 배열의 사이즈
  int* _data;// 데이터를 저장할 배열

};
inline void error(const char *message) {
  printf("%s\n", message);
  exit(1);
}

Stack::Stack(const int size): _top(-1), _size_of_array(size), _data(new int[size]) {
  // 스택이 비어있다면 _top은 -1의 값을 가진다
  // 생성자는 배열의 사이즈를 인자로 받아 배열을 동적으로 할당한다
}

Stack::~Stack() {
  delete[] _data;// 동적으로 할당된 배열을 해제
}

bool Stack::empty() const {
  return size() == 0;
}

bool Stack::full() const {
  return size() == _size_of_array;
}

int Stack::size() const {
  return _top + 1;// 배열의 인덱스는 0부터 시작하기 때문에
}

int Stack::top() const {
  if (empty()) error("Stack is empty");
  return _data[_top];// _top 인덱스의 데이터를 반환
}

void Stack::push(const int data) {
  if (full()) error("Stack is full");
  _data[++_top] = data;// _top 다음 인덱스에 데이터를 삽입
}

int Stack::pop() {
  if (empty()) error("Stack is empty");
  return _data[_top--];// _top 인덱스의 데이터를 반환하고 삭제
}

void Stack::display() const {
  if (empty()) {
    printf("%s\n", "Stack is empty");
    return;
  }
  printf("size(): %d\n", size());
  printf("top(): %d\n", top());
  for (int i=0; i<=_top; i++) {
    printf("%d ", _data[i]);
  }
  puts("(top)");
}

Performance Analysis

Time Complexity
empty full size top push pop
O(1) O(1) O(1) O(1) O(1) O(1)

댓글을 달아 주세요