|
|
|
|
| |
|
| |
|
|
| 마지막 교육 (0) | 2008/06/28 |
|---|---|
| 5주차 교육을 다녀와서... (0) | 2008/06/20 |
| 스토리텔링 표 만들기 (0) | 2008/05/21 |
| 다미 2차 교육을 다녀오고 나서~ (0) | 2008/04/27 |
| 다미4기 ^^ 워크샵 (0) | 2008/04/11 |
| 다미 - 워크샵을 다녀오고.. (0) | 2008/04/01 |
| 광우병 ... 그 날이 점점 우리 곁으로 다가온다! (0) | 2008/05/17 |
|---|---|
| 하나로 텔레콤 600만 개인정보 유출 (0) | 2008/04/24 |
| 국내 유명 포털ID, 중국 사이트에서 판매...충격 (0) | 2008/04/21 |
| 야채가 우리 몸에 미치는 영향들! (0) | 2008/04/19 |
| 여자들이 좋아하는 나쁜남자들... (0) | 2008/04/19 |
| 사회적 기업 희망 블로거 ! (0) | 2008/05/16 |
|---|
| 설득의 기술 (0) | 2008/06/07 |
|---|---|
| 열정이 차이를 만든다. (0) | 2008/05/16 |
|
※ 큐의 정의 : 순차 리스트의 특수한 형태로서, 원소의 삽입은 뒤(rear)에서 삭제는 앞(front)에서 이루어지는 자료구조라고 하며, 선입 선출 리스트는 제일 먼저 출력된 원소가 우선적으로 출력됩니다. |
|
※ 큐의 구조 : 동적배열과 마찬가지로 상당히 구현이 쉬운 자료구조중 하나로 먼저 들어간 자료가 먼저 나오고, 늦게 들어간 자료가 늦게 나오는 구조입니다. |
|
|
※ 큐의 원리 : 큐는 매표소에서 표를 사기 위해 기다리는 대기자 열과 같은 원리를 가진다. 대기자 열에는 먼저 온 사람부터 차례로 대기자들이 늘어서 있다. 앞쪽 끝에서는 기다리던 사람이 표를 사서 빠져나가고(삭제), 뒤쪽 끝에서는 새로운 사람들이 대기자 열로 들어온다.(삽입) |
|
※ 큐의 성질 : 큐에 저장된 데이터 항목들 중에 먼저 삽입된 것은 먼저 삭제되고, 나중에 삽입된 것은 나중에 삭제된다. 그래서 큐를 선입 선출 리스트(First-InFirst-out:FIFO) 라 부른다. 후입 선출법을 사용하는 스택과는 상반될 성질을 가진다. |
|
※ 큐의 종류 : 큐에는 한 방향으로 데이터 항목들이 삽입/삭제되는 선형 큐와 시작점와 끝점이 서로 연결되어 있는 황형 큐가 있다. |
|
선형 큐 |
환형 큐 |
 |
|
|
배열로 구현하는 선형 큐 -데이터 집합을 배열에 저장합니다. -배열의 특성상 크기가 미리 정해져 있음 -front에서 Get하고, rear에서 Put 합니다. |
선형큐의 문제점을 보완하기 위해 만들어진 자료구조이다. 삽입과 삭제 동작은 선형 큐와 같지만, 큐의 상한과 하한이 서로 연결된 고리 모양을 하고 있어, 사실상 큐의 한계가 없는 것과 같다. |
|
데크의 정의 : 는 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다. 두개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생 시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있습니다. |
|
데크의 구조 : 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료 구조이다. |
 |
|
데크의 종류 : 스크롤과 셀프로 나눌 수 있습니다. 스크롤은 입력이 한쪽 끝으로만 가능하도록 설정한 데크이고, 셀프는 출력이 한쪽 끝으로만 가능하도록 설정한 데크 입니다. |
|
입력 제한 데크: Scroll |
출력 제한 데크: Shelf |
|
|
|
|
다중(Multi) 큐 : 크기가 n인 큐를 하나의 큐 크기가 n/m인 m개의 다중 스택으로 구현, 큐 하나 하나의 크기를 예상할 수 없으므로 동일한 크기로 분배하는 방식입니다. 다중 큐의 경우 각 큐에 삽입삭제가 진행되면 큐가 한 쪽방향으로 진행해가고 이에 따라 최악의 경우 m개의 큐가 1개의 큐로 축소될 수도 있다. 이러한 현상을 방지하기 위해 다중스택에서와 같이 각 큐를 시작위치를 지시하는 B[]를 사용하여 구성원 큐의 확장한계를 명시하는 방식이 고려될 수 있다. 또한 각 내부 큐를 환형의 큐로 구현하는 방식도 가능하다. |
|
큐의 응용 : 대표적인 예로 CPU 작업 스케쥴링 기법이 있으며, 일괄 처리 작업에 있어서 작업이 받아들여진 순서대로 읽혀지고 수행될 때 큐를 형성하게 됩니다. 큐는 작업의 우선 순위의 방법을 무시한 것인데 우선 순위를 사용하게 되면 각 우선 순위에 대해서도 하나의 큐가 사용되어집니다. 통신할 프로세스의 선택 또는 여러 시스템에서의 시뮬레이션을 위한 모델링 등에서도 사용될 수 있으며 이 외에도 우체국, 슈퍼마켓, 공장의 작업장 등 실생활에서도 큐는 많이 발견되며 이러한 큐 시스템에서 큐의 효율적인 이용은 전체 시스템의 성능에 많은 영향을 주게 됩니다. 특히, 산업 공학 등의 학문영역에서는 시스템의 성능 평가를 위해 대기 행렬 이론을 다루고 있습니다. |
| 큐에 대해서 공부하기 (0) | 2008/05/14 |
|---|---|
| 스택(Stack) 공부하기 (0) | 2008/05/14 |
| 자료구조 공부하기 (0) | 2008/04/15 |
|
※ 스택의 정의 : 스택(stack)이란 쌓아 올린 더미를 의미하는 것으로서 데이터 구조에서는 기억장치에 데이터를 일시적으로 겹쳐 쌓아두었다가 필요할 때 꺼내서 사용할 수 있도록 주기억장치나 레지스터의 일부를 할당하여 사용하는 임시적인 기억 장치를 말한다. 스택은 선형 리스트 구조의 특별한 형태로서 리스트내의 데이터의 삽입과 삭제가탑(top)이라 불리우는 한쪽 끝에서만 일어나는 데이터 구조를 말합니다. |
|
※ 스택의 구조 : 기본적인 자료구조의 하나로, 나중에 넣은 값이 먼저 나오는 구조를 가지고 있다. LIFO(Last In First Out)이라고 부르기도 한다. 스택에 새 데이터를 추가하는 것을 푸시(push), 빼내는 것을 팝(pop)이라고 한다. 가장 최근에 추가된 데이터부터 빼내게 된다. 예를 들어, a, b, c를 차례로 푸시한 다음 팝 동작을 하면 값이 c, b, a의 순서로 나오게 된다.다수의 컴퓨터에서 포인터를 이용하여 실제 사용되고 있으며, 함수를 호출할 때 인수의 전달 등에 이용된다. LIFO의 특징을 이용하여 역폴란드 표기법을 이용한 프로그래밍 언어인 포스(Forth) 등에 이용되고 있다. |
|
|
스택을 사용하는 분야는 많지만 그 중에서도 서브루틴의 복귀 주소를 저장하는데 주로 많이 사용됩니다. 수행 시간 동안 스택은 현재 수행중인 프로그램(또는 함수, 서브루틴 등)에 대한 적당한 정보를 기록하기 위해 프로그램 수행중에 사용됩니다. 스택에 저장되는 정보로는 수행중인 함수의 이름이나 주소, 수행이 다시 시작되는 주소, 수행 상태에서만 사용 가능한 데이터의 값, 그리고 수행이 다른 루틴으로 옮겨질 때의 레지스터의 내용 등을 포함합니다. |
|
※ 스택의 표현과 연산방법 스택을 표현하는 데에는 일반적으로 크게 두가지 방법이 있습니다. 첫째 : 스택이 포함할 수 있는 항목의 최대 크기를 알 수 있을 때 1차원 배열로 표현하는 방법 둘째 : 스택의 최대 크기를 알 수 없을 때 이를 연결 리스트로 표현하는 방법 |
|
※ 스택의 연산 Push(x, s) - x라는 항목을 s라는 스택 맨위에 삽입 Pop(s) - 스택 s의 맨위에 있는 항목을 리턴하고 삭제 Initialize(s) - 비어있는 스택을 생성 Full(s), Empty(s) - 스택 s에 대해 Push 및 Pop 연산을 적용할 수 있는지 확인 |
|
※ 스택의 배열 구현 CREATE() : 하나의 공백 스택 S를 만든다. TOP(S) : 스택 S의 top에 있는 항목(예 : 데이터 원소)을 결과로 반환한다.(return) PUSH(x.S) : 스택 S에 새로운 항목 x를 삽입하고, 그렇게 해서 바꿔진 스택을 결과로 반환한다. POP(S) : 스택 S의 top에 있는 항목을 삭제하고 그렇게 해서 바꿔진 스택을 결과로 반환한다. EMPTY(S) : 만약 스택 S가 공백이면 참을, 아니면 거짓을 결과로 반환한다. |
|
※ 스택을 배열로 구현하는 방법 |
스택을 연결리스트로 구현하는 방법 |
