2. 큐, 스택

1. 큐

삽입, 삭제 : O(1)

FIFO(First In First Out)의 형태인 자료구조로  첫 노드와 마지막 노드를 가리키는 front, rear 변수가 존재한다.

class queue{
private:
    Node *front;
    Node *rear;
public:
    queue(){front=rear=0;}

    void insert(int x){ //맨 마지막에 삽입 됨
        if(!front)
            front=rear=new Node(x);
        else
            rear=rear->link=new Node(x,0); 
    }

    void remove(){ //제일 처음에 들어온 노드가 삭제
        if(!front){
            return;
        }
        if(!front->next){ 
            //1개만 남은 경우 rear가 남은 것을 참조하는 것을 방지
        	front = rear = null;
        	return;
        }
        Node *temp = front;
        front=front->link;
        delete temp;
    }
};

 

2. 스택 

삽입, 삭제 : O(1)

LIFO(Last In First Out) 형태의 자료구조. 제일 최근에 삽입된 노드를 가리키는 top이 존재함.

class stack{
private:
    Node *top;
public:
    stack(){top=0;}

    void push(int x){ //맨 마지막에 삽입 됨
        top=new Node(x,top);
    }

    void pop(){ //제일 최근에 삽입된 노드가 삭제
        if(!top){
            return;
        }
        Node *temp = top;
        top=top->link;
        delete temp;
    }
};