Data Structure - stacks

1.  Stack ADT란?

정의 : 임의적인 객체 (arbitrary objects)를 stack 형식으로 저장

 

Stack이란? - 나중에 저장된 데이터가 먼저 나오는 Last-In First-Out 구조의 자료구조

 

Stack 형태의 자료구조

주요 Stack Operation

   - push(object) : 요소 삽입

   - pop() : 가장 나중에 추가된 요소 제거

 

부가 Stack Operation

   - top() : 가장 마지막에 추가된 요소 지우지 않고 (object) return

   - size() : 저장된 요소의 개수 (integer) return

   - empty() : 요소가 하나도 없는지 (비어있는지) 여부 (boolean) return

 

Operation 예시

The Standard Template Library(STL) 스택

STL 스택은 기본적으로 C++에서 제공해주는 라이브러리로써 아래와 같이 사용 가능하다.

#include <stack>
using std::stack  //스택 접근 가능하게 하기
stack<int> myStack // 정수들의 스택

 

Stack Container

학습자료에서는 따로 Stack Container로 언급이 되어있지 않고 C++ 인터페이스가 Stack ADT랑 잘 호응된다고 나와있는데, 아래 예제를 보면 Stack Container를 말하는 것 같다. 또한 STL 스택과 다르다는 점에서 혼동이 오는데, 아마 눈치상으로는 위의 STL은 standard template이다 보니 이는 사용자 임의로 template을 만드는 것이 다른 점 같기는 하지만, 어떻게 다른 것인지는 교수님께 여쭤보고 블로그를 갱신하겠다.  인터넷[https://blockdmask.tistory.com/100]에서 본 내용에 의하면 위의 STL 스택 코드에서 #include <stack> 과  using std::stack은 똑같이 적은 상태에서, template을 우리가 직접 정의해주는데 예를 들면 아래와 같다.

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)
};

위의 코드에서 thorw로 예외처리 해준 StackEmpty에 대해 알아보자.

 

ADT의 operation을 실행하려고 시도할 때, 가끔 이는 예외적으로 오류가 날 때가 있다. 따라서 이러한 오류를 막기 위해 throw문을 이용하여 pop과 top의 예외상황을 처리해 주는 것이다.

 

2. Stack의 활용

그렇다면 Stack은 어떻게 활용될까?

 

1. 직접적 활용

   

   - 웹 브라우저의 히스토리

   - 텍스트에디터에서 차례로 적고 지우는 기능

   - C++ 런 타임 시스템에서의 메소드의 chain

 

2. 간접적 활용

   - 알고리즘에서의 부가적 자료구조

   - 자료구조의 요소

 

C++ 런타임에서의 Stack 활용

전역변수와 지역변수에 대해 생각해보면 쉽다. 전역변수가 지역변수보다 아래쪽에 위치하기에 지역변수의 블럭이 끝나면 전역변수보다 먼저 pop되어 소멸하는 것이다. 반대로 말하면 전역변수가 지역변수보다 먼저 push되어서 아래쪽에 위치하게 되는 것이다. 이는 앞에서 살펴보았던 Recursion에서도 활용된다.

 

배열로 스택 구현하기 (Array Based Stack)

흔히 세로로 그려진 스택을 가로로 눕혔다고 생각하면 편하다. 

top = arr[t]이라고 하면 size()와 pop(), push는 다음과 같은 알고리즘으로 나타낼 수 있다.

하지만 배열로 스택을 구현하기에는 한계점이 있다. 배열로 스택을 구현하기 위해서는 항상 배열의 크기가 선행적으로 정해져야 하고, 추후에 배열에 크기를 변경하는 것이 불가능하다. 따라서 배열이 가득 차 있을 때 새로운 object를 push할 수 없다.

 

배열로 스택 구현하기

스택을 이용한 괄호 매칭 체크

간단하게 말로 설명하면  X[i]에 들어있는 괄호들을 개괄호( (,{,[ 같은 것들 )면 스택 S에 담고, 폐괄호 ( ),},] ) 들과 매칭되면 S.pop으로 하나씩 지워서 마지막에 스택 S가 비면(S.empty()) 모든 괄호들이 제대로 매칭이 제대로 된 것으로 true를 return 한다. 아니면 false를 return한다.