자료구조 - 스택(stack)

 

  목차

• 스택이란?
• 스택의 연산

 

---

스택이란?

스택이란 마지막에 들어간 자료가 가장 먼저 나오는 자료구조입니다.

스택은 자료의 입출력이 후입선출(LIFO: Last-In Frist-Out)로 제한되는 자료구조입니다.

스택은 다른 통로는 모두 막고 한쪽 만을 열어둔 구조이다. 이것을 보통 상단이라고 불립니다. 스택에 저장되는 것을 항복 또는 요소(element)라고 불립니다.

스택의 구조

 

스택의 대표적인 예 중에서 하나는 인터넷의 이전 페이지 기능이나 한컴의 되돌리기 기능을 생각하면 되겠습니다.

스택은 숫자나 문자열을 포함한 어떤 자료든 저장할 수 있다. 그건 큐나 트리 같은 다른 자료 구조들도 마찬가지 입니다.

반응형

---

스택의 연산

스택 자료형은 어떤 연산을 지원해야 할까? 그것을 삼입, 삭제가 가장 핵심적인 연산입니다. 이것은 스택 상태를 변화시킵니다. 추가적인 연산으로는 스택의 상태를 확인하거나 요소를 확인해 보는 정도 있겠습니다.

 

 

스택에는 아래와 같은 연산이 있습니다.

• push(e): 새로운 요소 e를 스택의 맨 위에 추가
• pop(): 스택의 맨 위에 있는 요소를 꺼내서 반환
• isEmpty(): 스택이 비어 있으면 True를, 아니면 False를 반환
• isFull(): 스택이 가득 차 있으면 True를, 아니면 False를 반환
• peek(): 스택의 맨 위에 있는 향목을 삭제하지 않고 반환
• size(): 스택에 들어 있는 전체 요소의 수를 반환

스택의 일련의 연산

 

스택의 연산은 이렇게 이루어 진다. 순서대로 설명해 보겠습니다.

a : 공백상태

b : 공백 상태에서 push(A)를 해서 A를 삼입시킴

c : b와 같이 B를 삼입

d : c와 같이 C를 삼입

e : 가장 위에 있는 C를 꺼내서 반환

f : 가장 위에는 B를 꺼내지 않고 반환

g: 스택이 비어 있는지 확인하기. 공백(비어 있는)이 아니므로 False를 반환

 

비어는 상태를 공백이라고 하고 가득차 있는 상황을 포화라고 합니다.

가득 차있는 상황에서는 더 이상 삼입할 수 없습니다. 그러므로 삼입을 하려고 하면 에러나 발생하는데 이것을 오버플로(Overflow)라고 합니다. 반대로 공백 상태에서는 더이상 삭제나 참조가 불가능 합니다. 이런 상황에서 삭제나 참조를 하려고 할 경우에 에러가 발생하는데 이것을 언더플로(Underflow)라고 합니다.

그러므로 스택을 안정적으로 사용하기 위해선 상태 검사를 해야합니다.