ADT Stack의 정의와 연산 구현 (create, push, pop, top, empty)

스택

 

실생활에서도 정말많이 사용하는 자료구조이다

 

물론 Computer Science에서도 정말정말정말 중요하고 몰라서는 안될 자료구조이기도 하다

인터넷 방문 기록(뒤로가기)의 구현에도, 함수의 재귀 호출에도 스택이 사용된다

하지만 스택에 대해서 음 후입선출~ 정도까지만 간략히 알고있는 경우가 많다

또 스택이면 스택이지 ADT 스택은 뭘까?

 

우선 스택에 대해 간략하게 알아보자면

스택에는 데이터들이 저장되어 있다. 가장 위(마지막)에 저장한 데이터의 위치를 스택의 탑이라고 한다.

데이터의 추가/삭제는 오직 스택의 탑 위치에서만 가능하다.

 

ADT Stack은 어떠한 자료의 형태에 'Stack'이라고 명명할 수 있게 하는 자료의 형태와 연산을 정의한 것을 말한다.

즉, 이것을 만족하지 않는 자료는 스택이라고 할 수 없으며 스택을 정의하기 위해서는 위의 조건 이외에는 불필요하다.

또한 이러한 정의는 특정 프로그래밍 언어에 종속되지 않는다.

C언어에서 배열을 이용해서 스택을 구현하던, Java에서 List를 이용해서 스택을 구현하던 간에 ADT Stack의 정의와는 무관하다는 뜻이다.

 

ADT Stack에서 지원하는 Stack의 연산은 5가지가 있다.

 

1️⃣ create(size): 최대 size개의 item을 저장할 수 있는 stack을 생성한다. 이 때, size는 주어지지 않을 수도 있다(스택 내부에서 임의 조정). O(1)

2️⃣ isEmpty(): stack에 item이 있는지 검사한다. 만약 item이 하나도 없다면 true, 아니라면 false를 반환한다. O(1)

3️⃣ push(item): stack에 item을 삽입한다(만약 size를 초과한다면 false를 반환할 수 있다). O(1)

4️⃣ pop(): stack의 top에 위치한 item을 반환하면서 동시에 제거한다(반환하지 않을 수 있다). O(1)

5️⃣ top() (=peek()): stack의 top에 위치한 item을 반환한다. O(1)

 

괄호에 들어간 것은 일부 스택의 정의마다 다르다.

하지만 위의 5가지 연산을 지원하고 이러한 자료만 스택이라고 규명한다.

내가 임의로 '스택의 연산도 쓰고싶은데... top이외의 자료도 접근하고 싶다'라고 생각해서 그러한 연산을 추가한다면 그것은 스택이 아니다

 

그것이 ADT Stack의 정의니까 

 

결국 스택은 top에 위치한 item만 접근할 수 있다.

push할 때는 top(가장 마지막에 push)의 뒤에 삽입하고, pop할 때도 top에 있는 아이템만을 제거한다.

이렇게 나중에 들어간 item이 먼저 나오는 구조를 Last-in-First-Out(LIFO) 구조라고 한다.

 

위에서 잠시 언급했던 함수의 콜 스택에서도 stack의 원리를 사용한다

main함수에서는 func1함수를 호출 -> func1함수에서 func2함수를 호출

-> func2함수에서 값을 반환 -> func1함수에서 반환된 값에서 추가 연산을 한 뒤 값을 반환 -> main함수의 변수 대입

 

이러한 순서로, 나중에 호출된 함수의 코드를 전부 시행한 뒤 이전 함수로 돌아가는 스택 구조를 활용한다.

 

아래는 c로 구현한 adt stack이다.

typedef struct data_type {
	int num;
}data;

typedef struct {
	data* items;
	int capacity;
	int top;
}Stack;

void create(Stack* stack) {
	stack->capacity = 2;
	stack->top = -1;
	stack->items = (data*)malloc(sizeof(data) * stack->capacity);
}

bool isEmpty(Stack* stack) {
	if (stack->top == -1)return true;
	return false;
}

data top(Stack* stack) {
	return stack->items[stack->top];
}

void push(Stack* stack, data item) {
	stack->top++;
	if (stack->top == stack->capacity) {
		stack->capacity *= 2;
		stack->items = (data*)realloc(stack->items, sizeof(data) * (stack->capacity));
	}
	stack->items[stack->top] = item;
}

data* pop(Stack* stack) {
	if (isEmpty(stack)) {
		printf("Stack is already empty.\n");
		return NULL;
	}

	data* item = &stack->items[stack->top];
	stack->top--;
	return item;
}