반응형 자료구조2 큐와 스택, 데크는 뭘까? 큐와 스택, 데크 일렬로 늘어선 같은 형태의 자료들을 저장한다. 셋의 차이는 어느 쪽 끝에서 자료를 넣고 뺄 수 있는가 이다. 셋 다 O(1)에 이루어진다. push : 자료를 넣는 것 pop : 자료를 빼는 것 큐 선입선출 가장 먼저 들어간 자료 순으로 빠진다. 줄서기 스택 후입선출 가장 늦게 들어간 것 순으로 빠진다. 컨텍스트 관리 데크 양쪽 끝에서 자료들을 넣고 뺄 수 있다. 스택과 큐를 모두 구현 가능하다. 19.2 큐와 스택, 데크의 구현 연결 리스트 양쪽 끝에서 추가와 삭제를 모두 상수 시간에 할 수 있다. 노드의 할당과 삭제, 포인터를 따라가는데 드는 시간이 걸리기 때문에 가장 효율적이진 않다. 동적 배열 스택은 쉽게 가능하다. 하지만 앞에서 추가와 삭제가 일어나는 것은 동적 배열에서 쉽지 .. 2024. 4. 17. 선형 자료 구조는 뭘까? 18.2 동적 배열 배열을 이용해 만들어낸 별도의 자료 구조이기 때문에 배열의 특징을 그대로 받는다. 원소들은 메모리의 연속된 위치에 저장된다. 캐시의 효율성과 직결되어 중요한 포인트 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다. O(1)? 시간복잡도 개념에서 상수를 의미한다. 입력에 관계없이 복잡도가 동일하게 유지된다. 동적 배열만의 특징은 아래와 같다. 배열의 크기를 변경하는 resize() 연산이 가능하다. 이 동작을 수행하는 데는 배열의 크기 N에 비례하는 시간이 걸린다. 주어진 원소의 배열의 맨 끝에 추가함으로써 크기를 1 늘리는 append() 연산을 지원한다. 이 동작을 수행하는 데는 상수 시간이 걸린다. 동적 배열의 크기가 바뀌는 과정은 아래와 같다. 새 배열을 .. 2024. 4. 17. 이전 1 다음 728x90 반응형
