CS/Data Structure3 [자료구조] Swift로 구현하는 Queue (큐) 큐의 개념 큐는 아래의 그림과 같이 한 쪽 끝에서는 자료의 삽입 연산만 가능하고 반대쪽 끝에서는 삭제만 가능한 자료구조이다. 이러한 특성을 가리켜 선입선출(FIFO: First In First Out)이라고 한다. 대표적인 예로 마켓에서 계산을 위해 계산대 앞에서 줄을 서서 기다리고 있는 사람들을 떠올리면 된다. 가장 먼저 도착한 사람이 먼저 계산을 할 수 있고 마지막에 도착하는 사람은 제일 끝에서 자신의 차례를 기다린다. 큐에는 선형큐, 원형큐 그리고 우선순위 큐등 여러 종류가 있는데 여기서는 가장 기본적인 선형큐에 대해서 알아본다. 큐에서 사용되는 연산 큐에서 사용되는 연산의 종류는 다음과 같다. count : 큐에 들어있는 자료의 개수 isEmpty : 큐가 비어있는 지를 체크하기 위한 연산 enq.. 2022. 4. 28. [자료구조] Swift로 구현하는 Linked List (연결 리스트) Linked List (연결 리스트)란? 링크드 리스트는 위의 그림과 같이 데이터를 순차적으로 저장하지 않고 각각 떨어진 공간에 존재하는 데이터를 연결해 놓은 자료구조를 말한다. 위의 그림의 사각형을 노드(Node)라고 하는데 노드는 자신의 데이터와 다음 노드를 연결하는 포인터로 구성되어 있다. Array와 Linked List 배열과 링크드 리스트는 서로 장단점이 명확하다. 먼저 배열을 살펴보자. 배열은 index를 사용하여 한 메모리 공간 안에 데이터를 순차적으로 저장한다. 사용자는 인덱스를 이용해서 원하는 위치에 있는 데이터를 바로 접근할 수 있다. 하지만 배열의 중간에 데이터를 삽입하거나 삭제할 경우 기존의 데이터를 이동시키는 작업이 필요하다. 그렇기 때문에 삽입과 삭제에 있어서 오버헤드가 발생할.. 2022. 4. 20. [자료구조] Swift로 구현하는 Stack Stack이란? 스택은 리스트의 끝(즉, 스택의 맨 위)에서 자료의 삽입과 삭제가 이루어지는 자료구조이다. 가장 최근에 들어온 자료가 가장 먼저 나가게 되는 LIFO(Last In First Out) 형태를 띄고있다. 스택의 입출력은 맨 위(top)에서만 일어나기 때문에 스택의 중간에 데이터를 삽입하거나 삭제하는 것은 불가능하며 top을 중심으로 연산이 이루어진다. 스택에서 사용되는 연산은 다음과 같다. count : 스택에 들어있는 요소들의 개수 isEmpty : 스택이 비어있는 지를 체크 push : 스택에 새로운 요소를 삽입 pop : 스택의 top에 있는 요소를 삭제 top : 스택의 top에 있는 요소 조회 Stack의 기본 구조 struct Stack { // 스택의 요소들을 담아두는 배열 v.. 2022. 4. 17. 이전 1 다음
