Kang-ji

스택(Stack) 

스택(Stack)이란?

한 쪽 끝에서만 자료를 넣고 뺄 수 있는  후입 선출의 구조로, LIFO(Last In First Out) 형식의 자료 구조

스택(Stack)의 연산

스택(Stack)는 LIFO(Last In First Out) 를 따른다. 즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다. (입구와 출구가 동일지점으로 데이터의 삽입과 삭제가 한방향에서만 이루어진다.)

• push(item): 삽입연산. item 하나를 스택의 가장 윗 부분에 추가한다.
• pop(): 삭제 연산. 스택에서 가장 위에 있는 항목을 제거한다.
• top : 삽입과 삭제가 일어나는 위치를 Top이라고 한다.
• peek(): 스택의 가장 위에 있는 항목을 반환한다.
• isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

스택(Stack)의 사용사례

• 웹브라우저 방문기록 (뒤로가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 실행 취소 : 가장 나중에 실행된 것부터 실행취소
• 역순 문자열 만들기 :가장 나중에 입력된 문자부터 출력
• 후위 표기법 계산
• 안드로이드의 액티비티
• 수식의 괄호 검사 : 연산자 우선순위 표현을 위한 괄호 검사

큐(Queue)

큐(Queue) 란?

먼저 들어온 것이 먼저 나가는 선입선출로 FIFO(First In First Out) 형식의 자료구조

큐(Queue) 의 연산

규에서 데이터의 삽입과 삭제 연산을 주로 enQueue와 deQueue라 칭한다. 

스택과 다르게 입구와 출구가 각각 나위어져 있다. 

이때 출구는 머리(Front)로 정해 삭제연산만 수행하고, 입구는 꼬리(Rear)로 정해 삽입연산만 수행한다. 

• enqueue(): 꼬리, 리어(rear)에서 이루어지는 삽입연산.
• dequeue(): 머리, 프론트(Front)에서 이루어지는 삭제 연산.\

큐(Queue)의 사용사례

큐는 주로 데이터가 입력된 시간 순서대로 처리해야할 필요가 있는 상황에 이용한다. 

• 은행업무
• 대기열 순서와 같은 우선순위의 작업예약
• 서비스 센터의 대기시간
• 프로세스 관리
• 너비 우선탐색(BFS, Breadth First Search) 구현
• 캐시(Cache) 구현

연속 리스트(Contiguous List) 

배열처럼 연속적인 기억 장소에 데이터가 저장되는 자료구조. 

연속적으로 데이터가 저장되어있어 검색에는 용이하지만, 데이터의 삽입이나 삭제에 단점이있다. 삽입과 삭제가 일어나는 경우 자료의 이동이 필요하다는 번거로움이 있다.

연결 리스트(Linked List)

데이터를 임의기억공간에 기억시키되, 데이터 항목의 순서에에 따라 노드의 포인터를 이용하여 서로 연결시킨 자료구조. 

새로운 데이터를 추가하고 삭제하는 것이 용이하고 효율적이다.

배열처럼 메모리에 연속적으로 위치하지 않고 구조의 재구성이 필요없다. 메모리를 더 효율적으로 사용할 수 있기 때문에 

대용량의 데이터 처리에 적합하다. 하지만 연결이 끊어지면 다음 노드를 찾기가 어렵고 속도가 느리다는 단점이 있다. 

연결리스트 구분

연결방향에 따라 단일 연결 리스트, 연결리스트, 이중연결리스트, 환형 연결리스트가 있다. 

단일 연결 리스트

각 노드에 자료공간과 한개의 포인터 공간이 있고 각 노드의 포잍너는 다음 노드를 가리킨다.

이중연결리스트

단일 연결리스트와 비슷하지만 포인터 공간이 두개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다. 

원형 연결리스트

일반적인 연결리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조

배열 (Array)

배열(Array)이란? 

가장 기본적인 데이터구조로 연속된 메모리 공간에 순차적으로 저장된 데이터 모음.

생성되는 순간 설정되는 셀에 인덱스가 부여되고 해당 셀의 개수는 고정된다.

이때 부여된 인덱스를 통해 원하는 데이터에 겁근할 수 있다.

배열은 바로 만들어서 사용하기가 쉽고 원하는 데이터를 효율적으로 검색하여 가져오는게 가능하다. 

배열을 기반으로 더 복잡한 자료 구조를 만들 수 있으며 정렬이 용이하다는 장점이 있다. 

대부분의 프로그래밍 언어에서 동일타입의 데이터를 저장한다. 

배열을 구성하는 각각의 값을 Element라고 하며, 배열에서의 위치를 가리키는 숫자는 Index라고 한다. 

배열(Array)의 단점

생성될 때 셀의 개수가 고정되므로 데이터를 저장할 수 있는 메모리의 크기가 고정되어 있고 데이터를 추가, 삭제하는 과정이 비효율적이다. 

데이터가 삭제되고 나면 남은 셀은 빈공간이 되므로 메모리 낭비가 심하다. 

배열(Array)의 사용사례

• 순차적인 데이터를 저장하며 값보다는 순서가 중요할때 (주식 가격, 대회결과, 날씨 등)
• 다차원 데이터를 다룰때 (배열 안의 배열이 필요할 경우)
• 어떤 특징의 요소를 빠르게 읽어야 할때 (인덱스로 바로 불러와야 할경우)
• 데이터 사이즈가 자주 바뀌지 않으며 요소가 삭입/삭제 작업이 적을 때