스택(Stack)

<스택(Stack)>

접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조

스택에 저장된 원소는 top(맨 위)으로 정한 곳에서만 접근 가능

- top 위치에서만 원소를 삽입하므로, 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓이는 LIFO(Last In First Out)구조이다.

[스택 실생활 활용 예]

1. 연탄 쌓기

연탄을 하나씩 쌓으면서 아궁이에 넣는다. 마지막에 넣은 연탄이 가장 위에 있게 된다.

꺼낼때는 위에서부터 하나씩 꺼내야 한다. 마짐가에 넣은 연탄을 가장 먼저 꺼낸다.

2. 옷을 입고 벗는다.

옷을 입을때와 벗을 때를 생각해보면 스택구조인 것을 알 수 있다.

<Push>

스택에서의 삽입연산을 한다.

[Push 알고리즘]

① top ← top+1;
스택 S에서 top이 마지막 자료를 가리키고 있으므로 그 위에 자료를 삽입하려면 먼저 top의 위치를 하나 증가시킨다.
만약 이때 top의 위치가 스택의 크기(stack_SIZE)보다 크다면 오버플로우상태가 되므로 삽입 연산을 수행하지 못하고 연산이 종료된다.
​

② S(top) ← x;
오버플로우 상태가 아니라면 스택의 top이 가리키는 위치에 x 삽입

<Pop>

스택에서의 삭제 연산

① top ← top+1;
스택 S에서 top이 마지막 자료를 가리키고 있으므로 그 위에 자료를 삽입하려면 먼저 top의 위치를 하나 증가시킨다.
만약 이때 top의 위치가 스택의 크기(stack_SIZE)보다 크다면 오버플로우상태가 되므로 삽입 연산을 수행하지 못하고 연산이 종료된다.
​

② S(top) ← x;
오버플로우 상태가 아니라면 스택의 top이 가리키는 위치에 x 삽입

<배열을 이용한 스택>

순차 자료구조인 1차원 배열을 이용하여 구현
- 스택의 크기 : 배열의 크기
- 스택에 저장된 원소의 순서 : 배열 원소의 인덱스
- 인덱스 0번 : 스택의 첫번째 원소
- 인덱스 n-1번 : 스택의 n번째 원소
- 변수 top : 스택에 저장된 마지막 원소에 대한 인덱스 저장

공백 상태 : top = -1 (초기값)
포화 상태 : top = n-1

[배열 구조]

[순차 자료구조로 구현한 스택의 장점]
순차 자료구조인 1차원 배열을 사용하여 쉽게 구현
[순차 자료구조로 구현한 스택의 단점]
물리적으로 크기가 고정된 배열을 사용하므로 스택의 크기 변경 어려움
순차 자료구조의 단점을 그대로 가지고 있다.

<연결 리스트를 이용한 스택>

단순 연결 리스트를 이용하여 구현
- 스택의 원소 : 단순 연결 리스트의 노드
- 스택 원소의 순서 : 노드의 링크 포인터로 연결
- push : 리스트의 마지막에 노드 삽입
- pop : 리스트의 마지막 노드 삭제
- 변수 top : 단순 연결 리스트의 마지막 노드를 가리키는 포인터 변수
−초기 상태 : top = null

① 공백 스택 생성 : createStack(S);

② 원소 A 삽입 : push(S, A);

③ 원소 B 삽입 : push(S, B);

④ 원소 C 삽입 : push(S, C); 

⑤ 원소 삭제 : pop(S);

[연결리스트를 이용한 스택의 코드]

Copyrightⓒ2014 By 한빛아카데미(주)