자료구조 - Stack

Stack은 말 그대로 각각의 원소들을 쌓아서 저장하는 방식이다.

 

stack의 특징은 원소의 추가와 삭제가 stack의 가장 위에서만 발생한다는 것인데 결과적으로 가장 마지막에 추가된 원소가 가장 먼저 빠지기 때문에 LIFO(last in first out)구조를 가진다.

 

Stack의 헤더를 다음과 같이 짜볼 수 있다.

template<class ItemType>	
class StackType {
    int top;
    ItemType  items[MAX_ITEMS];
public:
    StackType();
    
    void Push(ItemType item);
    void Pop();
    void ReplaceItem(ItemType oldItem, ItemType newItem);
    
    bool IsFull() const;
    bool IsEmpty() const;
    ItemType Top();
};

 

여기서 Push, Pop, ReplaceItem은 Transformer에 해당하는 부분으로 각각 가장 위에 원소를 삽입, 가장 위의 원소를 제거, Stack에서 특정 값을 새로운 값으로 변환하는 과정을 수행한다.

 

IsFull, IsEmpty, Top는 Observers로 각각 스택이 전부 찼는지, 스택이 비어있는지 그리고 스택의 제일 윗값은 무엇인지 확인한다.

 

이제 Stack을 실제로 구현해보면 다음과 같이 짤 수 있다.

#include "StackType.h"

template<class ItemType>	
StackType<ItemType>::StackType() {
	top = -1;
}

template<class ItemType>	
void StackType<ItemType>::Push(ItemType newItem) {
	if (IsFull())
		throw FullStack();
	top++;
	items[top] = newItem;
}

template<class ItemType>	
void StackType<ItemType>::Pop() {
	if (IsEmpty())
		throw EmptyStack();
	top--;
}

template<class ItemType>	
void StackType<ItemType>::ReplaceItem(ItemType oldItem, ItemType newItem) {
	for (int i = 0; i <= top; i++) {
		if (oldItem == items[i])
			items[i] = newItem;
	}
}

template<class ItemType>	
bool StackType<ItemType>::IsFull() const {
	return (top == MAX_ITEMS - 1);
}

template<class ItemType>	
bool StackType<ItemType>::IsEmpty() const {
	return (top == -1);
}

template<class ItemType>	
ItemType StackType<ItemType>::Top() {
	if (IsEmpty())
		throw EmptyStack();
	return items[top];
}

 

Push를 해주게 되면 만약 stack이 다 찼다면 FullStack로 예외 처리를 하고, 그렇지 않으면 현재 저장 되어있는 stack의 가장 위를 가리키고 있는 위치를 올린 다음에 해당 위치에 새로운 값을 쌓아준다.

 

Pop을 해주게 되면 만약 stack이 비었다면 EmptyStack으로 예외처리를 해주고, 그렇지 않으면 현재 가장 위를 가르키고 있는 위치를 내려주면 된다.

 

ReplaceItem의 경우 stack의 처음부터 순서대로 stack의 모든 원소를 비교하여 만약 바꾸고 싶은값을 찾으면 바꿀값으로 바꿔준다.

 

stack에는 정수가 들어갈 수도 있고, 실수가 들어갈 수도 있고, 문자가 들어갈 수도 있다.

 

이때 타입별로 stack을 따로 구현하면 같은 동작을 하는 프로그램을 여러개 만들어야하는 번거로움이 있다.

 

따라서 코드를 짤 때 C++의 template을 이용하여 stack에 값을 저장할 때 타입별로 stack을 따로 만들지 않고 사용자에 의해 할당을 해주면 편하게 사용할 수 있다.

 

파이썬으로 구현하면 다음과 같다

 

class StackType:
    def __init__(self):
        self.info = []

    def is_empty(self):
        return len(self.info) == 0

    def is_full(self):
        return len(self.info) == MAX_ITEMS

    def push(self, item):
        self.info.append(item)

    def pop(self):
        if not self.is_empty():
            return self.info.pop()

    def top(self):
        if self.is_empty()==True:
            a="Stack is Empty"
            return a
        else:
            return self.info[-1]