C언어 LinkedList로 Queue구현하기 과제
by luis lee
이 포스팅은 개인적인 용무로 인해 타학교 과제를 하다가 그냥 올리는 포스팅입니다. 과제 내용은 다음과 같으며 구현은 최대한 빨리 끝내야했기 때문에 코드를 깔끔하게 구성하지는 않았습니다.
문제
Create a special queue using linked-list. If the linked-list is not used, 0 point will be given. There are three operations of the special queue. ‘I’ (In) operation to enqueue a value to a queue, ‘O’ (Out) operation to dequeue a value in a queue, and ‘P’ (Priority) operation to dequeue a priority value in a queue. Given an ‘I’ or ‘P’ operation, an integer is given together. In the ‘I’ operation, the value is enqueued to the queue. In the ‘P’ operation, the value is immediately dequeued regardless of the order. If there is no value in the queue, no action is taken. If there is more than one value in the queue, dequeue the value at the front of the queue. Given the operations of a queue in an empty queue state, print the values that are dequeued and the queued values in order after completing all the operations. Global variables should not be declared or used in this problem.
Sample
|input |
|——|
10
I 7
I 3
I 4
I 2
O
I 9
I 2
I 6
P 2
O
| output | | —— |
7
2
3
4 9 2 6
코드의 구현
구현은 1시간 10분정도 걸렸다. input/output format 이 정해져있고 c언어에 익숙하지는 않아서 scanf 부분에서 약간 시간이 걸렷다. 완전히 최적화되어있는 코드는 아니지만 그냥 포스팅 해본다.
#include <stdlib.h>
#include <stdio.h>
typedef struct Queue
{
struct Queue *next; //pointing next Queue node
int data;
} Queue;
//insert node after target
Queue* I_operator(Queue * target,int value);
//delete node (parent of target)
bool D_operator(Queue * target);
Queue * findParent(Queue * target,Queue * head) //double linked list 가 아니므로 이전 노드를 찾는 함수를 구현
{
Queue * resultQ;
if(head->next == NULL)
return NULL;
for(resultQ = head; resultQ ; resultQ = resultQ->next)
{
if(resultQ->next == target)
{
return resultQ;
}
}
return resultQ;
}
Queue * findValue(int value , Queue * head) //특정 값을 가지는 node를 찾는다.
{
Queue * resultQ;
if(head->next == NULL)
return NULL;
for(resultQ = head->next; resultQ ; resultQ = resultQ->next)
{
if(resultQ->data == value)
{
return resultQ;
}
}
return resultQ;
}
Queue * findLast(Queue * head) //마지막 노드를 찾는 함수
{
Queue * resultQ = head;
if(head->next == NULL)
return resultQ;
for(resultQ = head->next; resultQ->next ; resultQ = resultQ->next)
{
}
return resultQ;
}
void doOperation(char OpType,int value,Queue * head)
{
if(OpType == 'O')
{
D_operator(head);
}
else if(OpType == 'I')
{
Queue * last = findLast(head);
I_operator(last,value);
}
else if(OpType == 'P')
{
Queue * findedQueue = findValue(value,head) ;
Queue * target = findParent(findedQueue,head);
D_operator( target);
}
else
{
printf("wrong input");
//wrong input
}
}
//input operator
//target 의 뒤에 value 를 가지는 노드를 넣는다.
Queue* I_operator(Queue * target,int value)
{
Queue * newQueue = (Queue*)malloc(sizeof(Queue));
newQueue->data = value;
newQueue->next = target->next;
target->next = newQueue;
return newQueue;
}
//target 의 앞에있는(parent) 노드를 제거한다.
bool D_operator(Queue * target)
{
if(target == NULL)
return false;
Queue * del = target->next;
if(del == NULL)
{
return false;
}
printf("%d\n",del->data);
target->next = del->next;
free(del);
return true;
}
int main(int argc, char const *argv[])
{
/* code */
Queue * head = (Queue*)malloc(sizeof(Queue));
head->next = NULL; //initialize head node ( head node is dummy node in my code )
int inputSize;
scanf("%d", &inputSize);
for(int i = 0; i < inputSize; i++)
{
//key input
char OpType; //operation type ( I , O , P )
int value;
scanf(" %c",&OpType);
if(OpType != 'O') //if Input's operator type is not 'O' , scan value
{
scanf("%d",&value);
}
doOperation(OpType,value , head);
}
for(Queue * curQ = head->next; curQ; curQ = curQ->next)
{
printf("%d ",curQ->data);
}
return 0;
}
Subscribe via RSS