Programing/C- programing

큐 : 링크드 리스트로 구현한 간단한 큐

sosal 2010. 8. 19. 11:45
반응형

/*
 http://sosal.tistory.com/
 * made by so_Sal
 */

연결리스트로 간단하게 `큐`를 구현해보려고 합니다.
밑에 스택에서 사실 소스를 그대로 재탕해먹었습니다.
push부분과 pop 부분이 상반된다는 점 빼고는
간단한 큐와 스택이 다른점은 없으니..^^;



#include
<iostream>
using namespace std;

class node{
private:
    char value;         //간단하게 알파벳 저장하는 스택의 노드~
public:
    node(int a){          // 생성자 함수를 이용하여 value 초기화
        value = a;
    }
    char getValue(){      // 값을 얻어오기 위한 함수
        return value;
    }
    node *next;          // 다음 노드를 가리킬 포인터
    node *prev;          // 이전 노드를 가리킬 포인터
};

node *first;
node *last;
int count=0;

void push(char val);
void pop();
void print();
int menu();

int main(){
    int num;
    char val;
    while(1){
        num = menu();
        switch(num){
        case 1:
            cout<<"문자열을 입력해주시오 : ";
            cin>>val;
            push(val);
            break;
        case 2:
            pop();
            break;
        case 3:
            print();
            break;
        case 4:
            return 0;
            break;
        default:
            break;
        }
       
    }
    return 0;
}

void push(char val){
    node *newNode = new node(val);   //노드 생성
    newNode->next=NULL;
    newNode->prev=NULL;
   
    if(count==0){                // 첫번째 노드라면
        first=newNode;         // 첫째와 끝 모두를 같은 노드로!
        last=newNode;
    }
    else{
        last->next=newNode;     // 두번째 이상의 노드라면
        newNode->prev=last;
        last=last->next;        // 제일 마지막 노드의 바로 다음 노드로 push
    }
    count++;      
}

void pop(){
    node* del;          // 연결 끊은 후에도 계속 가리킬 포인터
    del=first;
    first=first->next;  // 연결 끊기!
    delete del;         // 삭제 크리!
    count--;
}

void print(){
    node* cur=last;
    cout<<"\t\t┌─┐"<<endl;
    for(int i=0;i<count;i++){
        cout<<"\t\t│"<<cur->getValue()<<" │"<<endl;
        if(cur->prev != NULL)
            cur=cur->prev;
        else
            break;
    }
    cout<<"\t\t└─┘"<<endl;
}

int menu(){
    int val;
    cout<<"[1]:Push, [2]Pop, [3]print, [4]exit :: ";
    cin>>val;
    return val;
}

네.. 아주 쉽게 완성되었네요 +_+
큐입니당. ㅎㅎ