반응형
1. 1
선입 선출이다.
2. 2
3. 40,50
4. (c) front == rear
5. 2
6.
| [0] | [1] | [2] | [3] | [4] |
| C | A | D |
7. 1
8.
int get_Count(&QueueType q) {
if (q->front <= q->rear)
return q->rear - q->front;
else
return MAX_QUEUE_SIZE - (q->front - q->rear);
}9.
#include<stdio.h>
#define MAX_SIZE 100
typedef struct Stacktype {
int stack[MAX_SIZE];
int top;
};
void Stack_init(Stacktype* s) {
s->top = -1;
}
void Stack_push(Stacktype* s, int item) {
s->stack[++(s->top)] = item;
return;
}
bool is_empty(Stacktype* s) {
return s->top == -1;
}
int Stack_pop(Stacktype* s) {
int t = s->stack[s->top];
s->stack[s->top] = 0;
s->top--;
return t;
}
typedef struct Queuetype {
Stacktype s1, s2;
};
void Queue_init(Queuetype* q) {
q->s1.top = -1;
q->s2.top = -1;
}
void Queue_push(Queuetype* q, int item) {
Stack_push(&(q->s1), item);
return;
}
int Queue_pop(Queuetype* q) {
if (is_empty(&(q->s2))) {
while (!is_empty(&(q->s1))) {
Stack_push(&(q->s2), Stack_pop(&(q->s1)));
}
}
return Stack_pop(&(q->s2));;
}
int main(void) {
Queuetype q;
Queue_init(&q);
Queue_push(&q, 5);
Queue_push(&q, 4);
Queue_push(&q, 3);
printf("%d\n", Queue_pop(&q));
printf("%d\n", Queue_pop(&q));
printf("%d\n", Queue_pop(&q));
}10.
#include<stdio.h>
#include<stdlib.h>
#define QUEUE_MAX_SIZE 10
typedef int element;
typedef struct Queuetype {
element Queue[QUEUE_MAX_SIZE];
int front, rear;
};
void init(Queuetype* q) {
q->front = q->rear = 0;
return;
}
bool is_full(Queuetype* q) {
return ((q->rear + 1) % QUEUE_MAX_SIZE == q->front);
}
bool is_empty(Queuetype* q) {
return q->front == q->rear;
}
void push(Queuetype* q, element item) {
if (!is_full(q)) {
q->rear = (q->rear + 1) % QUEUE_MAX_SIZE;
q->Queue[q->rear] = item;
}
else {
fprintf(stderr, "메모리가 가득찼습니다.\n");
exit(1);
}
return;
}
element pop(Queuetype* q) {
if (is_empty(q)) {
fprintf(stderr, "메모리가 비어있습니다.\n");
exit(1);
}
else {
q->front = (q->front + 1) % QUEUE_MAX_SIZE;
return q->Queue[q->front];
}
}
int fibonachi(Queuetype* q, int n) {
if (n == 0)
return 0;
else if (n == 1)
return 1;
for (int i = 2; i <= n; i++) {
int d = pop(q);
push(q, d + q->Queue[q->rear]);
}
return q->Queue[q->rear];
}
int main(void) {
Queuetype q;
init(&q);
push(&q, 0);
push(&q, 1);
int n = 40;
printf("%d", fibonachi(&q, n));
}11.
#include<stdio.h>
#include<stdlib.h>
#define DEQUEUE_MAX_SIZE 100
typedef char element;
typedef struct Dequeuetype {
element Dequeue[DEQUEUE_MAX_SIZE];
int front, rear;
};
void init(Dequeuetype* q) {
q->front = q->rear = 0;
return;
}
bool is_full(Dequeuetype* q) {
return ((q->rear + 1) % DEQUEUE_MAX_SIZE == q->front);
}
bool is_empty(Dequeuetype* q) {
return q->front == q->rear;
}
void push_back(Dequeuetype* q, element item) {
if (!is_full(q)) {
q->rear = (q->rear + 1) % DEQUEUE_MAX_SIZE;
q->Dequeue[q->rear] = item;
}
else {
fprintf(stderr, "메모리가 가득찼습니다.\n");
exit(1);
}
return;
}
void push_front(Dequeuetype* q, element item) {
if (is_full(q)) {
fprintf(stderr, "메모리가 가득찼습니다.\n");
exit(1);
}
else {
q->Dequeue[q->front] = item;
q->front = (q->front - 1) % DEQUEUE_MAX_SIZE;
}
}
element pop_front(Dequeuetype* q) {
if (is_empty(q)) {
fprintf(stderr, "메모리가 비어있습니다.\n");
exit(1);
}
else {
q->front = (q->front) + 1 % DEQUEUE_MAX_SIZE;
return q->Dequeue[q->front];
}
}
element pop_back(Dequeuetype* q) {
if (is_empty(q)) {
fprintf(stderr, "메모리가 비어있습니다.\n");
exit(1);
}
else {
element temp = q->Dequeue[q->rear];
q->rear = (q->rear - 1) % DEQUEUE_MAX_SIZE;
return temp;
}
}
void check_pelindrome(char I[]) {
Dequeuetype q;
init(&q);
int i = 0, j = 0;
while (I[i] != NULL) {
if ('a' <= I[i] && I[i] <= 'z'){
push_back(&q, I[i]);
j++;
}
else if ('A' <= I[i] && I[i] <= 'Z'){
push_back(&q, I[i] - ('A' - 'a'));
j++;
}
i++;
}
while (!(j == 0 || j == 1)) {
if (pop_front(&q) != pop_back(&q)) {
printf("Pelindrome이 아닙니다.\n");
return;
}
j -= 2;
}
printf("Pelindrome이 맞습니다.\n");
return;
}
int main(void) {
char I[20] = "mad@.,Am";
char T[20] = "rac.er";
check_pelindrome(I);
check_pelindrome(T);
}관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 6장 핵심정리를 가져오도록 하겠습니다.
반응형