자료구조[기말고사] 정리

소개

자료구조 정리한것입니다. 많은 참고 하시고요 시험 잘보세요

목차

없음

본문내용

- 스택
- 스택의 추가 연산을 push라 부르고, 삭제 연산을 pop이라 부르며, 이 연산들이 발생하는 한쪽 끝을 스택의 상단이라고 부른다. 따라서 스택에서 처리할 수 있는 원소는 상단에 있는 원소뿐이다. 추가와 삭제 두연산이 스택의 동일한 한 쪽 끝에서만 발생하므로, 삭제되는 순서는 추가된 순서와 반대이다. 즉 제일 마지막에 추가된 원소가 먼저 삭제되는데 이러한 현상을 후입선출이라 한다.
- 스택저장은 책 참조
- 스택의 연산 [추가]
- 우선 top이 스택의 한계인 n이상인 지를 먼저 확인한다. 만일에 top이 n이상이라면 스택에는 이미 원소들이 가득차있기 때문에 더 이상의 항목을 추가할 수 없다. 그래서 스택에 원소가 가득 찼을 때 취할 수 있는 행위를 하도로ㄱ 한다. 하지만 top이 n보다 작으면 스택에 항목을 넣을 여유 공간이 있기 때문에 top의 값을 증가시키고 그위치인 스택에 항목을 넣는다.
- 스택의 연산 [삭제]
- top이 0이라면 스택에는 원소가 하나도 없기 때문에 스택에서 원소를 꺼내는 작업을 할 수 없고 대신에 스택이 비었을 때 취할 수 있는 행위를 하도록 한다. top이 0보다 크다면 스택에는 하나 이상의 원소들이 있기 때문에 스택에서 top이 가리키는 위치에 있는 원소를 꺼내어 항목에 넘겨주고 top값을 1만큼 감소 시킨다.
- 큐는 한쪽 끝에서 자료가 추가되고 반대쪽 끝에서는 삭제가 일어나는 특별한 순차리스트이다.
- 큐에 들어있는 원소는 왼쪽(전두front)에서 꺼내지고(삭제), 큐에 항목을 넣을때는 오른쪽(후미rear)에서 추가되기 때문에, 먼저 들어간 원소가 먼저 꺼내진다. 이러한 현상을 선입선출이라고 한다.
- 단순 큐의 문제점 : 큐는 프로그램을 작성할 때 자주 사용된다. 큐의 가장 보편적인 이용은 운영체제에 의한 작업 큐의 관리이다. 만약 운영체제가 작업에 대한 우선순위를 사용하지 않는다면 작업들은 컴퓨터 시스템에 들어온 순서대로 처리될 것이다. 실제로는 비어 있지만 알고리즘상 가득차게 보인다.

참고자료

· 없음