큐 (연결리스트로 구현)

연결리스트로 큐를 구현하므로 크기에 제약이 없어 큐가 꽉 찼는지 검사할 필요가 없으므로 full() 함수가 필요가 없다. 큐의 기본적인 설명은 '선형 큐 (구조체로 구현)'에서 설명했으므로 생략하겠다. 원형 큐는 선형 큐를 보완한 형태지만, 여전히 배열 때문에 크기에 제약을 받는 단점을 보인다. 연결리스트로 구현한 큐는 이러한 단점을 없애서 큐를 구현할 수 있는 가장 효율적인 방법이라고 볼 수 있다. 구현 #include #include #include typedef struct Node //노드 정의 { int data; struct Node *next; }Node; typedef struct Queue //Queue 구조체 정의 { Node *front; //맨 앞(꺼낼 위치) Node *rear; ..

원형 큐 (구조체로 구현)

원형 큐의 기본 설명은 '원형 큐 (배열로 구현)'에서 이미 했으므로 생략하겠다. 바로 구조체로 구현한 원형 큐의 동작 상태를 볼 수 있는 코드로 넘어가겠다. 원형 큐 구현 #include #include #include #define MAX 5 typedef struct Queue { int queue[MAX]; int front, rear; }Queue; void init_queue(Queue* q) { q->front = q->rear = 0; //front, rear 0으로 초기화 } int empty(Queue* q) { return (q->front == q->rear); } int full(Queue* q) { return (q->front == ((q->rear+1)%MAX)); } voi..

원형 큐 (배열로 구현)

원형 큐 기본 설명 선형 큐의 단점을 되새겨 보면 dequeue() 함수를 실행함으로서 발생하는 사용할 수 없는 공간들이 생겼었다. 즉 그 공간들을 재활용할 수 있는 코드를 구현하지 않는 이상 메모리 누수가 생긴 것이다. 그래서 이런 단점을 보완한 것이 원형 큐이다. 이를 구현한 방법은 예시로 enqueue() 함수를 보이겠다. void enqueue(int data){ if(full()) { printf("큐가 포화상태입니다. 데이터 삽입을 취소합니다.\n"); return; } else { rear = (rear+1)%MAX; queue[rear]=data; } } 위의 함수를 보면 큐가 포화상태가 아닐 시, rear은 rear+1의 MAX로 나눈 나머지 값이 대입된다. dequeue() 함수도 이와..

선형 큐 (배열로 구현)

선형 큐의 기본 설명은 '선형 큐 (구조체로 구현)' 글에서 설명을 했으므로 생략하겠다. 단순 배열로 큐의 동작 상태를 보기 위해 구현한 코드를 바로 보이겠다. 선형 큐의 동작 상태 코드 #include #include #define MAX 5 int front; int rear; int data[MAX]; // 선형 큐 초기화 void init_queue() { rear = -1; front = -1; } // 선형 큐 상태 출력 void queue_print() { for (int i = 0; i

선형 큐 (구조체로 구현)

선형 큐 기본 설명 우선은 큐가 동작하는 모습을 이해하기 위한 코드의 설명을 하고 마지막에 스택을 구현했을 때처럼 직접 입력하는 코드는 따로 보이겠다. 밑의 그림을 보면 큐의 초기 상태는 front와 rear가 둘 다 -1에 있을 때다. 큐는 스택과 달리 먼저 들어온 것이 먼저 나가는 형태다. (FIFO, first in first out) 선형 큐의 동작 원리의 이해를 돕기 위해 몇 가지 동작을 해보겠다. 기본 코드는 다음과 같이 설정한다. #include #include #define MAX 5 typedef struct Queue{ int front; int rear; int data[MAX]; } Queue; [-1] [0] [1] [2] [3] [4] front, rear (NULL) (NULL..

4949: 균형잡힌 세상(BOJ C/C++)

4949번: 균형잡힌 세상(BOJ C/C++) 사용 언어: C 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지..

스택 (연결리스트로 구현)

'백준 10828번: 스택' 문제를 베이스로 둔 배열로 구현한 스택의 코드다. size() 함수는 구현이 가능한지 몰라서 일단 알아오고 다시 수정하겠다..ㅠ 수정해본 결과 내가 원하는 size() 함수는 아니지만 전역 변수로 stacksize를 두고 push함수의 호출에 stacksize가 1 증가하고, pop함수의 호출에 1 감소하는 형태로 구현하긴 했다. 이 방법 말고도 다른 구현 방법을 생각해봤는데, 그것은 노드의 개수를 세는 방법이다. 이 방법으로 코드를 짜기에는 필자가 생각하기에 이미 짜 놓았던 코드의 형식과 어우르지 못해서 아예 새로운 스택의 연결리스트 구현 코드를 짜야한다. 그래서... 다시 도전해보겠다...ㅠㅠ 에잉 모르겠다 포기 연결리스트 스택은 구조체와 기본 배열로 구현한 스택과 달리 ..

10773: 제로(BOJ C/C++)

10773번: 제로(BOJ C/C++) 사용 언어: C 문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. ..