대기열 시물레이션 큐의 선입선출 특성을 이용하여 다양한 시물레이션을 진행할 수 있다. 지금 해볼 것은 대기열에서 평균 대기 시간이 얼마나 되는지 이다. 예를 들어 한 손님이 은행에 갔다고 생각해보자. 은행에 들어가면 앞에 손님이 없다면 바로 서비스를 받을 수 있지만 손님이 있다면 먼저 온 손님이 모두 서비스를 받고 난 후에야 서비스를 받을 수 있을 것이다. 우리는 이러한 상황을 구현하여 어떤 손님이 은행에서 서비스를 받을 때까지의 대기 시간은 얼마이며, 은행이 문을 닫을때까지 손님들의 총 대기 시간, 평균 대기 시간을 예측할 것이다. 먼저 시물레이션에 사전 조건에 대해서 설명하자면 서비스를 처리하는 곳(은행 창구)는 1개이다. 그리고 손님의 정보로는 도착 시간, 서비스를 처리하는데 드는 시간(서비스시간)..

연결 리스트로 구현한 큐 연결 리스트로 구현한 큐의 장점은 미리 큐의 최대 크기를 정하지 않아도 된다는 점이다. 미리 최대 크기를 정하지 않기 때문에 배열 큐에서 빈공간이 있어도 리어 노드 앞에 공간이 없어 인큐 연산을 못하는 경우가 생기지 않기 때문에 메모리를 좀더 효울적으로 사용이 가능하다. 연결 리스트 큐의 구현 얀결 리스트를 이용해 스택을 구현할 때와 마찬가지로 연결 리스트를 사용하는데 연결 리스트를 통째로 사용하기 보다는 큐의 프런트 노드와 리어 노드에 대한 접근만 하면 되기 때문에 프런트 노드와 리어 노드를 가리키는 포인터만 사용한다. 각 함수 중간에 LQ가 있는데 LinkedQueue을 의미한다. 소스 파일 구성은 다음과 같다. 파일 이름 내용 linkedqueue.h 구조체 및 함수 선언 ..

배열 큐(Array Queue)란? 배열을 이용해 구현한 큐를 의미한다. 1차원 배열을 이용하기 때문에 자료들끼리 물리적으로도 연결되어 있고 배열 생성하기 전에 배열의 크기를 미리 정해주어야 한다. 배열로 만든 큐는 자료의 추가/제거를 반복하다 보면 빈 공간이 있음에도 이를 인식하지 못하는 경우가 생겨 메모리가 비효율적으로 쓰이는 문제점이 있다. 이는 다음에 구현해볼 배열을 이용한 원형 큐, 연결 리스트를 이용한 큐로 이를 해결할 수 있다. 각 함수 중간에 AQ가 있는데 ArrayQueue을 의미한다. 배열 큐의 구현 소스 파일 구성은 다음과 같다. 파일 이름 내용 arrayqueue.h 구조체 및 함수 선언 arrayqueue.cpp 함수 구현 arrayqueuemain.cpp main 함수 실행 1...

큐(Queue)이란? 큐도 자료를 차례대로 저장하는 선형 자료구조이다. 큐가 가지는 고유 특성은 FIFO(First-In-First-Out) - 선입선출(先入先出), 즉, 가장 먼저 들어간 자료가 가장 먼저 나오는 자료이다'라는 특성이다. 일상생활에서도 큐라는 단어를 자주 접한다.. 예를 들어 식당에 들어가기 위해 길게 늘어진 사람들의 줄을 대기열 혹은 큐라고 말한다. 큐가 길다는 말은 기다리는 사람들이 많아서 시간이 오래 걸린다는 의미로도 사용한다. 이러한 큐에 특징은 선입선출의 특성을 가진다. 스택에서는 스택의 특성 때문에 모든 연산이 스택의 제일 위(Top)에서 일어난다. 큐에서는 자료를 추가할 때는 뒤에서 추가하고 자료를 반환할 때는 앞에서 자료를 빼가기 때문에 스택보다 좀 더 생각해야 하는 부분..

배열 스택(Array Stack)란? 배열을 이용해 구현한 스택을 의미한다. 배열 리스트와 마찬가지로 물리적으로 연결되어있어야 하며 그에 따라 스택을 생성할 때 무조건 스택의 크기를 미리 지정해 주어야 한다. 각 함수 중간에 AS가 있는데 ArrayStack을 의미한다. 배열 스택의 구현 소스 파일 구성은 다음과 같다. 파일 이름 내용 arraystack.h 구조체 및 함수 선언 arraystack.cpp 함수 구현 arraystackmain.cpp main 함수 실행 1.arraylist.h #pragma once #include using namespace std; #define TRUE 1 #define FALSE 0 typedef struct ArrayStackNode { int data; }; ..

연결 리스트로 구현한 스택 앞서 배운 연결 리스트를 이용하여 구현하는 스택이다. 이러한 방식의 스택의 장점은 미리 스택의 크기를 정하지 않아도 되어 실제 사용하는 자료의 양보다 배열의 크기가 더 클 때 발생하는 메모리 공간 낭비가 일어나지 않는다는 점이다. 그러나 구현은 비교적 어렵다. 연결 리스트로 구현한 스택에서는 노드에 대해 위치 인덱스를 이용한 접근이 불가능하기 때문에 앞서 연결 리스트를 구현했을 때 사용한 헤더 노드와 비슷하게 스택의 탑에 위치한 노드에 접근하기 위한 포인터가 필요하고 push, pop 연산을 실행할 때마다 스택의 탑 노드에 대한 링크를 재설정해주어야 한다. 또한 pop 연산 시 기존에 탑 노드가 사라지면 그다음 위에 있는 노드에 접근할 수 있게 스택의 탑 노드부터 맨 아래에 저..

스택(Stack)이란? 영어 단어 stack은 ‘쌓다‘‘쌓다 ‘라는 뜻이 있고 명사로는 물건들이 쌓여있는 '더미'를 의미한다. 자료구조에서의 스택도 자료를 쌓아두는 기능을 한다. 일반적인 ’더미‘’ 더미‘와 다르게 스택은 스택만의 고유 특성을 가지고 있다. 그 특성은 LIFO(Last-In-First-Out) - 후입선출(後入先出), 즉, 가장 나중에 들어간 자료가 가장 먼저 나오는 자료이다'라는 특성이다. 이러한 특성 때문에 스택에서 자료를 꺼낼 때에는 앞서 배운 리스트와 다르게 가장 나중에 들어간 자료만 꺼낼 수 있다. 추가적으로 스택은 선형 자료구조로, 선형의 의미는 저장된 자료들 사이의 선후관계가 모두 1대11대 1 관계라는 뜻이다. 다시말해 하나의 물건 위에는 오직 하나의 물건만을 쌓을 수 있다..

이중 연결 리스트(Doubly Linked List)란? 이중 연결 리스트는 노드들이 양방향으로 연결되어 있는 연결 리스트를 말한다. 그림과 같이 이중 연결 리스트는 노드들을 양방향으로 연결하기 위해 링크를 2개씩 가지고 있다. 이때 왼쪽으로 가는 링크는 pLLink 오른쪼으로 가는 링크는 pRLink라고 할것이고 이중 연결 리스트에서는 다음과 같은 식이 성립한다. pNode==pNode->pLLink->pRLink; 이중 리스트의 장점 원형 리스트는 양방향으로 연결되어 있기 때문에 어떠한 노드에 접근할때 정해진 방향으로만 가야하는 단순 연결 리스트,원형 연결 리스트에 비해 용이하다. 예를 들어 위치 인데스 position에 존재하는 노드를 이용해 position 이전에 있는 노드에 접근하라고 한다면 단..

원형 연결 리스트(Circular Linked List)란? 기본적인 구조는 단순 연결 리스트와 똑같은 구조지만 맨 마지막 노드의 링크가 NULL값인 단순 연결 리스트와 다르게 원형 연결 리스트에서 맨 마지막 노드의 링크는 맨 처음 노드를 가리킨다. 따라서 노드끼리 연결된 형태가 원형을 이루고 순환구조라는 점에서 차이가 있다. 그림과 같이 원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리킨다. 이때 노드가 딱 1개 존재하는 경우가 생길 수도 있는데 이때 그 노드는 첫 번째 이자 마지막 노드이기 때문에 그 노드의 링크는 자기 자신을 가리키게 된다. 원형 리스트의 장점 만약 연결 리스트 위에서 어떠한 위치에 존재하는 노드의 이전에 위치하는 노드를 탐색한다고 가정해보자 단순 연결 리스트에서 현재 노드의 ..

연결 리스트(Linked List)란? 연결 리스트는 배열 리스트와 다르게 포인터를 이용하여 구현한다. 포인터를 이용하여 순차적으로 자료를 연결하기 때문에 물리적으로 각 자료들이 어디에 위치해 있는지 상관이 없어진다. 아래 그림과 같이 각 자료들이 어디에 물리적 위치는 인접해 있지 않지만 자료들은 순차적으로 연결되어 있다. 추가적으로 연결 리스트는 배열 리스트와 다르게 저장 가능한 최대 원소의 개수를 지정해 주지 않아도 된다. 연결 리스트는 자료들끼리 붙어있어야 한다는 물리적 제약이 없기 때문에 그냥 새로운 원소를 생성하고 포인터를 이용해 연결만 잘해주면 된다. 연결 리스트의 구조 배열 리스트의 노드(원소)는 자료(Data)만 담고 있었지만 연결 리스트의 노드는 자료에 다음 노드로 연결되는 링크(Link..