[연습문제] C로 배우는 쉬운 자료구조 6~7장

스택 ? 한쪽 끝에서만 새로운 항목을 삽입하거나 기존의 항목을 삭제할 수 있도록 고안

후입
선컼





←
top
마��막자료
(가장 최근 자료)




.
.
.

첫 번째 자료
(가장 오래된 자료)
(스택의 구조)
top : 스택은 top를 통해서 들어온 자료가 일정한 방향으로 쌓이며 top는 현재 스택의 가장 위에 있는 마지막 자료를 가리키며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 되며, 삽입된 자료는 스택의 마지막 자료가 되고, 이때 tip은 삽입된 자료를 마지막 자료로 가리킨다. 스택에서 자료를 삭제할 경우에도 top를 통해서만 가능하다.

- 스택의 구조?










→A삽입
(push A)

→B삽입
(push B)

→C삽입
(push C)

→삭제
(pop)




C



B
B
B

A
A
A
A
시간순서에 따라 자료가 쌓여서 가장 마지막에
삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 갖는다.
이를 후입선컼(LIFO)이라고 표현한다.





스택에서 top을 통한 삽입연산을 push, top을 통한 삭제 연산을 pop이라고 한다.

- 스택의 구현




n번째 원소

[0]
[1]

[n-1]
…
→ stack
첫 번째 원소
두 번째 원소
…
n번째 원소
두 번째 원소


첫 번째 원소


스택에 대한 1차원 배열의 표현
순차 자료구조인 1차원 배열을 이용하여 스택을 구현할 수 있다. 1차원 배열인 stack[n]을 사용할 때 n은 배열의 크기로서 배열원소의 개수를 나타내는데, 이것이 스택의 크기이다. 스택에 원소가 쌓이는 순서는 배열의 인덱스로 표현한다. 따라서 스택의 첫 번째 원소는 stack[0]에 저장되고, 스택의 두 번째 원소는 stack[1]에 저장되고, 스택의 i번째 원소는 stack[i-1]에 저장된다.





top은 마지막 원소의 인덱스를 저장하는 변수를 사용하고, 스택의 top은 노드에 대한 포인터 top을 사용한다.