6. 스택(stack) -a. 배열 기반

스택

  # 스택이란 먼저 들어온 자료가 마지막에 나오고, 마지막에 들어간 자료가 가장 먼저 나오는 구조를 가진 일종의 리스트이다.

  # 영어로는 'FILO(First In Last Out)', 'LIFO(Last In First Out)' 구조의 자료구조라고 불린다.

  # 현실의 쌓여있는 책더미나 동전 지갑, 한쪽만 뚤려있는 통등을 생각하면 이해하기 편하다.

  # 일반적으로 스택에 가장 나중에 들어온 데이터의 위치를 Top, 가장 처음에 들어온 데이터의 위치를 Bottom이라 한다.

  # 일반적으로 스택에 데이터를 넣는 행위를 Push, 데이터를 빼는 행위를 Pop, Top의 데이터를 확인하는 행위를 Peek이라 한다.

  # 스택이 비어있을 때 데이터를 빼려고 하면 Underflow가 발생하고, 스택이 가득 차있을때 데이터를 넣으려고 하면 Overflow가 발생한다.

  # 스택은 컴퓨터에서 실제로 사용되는 곳이 많은 자료구조이니 이해해두면 좋다. (서브루틴의 복귀주소 저장장소, 컴파일러, 산술식 계산 등)

  # 스택은 배열이나 연결리스트를 이용하여 구현할 수 있다.

배열 기반 스택

  # 배열 기반의 스택은 배열에 접근하는 index를 push와 pop에 따라서 top변수의 값을 바꿔주는 걸로 구현할 수 있다.

  # 배열 기반 스택은 구현이 쉽다는 장점이 있지만 스택의 크기를 바꾸기 힘들다는 단점이 있다.

  # 배열 기반 스택의 크기를 바꾸기 위해서는 선형 리스트에서와 마찬가지로 메모리 공간을 새로 할당해서 옮겨줘야만 한다.

배열 기반 스택의 ADT

  1. 스택 생성시 스택의 크기를 정해야 한다.

  2. 스택에 데이터를 넣는다. (Push)

    (Stack이 가득차있는 경우 값을 저장하지 못하고 false를 반환한다. 그러므로 사용시 스택에 빈공간이 있는지 확인할 필요가 있다.)

  3. 스택에서 데이터를 뺀다. (Pop) 

  4. 스택 맨 위의 데이터를 확인한다. (Peek)

    (Stack이 비어있었던 경우 쓰레기값을 반환한다. 그러므로 사용시 스택이 비었는지 확인할 필요가 있다.)

  5. 스택에 들어있는 데이터의 개수를 확인한다. (Count) 

  6. 스택의 최대 사이즈를 확인한다. (CapacitySize)

  (스택이 비었는지는 Count가 0인지 확인하는 걸로, 가득 찼는지 확인하는 것은 Count를 Capacity와 비교하는 걸로 대신한다.)

  7. 스택을 복사한다. (복사생성자) (이 때, 스택의 데이터가 포인터이면 이를 사용하지 말고 사용자가 직접 깊은 복사를 해야한다.)

 

 C++로 구현한 배열 기반 스택

#pragma once

template <typename T>
class StackArray
{
	int size;
	T* capacity;
	int top;

public:
	bool Push(T data);
	bool Pop();
	T& Peek();
	int Count();
	int CapacitySize();

public:
	StackArray(int size);
	virtual ~StackArray();
};

template <typename T>
StackArray<T>::StackArray(int _size)
{
	size = _size;
	capacity = new T[size];
	top = -1;
}

template <typename T>
bool StackArray<T>::Push(T data)
{
	if (top == size - 1) {
		return false;
	}

	capacity[++top] = data;
	return true;
}

template <typename T>
bool StackArray<T>::Pop()
{
	if (top == -1) {
		return false;
	}

	top--;
	return true;
}

template <typename T>
T& StackArray<T>::Peek()
{
	return capacity[top];
}

template <typename T>
int StackArray<T>::Count()
{
	return top + 1;
}

template <typename T>
int StackArray<T>::CapacitySize()
{
	return size;
}

template <typename T>
StackArray<T>::~StackArray()
{
	delete[] capacity;
}