본문 바로가기
728x90
반응형

Datastructure/[7] 큐

[7] 큐 ⑥ 응용 : 연결리스트를 이용한 데크 구현 2024. 5. 22. [ 문제 2-데크 ] 데크는 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 자료구조다. 헤드 노드와 테일 노드가 없는 이중연결리스트를 사용하여 아래에 정의된 데크 함수들을 구현하시오. ◦ 초기 상태- 주의 : 연산 수행 도중 원소가 모두 삭제되어 데크가 비는 경우에도, 아래 초기 상태가 되어야 함.◦ 데크 연산- add_front(deque, X) : deque의 앞에 원소 X를 추가 (주 교재의와 동일).- add_rear(deque, X) : deque의 뒤에 원소 X를 추가 (주 교재의와 동일).- delete_front(deque) : deque의 앞에 있는 원소를 반환한 다음 삭제 (주 교재의pop과 동일).- delete_rear(deque) : deque의 뒤에 있는..
[7] 큐 ④ 덱(deque) 2024. 5. 22. 덱(deque)덱(deque)은 double-ended queue의 줄임말로서 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 자료 구조이다.특징1. 배열로도 구현이 가능하고, 연결 리스트로도 구현이 가능하다. 따라서 구현한 자료구조에 따라서 해당 자료구조의 특징을 갖는다.2. 데이터의 맨 앞과 맨 뒤에서만 삽입, 삭제, 접근이 필요할 때 사용하는 것이 바람직하다.장점단점데이터의 앞과 뒤에서만 삽입, 삭제, 접근이 이루어질때 굉장히 빠르게 동작한다. O(1)중간 요소를 접근하거나 중간에 삽입, 삭제가 필요한 작업이 있다면 굳이 채택할 필요가 없다. 덱의 연산시계방향으로 증가하는 함수• delete_front • add_rear • is_full• get_front반시계방향으로 감소..
[7] 큐 ⑤ 응용 : 배열로 구성된 원형 큐 ADT 구현 2024. 5. 22. [ 문제 1-큐 ] 배열로 구성된 원형 큐를 위한 삽입, 삭제 프로그램을 작성하시오.◦ 주요 전략 : 본 문제의 원형 큐에서는 포화 상태와 공백 상태를 구분하기 위해 한 자리를  비워둠. - front, rear, 배열의 초기 값은 0 - 삽입 시 rear 값을 하나 증가시킨 후 데이터를 큐에 삽입 (출력 예시 1 참고) - 삭제 시 front 값을 하나 증가시킨 후 front가 가리키는 데이터를 삭제 - front = rea r면 공백 상태로 정의하고, front가 rear보다 하나 앞에 있으면 포화 상태로 정의함  ※ 주의  주교재가 제시하는 전략에서는 front와 rear가 각각 큐의 맨 앞과 맨 뒤의 원소 위치를 직접 가리키는 방식으로 정의되어 있으나 위 전략은 front가 맨 앞 원소 위치보다 ..
[7] 큐 ③ 연결리스트 ADT 2024. 5. 20. 연결리스트에 기초한 큐단일연결리스트를 사용하여 큐를 구현할 수 있다. ☑ 삽입과 삭제가 특정위치에서만 수행되므로, 역방향링크는 불필요하다. (참고: 스택의 경우 헤더노드 불필요)☑ front 원소를 연결리스트의 첫 노드에, rear 원소를 끝 노드에 저장하고 f와 r로 각각의 노드를 가리키게 한다. • 기억장소 사용: O(n)• 큐 ADT의 각 작업: O(1)헤더 및 구조체 선언#include #include #include typedef char element;#define MAX 10typedef struct QueueNode { element data; struct QueueNode* next;} QueueNode;typedef struct { QueueNode* front; ..
[7] 큐 ② 배열 ADT 2024. 5. 20. 큐(QUEUE) : 먼저 들어온 데이터가 먼저 나가는 자료구조선입선출(FIFO: First-In First-Out) 순서를 따른다. (예) 매표소의 대기열  큐 ADT• 큐 ADT는 임의의  삽입과 삭제는 선입선출(First-In First-Out, FIFO) 순서를 따른다.• 큐 ADT는 대기열을 추상화한 데이터 구조이다. 삽입은 큐의 뒤(rear), 삭제는 큐의 앞(front)이라 불리는 위치에서 수행된다.큐 메쏘드주요 큐 메쏘드 ❖ enqueue(e): 큐의 뒤에 원소를 삽입 ❖ element dequeue(): 큐의 앞에서 원소를 삭제하여 반환 보조 큐 메쏘드 ☉ element front(): 큐의 앞에 있는 원소를 (삭제하지 않고) 반환 ☉ integer size(): 큐에 저장된 원소의 수를 ..
[7] 큐 ① 2024. 3. 3. 큐스택과 동일하게 데이터를 일시적으로 쌓아놓은 자료 구조로 가장 먼저 넣은 데이터(프런트)를 가장 먼저 꺼내게 된다.선입 선출(FIFO, First In First Out) ▶ 인큐 : 큐에 데이터를 넣는 작업▶ 디큐 : 데이터를 꺼내는 작업▶ 피크 : 맨 앞의 데이터를 확인 데이터를 꺼내는 쪽을 프런트라고 하고, 데이터를 넣는 쪽은 리어라고 한다.일반적인 큐에서는 디큐 과정에서 프런트에 있는 값이 제일 먼저 빠지므로 두 번째 이후의 요소는 하나 씩 앞쪽으로 이동해야 한다. 이 처리의 복잡도는 O(n)이다.큐 구조체 (IntQeue)아래 코드는 큐를 관리하는 구조체로 3개의 멤버와 프런트/리어로 구성된다. 이때 앞서 다룬 스택 포인터는(스택에 저장된 데이터 개수) pst으로 선언했으나 큐에서는 큐에 저..
728x90
반응형

티스토리툴바