반응형 C4 Queue - C와 Python 비교 - 2 지난 원형큐 설명에 이어 deque(덱 큐)에 대해 설명하겠다. 덱 큐는 원형큐에 비해 매우 파워풀하다. 원형큐는 front가 삭제 rear가 삽입으로 정해져 있었다면 그에 비해 덱큐는 front와 rear가 모두 삭제와 삽입이 자유롭다는 것이다. 사실 이는 덱이라고 불리지만 원형큐로 구현하면 시간복잡도가 O(1) 이기 때문에 효율적이다. 그래서 덱큐라고 명칭한다. 덱큐와 원형큐가 다른 점은 앞서 말했듯이 front와 rear가 모두 삭제가 가능하다는 것이다. 이를 구현하기 위해선 원형큐에선 시계방향의 회전만 했다면 덱큐는 반시계방향 회전을 한다. 이로 인해 delete_rear와 add_front가 구현될 수 있다. 덱큐는 원형큐를 상속하여 구현해보겠다. 일단 python코드이다. # 덱큐 -> 원형큐.. 2020. 7. 13. Queue - C와 Python 비교 Queue는 대표적인 FIFO(First In First Out) 알고리즘이다. 즉 선입선출으로 먼저 들어온 값이 먼저 나가는 구조이다. LIFO구조인 stack과 비교된다. 구조상으로 스택과 다른 점은 삽입과 삭제 연산의 위치가 다르다는 것이다. 스택은 맨 위에부터 꺼내 쓰고 꺼내서 빼는 구조로 삽입과 삭제 연산의 위치가 같지만 Queue는 앞뒤에 문이 있다고 생각하면 된다. 따라서 앞의 문은 front, 뒤에 문은 rear 이다. 삽입이 일어나는 곳은 rear, 삭제가 일어나는 곳은 front 이다. 기본적으로 큐의 종류는 선형큐,원형큐,덱큐,우선순위 큐가 있다. 이 중 가장 기본적으로 선형큐의 구현을 보여줘야하지만 선형큐는 다른 큐에 비해 비효율적인 면이 있다. 왜냐하면 삭제연산에서 리스트의 모든 .. 2020. 7. 13. Stack - C와 Python 비교(2) 스택의 예시로 많이 쓰는 것은 괄호 검사기이다. 프로그래밍을 하다보면 insert가 눌려져서 괄호가 하나씩 없거나 많아서 오류난 경험이 한 번 씩은 있을것이다. 이를 검사하는 프로그래밍을 할 것이다. 일단 C로 한 번 구현해보겠다. #include #include #define MAX_STACK_SIZE 100 typedef int element; typedef struct { element data[MAX_STACK_SIZE]; int top; }StackType; void init_stack(StackType* s) { s->top = -1; } int is_empty(StackType* s) { return (s->top == -1); } int is_full(StackType* s) { retur.. 2020. 7. 3. Stack - C와 파이썬 비교(1) 스택은 자료구조의 기본이라고 할 수 있다. 스택의 특징은 후입선출(LIFO)이다. 즉, 마지막에 들어간 것이 처음에 나온다고 생각하면 된다. 스택의 말 뜻처럼 쌓는다고 생각하면 편하다. 예를 들어 밑넓이는 좁고 높이가 긴 직육면체의 상자가 있다 생각해보자. 여기에 물건을 넣었을 때 맨 밑의 물건을 꺼내기 위해선 안에 있는 모든 물건을 빼야한다. 스택은 이런 것이다. 자세한 것은 밑의 링크를 참조하면 된다. https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D 스택 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdo.. 2020. 7. 3. 이전 1 다음 반응형
