자료구조

1. 큐 ADT

큐란? 선입선출(FIFO : First-In First-Out) : 스택의 경우, 나중에 들어온 데이터가 먼저 나가는 구조인데 반하여 큐는 먼저 들어온 데이터가 먼저 나가는 구조 큐의 예로는 매표소에 표를 사기 위해 늘어선 줄을 들 수 있다 줄에 있는 사람들 중 가장 앞에 있는 사람이 가장 먼저 표를 사게 될 것이다. 그리고 나중에 온 사람들은 줄의 맨 뒤에 서야 할 것이다 큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 가지고 있다. 구조상으로 큐가 스택과 다른 점은 스택의 경우, 삽입과 삭제가 같은 쪽에서 일어나지만 큐에서는 삽입과 삭제가 다른 쪽에서 일어난다는 것이다. 후단 (rear) :큐에서 삽입이 일어나는 곳 전단 (front) : 큐에서 삭제가 일어나는 곳 큐의 ..

3. 스택의 응용

괄호 검사 문제 수식의 계산 미로 문제 ft. C언어 미로 문제(maze solving problem) 미로에 갇힌 생쥐가 출구를 찾는 문제이다 미로가 서로 연결된 여러 개의 작은 방 또는 칸으로 구성되어 있다고 가정하자 생쥐가 출구를 찾는 기본적인 방법 : 시행착오 방법으로 하나의 경로를 선택하여 한번 시도해보고 안되면 다시 다른 경로를 시도하는 것이다. 문제는 현재의 경로가 안 될 경우에 다른 경로를 선택해야 한다는 것으로 다른 경로들이 어딘가에 저장되어 있어야 한다. 그러면 현재 위치에서 가능한 경로 중에서 가장 가까운 경로이면 좋을 것이다 따라서 가능한 경로들이 저장되는데 그중에서 가장 최근에 저장한 경로가 쉽게 추출되는 자료구조인 스택이 가장 적합하다 구체적으로 현재 위치에서 갈 수 있는 방들의..

2. 스택의 구현

https://blogshine.tistory.com/36 [자료구조] C++로 쉽게 풀어쓴 자료구조 : 6장, List 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 6장. 리스트 앞에서 배운 스택, 큐, 덱과 같이 리스트 또한 선형 자료구조 이다. 선형이란 blogshine.tistory.com 배열은 순차적인 메모리 공간에 할당된다고 해서 순차적 표현(sequential representation)라고도 한다. 배열을 이용한 스택의 표현 스택을 가장 간단하게 구현할 수 있는 방법은 배열을 이용하는 것이다. 정수를 저장할 스택을 만들려면 정수의 1차원 배열이 있어야 하고 이를 data[MAX_STACK_SIZE]라고 부른다. 이 배열을 이용하여..

1. 스택 ADT

스택이란? 스택을 영어사전으로 찾아보면 '(건초, 밀집 따위를 쌓아 놓은) 더미, 낟가리'를 의미한다 식당에 쌓여있는 접시 더미, 책상에 쌓여있는 책, 창고에 쌓여있는 상자 등이 스택의 전형적인 예이다. 입출력 형태 : 후입선출 (LFO : Last-In First-Out) 창고에서 새로운 상자들을 쌓을 때는 상자더미의 맨 윗부분에 놓는다. 상자가 필요하면 상자더미의 맨 위에 있는 상자를 꺼낸다. 따라서 가장 최근에 들어온 상자가 가장 위에 있고, 또 먼저 나가게 된다. 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. 스택 상단 (stack top) : 스택에서 입출력이 이루어지는 부분 스택 하단 (stack bottom) : 반대쪽인 바닥 부분 요소 (element..

3. 연결 리스트로 구현된 리스트

연결 리스트 (linked list) 연결된 표현 (linked representation) : 동적으로 크기가 변할 수 있고 삭제나 삽입 시에 데이터를 이동할 필요가 없는 표현 => 포인터를 사용하여 데이터를 연결함 => 리스트 뿐만 아니라 다른 자료구조 (트리, 그래프, 스택, 큐)등을 구현한는데도 많이 사용됨 연결 리스트 : 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법 => 상자를 연결하는 줄은 포인터(pointer)로 구현됨 장점 중간에 삽입(삭제)하는 문제가 쉽게 해결됨 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들엇 쉽게 추가할 수 있음 단점 배열로 구현한 리스트에 비하여 상대적으로 구현하기 어려워서 오류가 나기 쉬움 데이터뿐만 아니라 포인터도 저장해야 하므로 ..

1. 리스트

1. 리스트의 추상 자료형 - 리스트의 개념 리스트 : 목록 형태로 이뤄진 데이터 형식 노드 (Node, 마디) : 리스트의 목록을 이루는 개별 요소 첫 번째 노드를 헤드 (Head, 머리) 라고 부르고 마지막 노드를 테일 (Tail, 꼬리) 이라고 부른다 리스트의 길이는 헤드부터 테일까지 이르는 노드 개수와 같다 ADT는 자료구조가 갖춰야 할 일련의 연산 리스트도 갖춰야 할 연산이 있는데 Append : 리스트에 노드를 추가하는 연산 Insert : 노드 사이에 노드를 삽입하는 연산 Remove : 노드를 제거하는 연산 GetAt : 특정 위치에 있는 노드를 반환하는 연산 - 리스트의 구현 리스트는 배열과 연결 리스트를 이용하여 구현할 수 있음 배열로 구현된 리스트 장점 구현이 간단 속도가 빠름 단점 ..