1. 스택(Stack)

1. 스택

- 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료 구조이다.

- 마지막으로 넣은 것이 가장 먼저 나오기 때문에 Last in First Out(LIFO)라고 한다.

[ 배열을 이용한 스택 구현 ]

0. 초기 상태

1. push 연산 : Stack에 데이터를 삽입

: 현재 size에 데이터를 삽입하고, size를 하나 증가시킨다.

stack[size] = 4;
size++;

stack[size] = 3;
size++;

2. pop 연산 : Stack에서 데이터를 꺼낸다.

: 현재 size - 1에 있는 데이터를 출력하고 size를 하나 줄인다.

int result = stack[size-1];
size--;
return result;

3. Empty 연산 : Stack이 비었는지 비어있지 않은지를 확인한다.

: size = 0이면 Stack이 비어있는 상태이다.

4. Full 연산 : Stack이 가득찼는지 확인한다.

: stack의 최대 size에 도달하면 true를 리턴한다.

5. Top 연산 : Stack에서 가장 위에 있는 데이터를 확인한다.

: Stack의 size-1 값을 return 한다. pop과 다르게, size를 하나 줄이지 않아 데이터가 꺼내지지는 않고 그대로 유지된다.

6. Size 연산 : Stack에서 현재 저장되어 있는 데이터의 개수를 확인한다.

: Stack의 size값을 그대로 리턴한다.

[ 최종 구현(C++) ]

#include <stdio.h>
#define MAX_STACK_SIZE 51

template<typename T>
class Stack
{
	int size = 0;
	T data[MAX_STACK_SIZE] = { 0 };

public:
	Stack() {}

	void push(T item)
	{
		data[size] = item;
		size++;
	}

	T pop()
	{
		T result = data[size-1];
		size--;

		return result;
	}

	int getSize() { return size;  }
	int isEmpty() { return size == 0; }
};