안지현

1. 큐란?

1) 개념

- 사전적 의미 : 무엇인가를 기다리는 줄

- 자료구조에서의 의미 : 무언가를 처리하기 위해 대기 중인 자료의 줄, 대기행렬이라고도 함

2) 특성

- FIFO(First-In First-Out) : 선입선출, 가장 먼저 들어간 데이터가 가장 먼저 나옴

3) 사용 예

- 선입선출 특성이 필요한 현실 세계의 다양한 시스템들을 나타낼 때 사용

- ex) 운영체제의 프린터 스풀러 (먼저 처리한 것부터 실행)

4) 구조

- 데이터를 차례대로 저장하는 선형 자료구조

- 새로운 데이터를 맨 뒤인 리어에 추가

- 리어(rear) : 큐에서 맨 나중에 추가한 데이터

         - 맨 앞인 프런트에서 자료를 제거하여 반환

- 프런트(front) : 맨 먼저 추가한 데이터

- 인큐(enqueue) : 새로운 데이터를 추가하는 연산

         - 큐의 크기 : 저장할 수 있는 최대 데이터의 개수 → 오버플로우 방지하기 위해 동적 메모리 사용을 권장

- 디큐(dequeue) : 기존 데이터를 반환하는 연산

         - 프런트가 가리키고 있는 데이터 제거

- 피크(peek) : 가장 오래된 데이터 반환 (데이터 제거 X)

2. 추상 자료형 큐

3. 배열 선형 큐

1) 개념

- 배열로 구현한 선형 큐

2) 단점

- 미리 크기를 지정해야 함

- 배열의 앞부분부터 사용할 수 없는 빈 곳이 생김 (메모리 낭비)

         → 배열 원형 큐를 사용하거나 포인터로 구현한 연결 큐를 사용할 것을 권장

3) 구조

① enqueue()

- 조건식 1 : rear == maxCount – 1 (배열 선형 큐가 가득 찬 상태)

- 조건식 2 : currentCount == maxCount

② isFull()

- 현재 노드 개수 pQueue->currentCount가 최대 노드 개수 pQueue->maxCount와 같다면 배열 선형 큐가 가득 찬 상태

- 조건식 : pQueue->rear == pQueue->maxCount - 1

③ dequeue()

- pReturn->data = pQueue->pData[pQueue->front].data

④ isEmpty()

- 멤버 변수 currentCount의 값이 0이면 현재 큐가 비어 있는 상태

⑤ peek()

- 값을 삭제하지 않는다는 점이 dequeue와 다름

4. 배열 원형 큐

1) 개념

- 빈 노드가 있지만 인큐 연산이 불가능한 배열 선형 큐의 단점 보완

- 조건식 1 : rear = (rear+1) % maxCount

1. 스택이란?

1) 개념

- 선형구조

- 사전적 의미 : 물건이 쌓여 있는 더미

2) 구조

- top : 스택의 가장 윗부분

- bottom : 스택의 가장 아랫부분

- element : 스택에 저장되는 것

- 입출력은 맨 위에서만 일어나고 중간에서는 데이터를 삭제할 수 없음

3) 특징

- 후입선출 : LIFO(Last-In First-Out)

→ 가장 최근에 들어온 입력이 가장 먼저 나가게 됨

      ex) ① PUSH 연산 : 새로운 자료를 스택에 추가하는 과정

           ② POP 연산 : 스택에 저장된 자료를 가져오는 과정

                    → 자료 제거 및 가져오기 연산이 동시에 수행

2. 추상 자료형 스택

- 스택(s)

① 객체 : 0개 이상의 원소를 가지는 유한 선형 리스트

② 연산

3. 스택 구현

- 전역 변수로 구현하는 방법

→ 배열, top 변수를 함수의 매개변수로 전달할 필요 없음

→ 단점 : 하나의 프로그램에서 여러 개의 스택을 동시에 사용하기 어려움

- 스택의 요소 : 구조체로 정의

- 동적 메모리 할당으로 스택 생성

4. 스택의 응용 – 괄호 검사 문제

1) 문제

- 프로그램에서 사용되는 괄호가 올바르게 사용되었는지를 스택을 사용하여 검사하는 프로그램

2) 검사 조건

- 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같음

- 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 함

- 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안됨

3) 괄호 검사 알고리즘

 1. 리스트란? 

1) 정의

- 자료를 순서대로 저장하는 자료구조

- 여러 개의 자료가 일직선으로 연결된 선형 구조

- 배열 리스트 : 배열을 이용하여 구현된 리스트

2) 주의점

- 리스트는 한 줄로 저장

- 줄을 세울 때 앞 항목과 뒤 항목이 1개로 연결되는 구조

3) 배열과 배열리스트

- 배열 : 같은 자료형의 데이터가 메모리 상에 연속적으로 저장

- 배열 리스트 : 자료가 일직선으로 서로 연결

 2. 자료형 

1) 정의

- 기초적인 자료형 : 정수, 실수, 문자열 등

- 새로운 자료형 : 스택, 큐, 리스트, 트리 등

2) int 자료형

- INT_MIN : 컴퓨터가 나타낼 수 있는 가장 작은 정수

- INT_MAX : 컴퓨터가 나타낼 수 있는 가장 큰 정수

- 복잡한 자료형 구현 시 연산자가 아닌 함수로 작성

3) 추상 자료형 (Abstract Data Type, ADT)

- 추상적, 수학적으로 자료형을 정의한 것

- 자료구조는 추상 자료형을 프로그래밍 언어로 구현한 것

- 자연수를 나타내는 추상 자료형 : Nat_Number

① 객체 : 0~INT_MAX까지의 순서화된 정수의 부분 범위

② 함수

 3. 리스트 ADT 

1) 정의

- 리스트는 자료를 정리하는 방법 중의 하나

2) 리스트 ADT

- 리스트를 추상 데이터 타입으로 정의한 것

① 객체 : n형으로, element형으로 구성된 순서 있는 모임

② 함수

3) 리스트 구현

- 배열을 이용한 구현

① 장점 : 리스트 ADT를 가장 간단하게 구현 가능

② 단점 : 크기 고정 → 메모리 낭비

- 연결 리스트를 이용한 구현

① 장점 : 크기 제한 X, 포인터를 이용한 유연한 진행 가능

② 단점 : 구현이 복잡

 4. 배열 리스트  

1) 정의

- 순차적 표현(sequential representation) : 배열을 이용한 리스트 구현은 순차적인 메모리 공간 할당

- 배열 사용 시 리스트의 항목을 자연스럽게 저장 가능

2) 실습