[Data Structure] Stack(스택)

Abstract Data Types (추상 자료형)

 

추상 자료형 (ADTs)는 한마디로 말하면 알고리즘의 요약본이다. ADT는 correctness와 performance를 독립적으로 생각하게 해줄 수 있다.
Correctness는 일반적으로 interface라고도 하는데, input이 들어왔을 때, output의 일치 정확도가 얼마나 높은 가를 말한다.
Performance는 implementation이라고 하며 time complexity와 같은 것을 말한다.
ADT를 짤 때는 해당 알고리즘의 기능만을 고려하며 성능과 자세한 구현을 고려하지 않는다.

 

Stack (스택)

 

스택 개념

 

스택의 삽입과 삭제 원리는 Last-In First-Out(LIFO, 후입선출)로 작동한다. 말 그대로 가장 나중에 들어온 데이터가 가장 먼저 나가게 되는 구조이다.
스택이 활용되는 예시는 아래와 같은 것들이 있다.

• 웹페이지 방문기록 (뒤로가기) : 가장 최근의 방문한 페이지를 우선으로 보여준다.
• 텍스트 편집 프로그램의 되돌리기 (ctrl+z)기능
• C++프로그램에서 코드가 구동되는 시스템 : function call stack이라고 한다.

 

Stack ADT

 

스택의 추상 자료형은 다음과 같다.

• push(object) : object를 삽입한다.
• object pop() : object중 가장 마지막에 삽입된 것을 제거한다.
• object top() : 가장 마지막에 있는 object를 return해준다.
• integer size() : 저장된 object의 개수를 return해준다.
• boolean empty() : 스택이 비어있는 지 아닌 지를 반환해준다.

위의 ADT를 고려해서 stack interface를 구현해보자.

template <typename E>
class Stack {
public:
  int size() const;
  bool empty() const;
  const E& top() const throw(StackEmpty);
  void push(const E& e);
  void pop() throw(StackEmpty);
};

 

Stack implementation (스택 구현)

 

스택을 구현하는 방식에는 2가지 방식이 있다.

1. Array-based stack
2. Linked List-based stack

 

Array-based Stack (배열 기반 스택)

 

ArrayStack prototype

#include <iostream>
using namespace std;

class arrayStack {
public:
  int* S;
  int capacity;
  int t;

  arrayStack(int capacity);
  arrayStack();
  int size();
  bool empty();
  int top();
  void push(int e);
  int pop();
};

배열 기반 스택의 프로토타입 함수 종류들이다. 멤버변수에서 포인터 변수인 S는 실제로 저장 역할을 하는 배열이 될 것이다. 배열 기반 스택은 배열의 인덱스를 바꿔주면서 삽입, 삭제, 출력 연산을 진행하는데, 여기서 어떤 값이 가장 최근 인덱스인지를 알려주는 역할을 t변수가 할 것이다. top의 index역할이라고 생각하면 된다.
자세한 설명은 각 함수 구현과 함께 설명하겠다.

 

arrayStack initializer (생성자)

arrayStack(int capacity) {
  this->capacity = capacity;
  this->S = new int[capacity];
  this->t = -1;
}

스택의 생성자이다. 구현하려는 스택의 크기를 정해주면 그 크기에 맞춰서 스택이 형성된다.
아무런 데이터가 없는 경우에는 top의 index를 -1로 지정해준다.

 

push function

void push(int e) {
  if (t == capacity - 1) {
    cout << "stack is full\n";
    return;
  }

  t++;
  S[t] = e;
}

push 함수는 구현이 어려운 편이 아니다. 하지만 후에 구현할 링크드 리스트와 다르게 배열구현 스택은 크기가 정해져 있으므로 스택이 꽉 찼을 때의 예외처리를 해 줄 필요가 있다.

1. 스택이 찼는 지를 확인해준다. 만약 꽉 찼다면 경고해주고 함수를 종료한다.
2. 스택이 차지 않았다면 top index인 t를 증가시켜준다.
3. 증가된 배열의 t index 위치에 값 e를 넣어준다.

스택이 꽉 찼는 지를 확인하는 방법은 어렵지 않다. top index가 배열의 크기보다 1개 작으면 되는 것이다. (왜 1개 작냐 생각이 든다면... 기초부터 다시 공부하는 것이 좋을거다.)

 

empty function

bool empty() {
  return t == -1;
}

스택이 비었는 지를 확인하는 방법은 쉽다. 앞에서 언급했지만 top의 시작 index값은 -1이다. 즉 t가 -1이라는 것은 스택이 비어있다는 뜻과 같다.

 

pop function

int pop() {
  if(empty()) {
    return -1;
  }

  int tmp = S[t];
  t--;
  return tmp;
}

제거연산을 할 때는 반드시 공백여부를 확인해 줘야한다.

1. 만약 스택이 비어있다면 -1을 반환해준다.
2. 비어있지 않다면 우선 기존의 top 값을 저장해준다.
3. top index를 1내려준다.
4. 기존의 top값을 반환해준다.

 

size and top function

int size() {
  return capacity;
}

int top() {
  if (empty())
    return -1;
  else
    return S[t];
}

두 함수 모두 간단한 구현이다. 그냥 필요한 값을 반환만 해주면 되기 때문다.

 

Linked list-based Stack

 

LinkedStack prototype

#include <iostream>
using namespace std;

class linkedStack {
public:
  int n;
  SLinkedList* S;

  linkedStack();
  int size();
  bool empty();
  int top();
  void push(int e);
  int pop();
};

linked list와 node에 대한 클래스는 이전 글을 확인하거나 tistory블로그에서 확인할 수 있다. 그 두개 코드가 같이 들어가면 너무 길어진다...
여기서 n은 전체 스택의 원소개수가 된다.

 

linkedStack initializer (생성자)

linkedStack() {
  this->S = new SLinkedList;
  this->n = 0;
}

생성자는 간단하게 초기화만 해준다.

 

empty function

bool empty() {
  return n == 0;
}

큰 원리는 배열기반과 비슷하다. n이 원소의 개수를 반환해주므로 n이 0개라면 스택이 비어있다는 의미가 되게 된다.

 

push function

void push(int e) {
  S->addFront(e);
  n++;
}

push 함수는 링크드 리스트 구현에서 사용한 addFront함수를 활용하면 된다. 스택은 최근에 들어온 값들만 확인하면 되기때문에 Front관련 함수들만 구현해서 활용하면된다.

1. 링크드 리스트 S에 원소 e를 넣어준다.
2. n 개수를 1 증가시켜준다.

 

pop function

int pop() {
    if (empty()) {
        return -1;
    }else {
        n--;
        return S->removeFront();
    }
}

스택의 공백 여부만 확인을 잘 해주면된다.

1. 우선 전체 원소수를 대표하는 n을 줄여준다.
2. 그 후 S의 removeFront값을 반환해준다.

 

size and top function

int size() {
  return n;
}

int top() {
  if (empty())
    return -1;
  else
    return S->front();
}

같은 원리로 동작해주면 된다.