[C,C++] List를 이용한 Stack, Queue 응용 Sorting

지인의 부탁으로
과제를 도와주었다.
요구사항 : List를 이용하여 Stack과 Queue를 이용하여 하나의 프로그램을 설계
요구사항이 너무나 뜬구름식이라 Stack과 Queue를 어떻게 이용할지 고민을 많이 하였다.
더욱이 찜질방에서 노트북으로 코딩을 했는데,
걍 간단한 리스트라서 기본 소스 없이 백지에서 시작하여 제작하였다.
새벽 2시경에 시작하여 5시반쯤 코딩을 마쳤었다. 귀찮아서 대부분 인라인으로 구현하였고,
따로 헤더파일을 사용하지 않았다.
기본 설계는 Stack 2개와 Queue 1개를 이용하여 배열의 값을 오름차순으로 정리하는 것이다.

소스내용 :
초기 값을 입력받아 배열에 무작위로 수를 저장한다.
그후 입력받은 값을 Stack에 Push한다.
단 넣기전에 Stack에 있는 값을 Pop한후 비교하여 자신보다 작은 값이면 Stack 2 에 저장하고 크면, 자신의 값을 넣는다.
자신보다 큰 값이 나오거나 스택이 비어있을 경우까지 계속반복한다.
입력받은 값이 Stack1에 Push되면 Stack2에 있는 모든 값을 Stack1에 집어넣는다.
이런식으로 차례로 배열의 값을 Stack1에 넣으면 내림차순에 의하여 Stack1에 값이 저장된다.
이 내림차순으로 정렬된 Stack을 오름차순으로 바꿔주기위해 Stack1의 모든 값을 Queue1에 Push한후,
Queue에서 Pop한후 결과 배열에 집어넣은후 출력한다.
그러면 정렬된 값이 저장된다.

개발환경 : Window XP       개발 툴 : Visual Studio 2005     사용언어 : C++
#include<iostream> using namespace std; class Node{ public: int num; Node *next; Node(int i){ num=i; next=NULL; }; }; class List{ public: Node *head; Node *current; Node *beforeCurrent; int count; List(){ head=current=beforeCurrent=NULL; count=0; } ~List(){ while(!isEmpty()){ queuePop(); } }; void push(int n){ Node *temp=new Node(n); current=head; if(isEmpty()){ head=temp; }else{ while(current->next!=NULL){ //MoveTo End current=current->next; } current->next=temp; //insert Last } count++; }; int stackPop(){ beforeCurrent=current=head; if(isEmpty()){ cout<<"List is Empty"<<endl; } else if(current->next==NULL){ head=NULL; int tempNum=current->num; delete current; count--; return tempNum; }else{ while(current->next!=NULL){ //MoveTo End beforeCurrent=current; current=current->next; } int tempNum=current->num; beforeCurrent->next=NULL; delete current; count--; return tempNum; } return 0; }; int queuePop(){ current=head; if(isEmpty()){ cout<<"List is Empty"<<endl; }else{ head=head->next; int tempNum=current->num; delete current; count--; return tempNum; } return 0; }; void printList(){ current=head; if(isEmpty()){ cout<<"List is Empty"<<endl; }else{ while(current->next!=NULL){ cout<<current->num<<" "; current=current->next; } cout<<current->num<<endl; } }; int checkCount(){ cout<<"count : "<<count<<endl; return count; } bool isEmpty(){ if(head==NULL){ return true; }else{ return false; } }; }; void main(){ List *stack1=new List(); List *stack2=new List(); List *queue1=new List(); int size; cout << "enter the list size: "; cin >> size; int *ary=new int[size]; int *aryResult=new int[size]; int i; for(i=0; i<size; i++){ cout << "enter the value: "; cin >> ary[i]; } //입력받기. cout<<"[Input Data]"<<endl; for(i=0;i<size;i++) { cout<<ary[i]<<" "; } cout<<endl; for(i=0;i<size;i++){ //stack1과 stack2를 이용하여 정렬, 결과값은 stack1에 쌓이고 stack2는 임시 스택으로 우선순위 작은 것들을 쌓아 놓는 곳임. int temp=ary[i]; if(stack1->isEmpty()){ stack1->push(temp); }else{ while(1){ int tempPop=stack1->stackPop(); if(tempPop<temp){ if(stack1->isEmpty()){ stack1->push(temp); stack2->push(tempPop); break; } stack2->push(tempPop); }else{ stack1->push(tempPop); stack1->push(temp); break; } } while(!(stack2->isEmpty())){ stack1->push(stack2->stackPop()); } } } //배열에 오름차순 정렬을 위해 큐를 이용 while(!(stack1->isEmpty())){ queue1->push(stack1->stackPop()); } while(!(stack1->isEmpty())){ queue1->push(stack1->stackPop()); } for(i=0;i<size;i++){ //정렬된 data들을 queue를 이용하여 dequeue하여 데이터 산출 int temp=queue1->queuePop(); aryResult[i]=temp; } cout<<"[Sorted Data]"<<endl; for(i=0;i<size;i++){ cout<<aryResult[i]<<" "; } cout<<endl; delete ary; delete aryResult; delete stack1; delete stack2; delete queue1; }

결과 값은 위와 같다.
총 size를 입력받고 배열에 저장후 정렬전 출력, 정렬후의 데이터를 출력한다.

소스 자체가 보기 좋게 해놓아서 코드가 쓸데없이 늘어난 듯 싶다.
기본적인 리스트를 사용하였고, 하나의 리스트 클래스에 큐와 스택기능을 다 넣고,
객체를 3개 생성하여 사용하였다.

그냥 아이디어가 흥미로웠다.^^;

※ 작성시 에로사항 : 처음작성했던 List의 기능중 Queue의 Pop기능에서 BeforeCurrent의 잘못된 사용으로, 에러가 발생하였다. 당연히 잘 돌아가고 알고리즘에 문제가 있었나 하고 고민했으나, 알고보니 List 내부 함수의 잘못이었던 것. 결국 찾아내었지만, 쓸데없이 시간이 낭비되었다 ㅠ.ㅜ;