DSA37 덱 (Deque) 덱 (Deque)덱이란 double-ended queue의 줄임말로서 큐의 front와 rear에서 모두 삽입과 삭제가 가능한 큐를 의미한다.ADT Deque객체 : n개의 element형의 요소들의 순서 있는 모임연산 : create() ::=intit(dq) is_empty(dq)is_full(dq)add_front(dq,e)add_rear(dq,e)delete_front(dq)delete_rear(dq)get_front(q)get_rear(q) 덱은 스택과 큐의 연산들을 모두 가지고 있다.add_front와 delete_front 연산은 스택의 push와 pop과 동일하다.add_rear와 delete_rear 연산은 큐의 enqueue와 dequeue과 동일하다.만약 덱의 front와 관련된 연산.. 2024. 7. 25. 원형큐 (Circular Queue) 원형큐 (Circular Queue)선형큐에서 삽입과 삭제를 하다보면 rear가 배열의 끝에 도달하게되는데 이때 더이상 삽입이 불가능해진다.따라서 이럴때는 배열의 요소들을 왼쪽으로 이동시켜줘야하는 불편함이 있다.이를 해결하기 위해 고안된 것이 바로 원형큐 (Circular Queue)이다.원형큐는 배열의 끝과 처음이 이어져있다고 생각하면 된다.front가 -1로 초기화되는 선형큐와는 다르게front와 rear가 처음에는 모두 0으로 시작하고 따라서 공백 검사 알고리즘도 if(front==rear)이다.포화 검사 알고리즘은 선형큐와 같다. if(rear==MAX_SIZE_QUEUE-1)이다.다음은 원형큐의 삽입, 삭제 알고리즘이다.삽입 알고리즘enqueue(Q,x):rearQ[rear]삭제 알고리즘dequ.. 2024. 7. 24. 큐 (queue) 큐 (queue)는 먼저 들어온 데이터가 먼저나가는 선입선출 (First-in First-out)이라고 한다.구조상 큐가 스택과 다른점은 스택은 삽입과 삭제가 같은 쪽에서 일어나지만 큐는 다른 쪽에서 일어난다.큐에서 삽입이 일어나는 곳을 rear라 하고 삭제가 일어나는 곳을 front라고 한다.ADT queue객체 : 0개 이상의 요소들로 구성된 선형 리스트연산:create(max_size) ::= 최대 크기가 max_size인 공백큐를 생성한다.init(q) ::= 큐를 초기화한다.is_empty(q) ::= q가 공백이면 TRUE, else FALSEis_full(q) ::= q가 full이면 TRUE, else FALSEenqueue(q,e) ::= if(is_full(q) ) else q의 끝에 .. 2024. 7. 23. 동적 배열 스택 2024.07.22 - [Algorithm] - 스택 (stack) 스택 (stack)스택은 후입선출의 입출력형태를 나타낸다. (Last-in, First-out)ADT 추상 자료형으로 스택을 나타내면 다음과 같다.객체: 0개 이상의 원소를 가지는 유한 선형 리스트연산:create(size) ::= 최대 크기가 sizkwone.tistory.com int main(void){ StackType t; init_stack(&t); push(&t, 1); push(&t, 2); push(&t, 3); printf("%d\n", pop(&t)); printf("%d\n", pop(&t)); printf("%d\n", pop(&t));} 이전글 구조체를 사용한 스택 구현.. 2024. 7. 22. 스택 (stack) 스택은 후입선출의 입출력형태를 나타낸다. (Last-in, First-out)ADT 추상 자료형으로 스택을 나타내면 다음과 같다.객체: 0개 이상의 원소를 가지는 유한 선형 리스트연산:create(size) ::= 최대 크기가 size인 공백 스택을 생성is_full(s) := is_empty(s)push(s,item)pop(s)peek(s) 전역변수와 1차원 배열을 이용한 스택 구현#include #include #define MAX_STACK_SIZE 100typedef int element;element stack[MAX_STACK_SIZE];int top = -1;int is_empty(){ return (top == -1);}int is_full(){ return (top == (MAX_ST.. 2024. 7. 22. 기수 변환 정수값을 임의의 기수(cardinal number)로 변환하는 알고리즘10진수 정수를 n진수 정수로 변환하려면 정수를 n으로 나눈 나머지를 구하는 동시에 그 몫에 대해 나눗셈을 반복해야 함이 과정을 몫이 0이 될 때까지 반복하고, 이런 과정으로 구한 나머지를 거꾸로 늘어 놓은 숫자가 기수로 변환한 숫자이다. #define _CRT_SECURE_NO_WARNINGS#include /*---type형 x값과 y값을 교환하는 매크로---*/#define swap(type,x,y) do{type t=x;x=y;y=t;}while(0)/*---정수값 x를 n진수로 변환한 숫자 문자의 정렬을 배열 d에 저장---*/int card_conv(unsigned x, int n, char d[]){ char dchar[.. 2024. 7. 16. 이전 1 2 3 4 5 6 7 다음
