스택

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

어떤 자료를 넣는 것을 push라고 하고, 어떤 자료를 빼는 것을 pop이라고 하는데 스택은 이러한 규칙을 가져야만 자료를 찾을 수 있다.

스택의 push와 pop은 원칙적으로 아래 그림과 같은 방향으로만 가능하기 때문에 안에 들어있는 자료는 원칙적으로 볼 수 없는 상태이다. 

즉 제일 위에만 무엇이 있는지 알 수 있는 자료구조인 것이다.

 

 

스택의 중간에 있는 데이터를 삭제해야 한다면 스택을 쓰면 안 되는 경우에 스택을 사용한 것이므로 스택을 사용하려면 반드시 맨 위의 자료가 의미 있을 때만 사용해야 할 것이다.

 

 

스택의 구현

스택은 일차원 배열 하나로 구현할 수 있고, 이때 size는 현재 스택에 들어있는 크기를 의미한다.

push를 구현

데이터 삽입(push)을 구현한다고 아래와 같이 가정했을 때, size의 상태가 3이다.

스택이라는 배열에 3,7,2가 들어있다고 가정한다면 새로운 자료가 들어올 때의 자리는 2 뒤의 빈칸이 되어야 하며

index로 표현하면 순서대로 0,1,2,3이고 size번째에 새로운 값이 추가되면 될 것이다.

 

push를 구현

데이터 추출 및 삭제(pop)을 구현한다고 아래와 같이 가정했을 때, size의 상태가 4이다.

size의 상태가 4라는 것은 0,1,2,3까지 자료가 존재한다는 뜻으로 3번째 칸에 존재하는 숫자 4가 size-1와 동일한 뜻이다.

따라서 0으로 초기화하여 size를 -1 해주면 pop을 구현한 것이다.

이때 stack의 size 1번재를 return 한다면 top을 구현한 것과 같다.

 

 

스택의 LIFO

Last In, First Out의 약자로 마지막으로 들어간 것이 첫 번째로 나온다는 뜻이다.

스택에 1,2,3,4,5를 넣은 다음 여기서 하나를 뺀다면 가장 마지막에 들어간 5가 나오게 된다.

그다음은 4, 그다음은 3... 의 순서대로 pop 하게 되는 것이다.

 

스택의 LIFO의 특징으로 구현할 수 있는 단어 뒤집기를 예로 설명하자면

 

• 문장이 주어졌을 때 단어를 모두 뒤집는 문제
• 단어의 순서를 바꿀수 없고, 단어는 영어 알파벳으로만 이루어져 있으며
• 단어의 최대 길이:20, 문장의 최대 길이: 1000

이라는 조건에서 예를 들어 Java Stack Study 이라는 단어가 주어졌다고 가정하자.

이때 단어라는것은 공백 하나로 구분되기 때문에 avaJ kcatS ydutS가 정답인 것이다.