본 카테고리에 게시되는 글은 제가 편입을 준비하며 정리한 자료들입니다.
참조한 서적은 다음과 같습니다.
1. C언어로 쉽게 풀어 쓴 자료구조. 천인국·공용해·하상호. 생능출판사
2. 윤성우의 열혈 자료구조. 윤성우. 오렌지미디어
학부 편입 면접을 위해 준비한 자료이기 때문에 지나치게 긴 코드 또는 너무 깊은 내용은 배제했습니다.
1. 스택의 개념
1) 기본 개념
- 간단하게 책 쌓아놓은 것 생각하면 된다.
- 후입선출 개념 : 맨 끝에 들어간게 맨 처음으로 나옴
- 스택의 후입선출 예시 : 함수 순환호출 마치고 return하면서 되돌아가는 과정
- 스택top : 스택의 가장 위쪽 자료 위치를 알림
스택 삽입, 출력, 스택 비었는지/꽉찼는지 등에 넓게 쓰임.
- 출력 순서가 입력 순서의 역순으로 이루어져야 할 경우 긴요하게 사용
ex) 함수 호출․복귀에 사용되는 시스템 스택
⇒ 함수가 호출될 때 마다 시스템 스택에는 프로그램 카운터(복귀 후 실행될 명령어의 주소), 함수 내 부 지역 변수를 저장하는 활성화 레코드가 저장됨.
⇒ 함수가 종료되면 자신을 실행한 함수로 복귀해야 함. 가령, A,B,C,순서로 함수가 실행되었다면,
C→B로, B→A로 복귀하는 과정 필요.
2) 스택ADT
|
※객체 : n개의 element타입 요소들의 순서 있는 모임 ※연산 create() ::= 스택 생성 init(s) ::= 스택 초기화 is_empty(s) ::= 스택이 비어있는지 검사 is_full(s) ::= 스택이 가득 찼는지 검사 (연결 리스트로 구현할 경우X) push(s, e) ::= 스택 맨 위에 요소를 추가 pop(s) ::= 스택 맨 위의 요소를 반환․삭제 peek(s) ::= 스택 맨 위의 요소를 반환(삭제X) |
3) 스택 기본연산
(1) Push 연산 : 삽입 연산
(2) PoP 연산 : 출력․삭제 연산
(3) is_empty, is_full연산 : 공백 스택인지, 포화 스택인지 검사
(4) create연산 : 스택 생성
(5) peek연산 : 삭제하지는 않고 보기만 하는 연산(pop은 요소를 삭제하면서 출력함)
2. 배열로 구현한 스택
- 배열이므로 최대 크기가 정해져 있음
1) 스택 구조체
- 데이터를 저장할 1차원 배열 stack[MAX_STACK_SIZE] 필드
- 가장 최근에 입력된 자료를 가리키는 top필드
※주의! top = -1로 초기화해야 공백 스택이 된다.
top = 0이면 0번에 데이터가 있음을 의미한다.
typedef struct StackType {
int stack[MAX_SIZE]; // 스택(배열로 구현)
int top; // 스택 top
} StackType
2) init함수
- top을 -1로 하여 스택을 공백 상태로 만든다.
- 배열에 대한 초기화는 할 필요 없다. 어떤 값이 있어도 top이 -1이면 공백 스택이 된다. 삽입 때에는 어차피 top이 가리키는 위치에 넣으면서 자연스럽게 덮어쓰기 될 것이고, 출력․삭제 때에도 top이 가리키는 대상만 출력되는 것이기 때문에, top이상에 존재하는 값은 신경 쓸 필요 없다.
3) is_empty / is_full 연산
(1) is_empty : top이 -1이면 TRUE(1)를 반환, 아니면 FALSE(0)반환
(2) is_full : top == (MAX_STACK_SIZE-1)이 참이면 T반환 아니면 F반환.
※배열 인덱스이므로 MAX_STACK_SIZE-1 이면 맨 끝 요소이다.
4) push연산
(1) 스택이 가득 차지 않았는지 검사(is_full사용)
(2) top을 +1증가시킨다.
(3) top이 가리키는 위치에 삽입한다.
※ 반드시 top부터 증가시켜야 한다. 안그러면 원래 있던 마지막 데이터 덮어쓰게 된다.
5) pop연산
(1) 스택이 텅 비지 않았는지 검사(is_empty사용)
(2) top이 가리키는 값을 반환한다.
(3) top을 하나 감소시킨다.
※데이터는 안지웠잖아! top만 감소시켰잖아? 할 수 있는데, 사실 top위에 있는 데이터는 지워진 데이터라고 보면 된다. 새로운 데이터 들어오면 자연스렆게 덮어씌워질 것이다. 모든 연산이 top을 기준으로 이루어지기 때문에, top위에 존재하는 데이터는 물리적으로는 존재할 지 몰라도 개념적으로는 없는 데이터나 마찬가지다. 예를들어, 배열에 데이터가 꽉 차 있어도 top==-1이면 텅 빈 스택이다.
6) peek연산
(1) 스택이 텅 비지 않았는지 검사(is_empty사용)
(2) top이 가리키는 값을 반환.
3. 연결 리스트로 구현한 스택
- ‘Linked stack’이라고 한다.
- 연결리스트 이므로 크기는 무제한
- 연결 리스트의 헤드 포인터를 top으로 사용하면 된다.
(명확한 표현을 위해 포인터의 이름은 top으로 한다.)
1) 노드 구조체
- 연결 리스트 노드 구조체와 동일하다.
typdef int element;
typedef struct StackNode{
element item;
struct StackNode *link;
} StackNode;
2) 스택 구조체
- top을 노드 구조체를 가리킬 수 있는 포인터로 선언한다.
typedef struct {
StackNode *top;
} LinkedStackType;
3) init함수
- top포인터를 NULL로 초기화하면 된다.
4) is_empty(꽉찰일 없으므로 is_full은 필요없다.)
- top == NULL이면 T, 아니면 F
5) 삽입함수 push
- head대신 top이라는 이름의 포인터를 사용한다는 것을 제외하면, 단순연결 리스트 맨 앞쪽에 삽입하는 것과 동일하다.(연결 리스트 스택에서는 top포인터가 head포인터 역할을 한다!!)
6) 출력삭제함수 pop
- 삭제노드를 가리킬 *temp포인터와, 삭제노드의 데이터를 담아둘 item변수를 사용한다.
- 단순연결 리스트 맨 앞쪽 노드 삭제와 동일하다.
7) 출력함수 peek
- top의 가리키는 노드의 data를 반환한다.
- 스택 top은 top포인터 선언해서 맨 위 노드(맨 마지막에 연결된 노드) 가리키게 하면 됨
- 삽입 : 맨 끝에 삽입 후 링크 조정, top이 삽입된 노드 가리키게 함
- 출력 : 맨 끝 노드 출력(데이터 출력후 노드 free시킴), top이 남은 노드중 맨끝노드 가리키게 함
'비전공자를 위한 컴공 편입 전공면접 > 자료구조' 카테고리의 다른 글
| 3. 리스트 (0) | 2019.03.21 |
|---|---|
| 2. 배열, 구조체, 포인터 (0) | 2019.03.21 |
| 1. 자료구조와 알고리즘 (1) | 2019.02.09 |
