[자료구조] #9 Linked Stack & Queue

• 포인터

 

프로그래밍에서 메모리의 특정 위치를 가리키는 변수이다. 

 

포인터는 Linked representation으로 사용된다. 

Linked representation은 데이터를 연결된 노드의 집합으로 나타내는 방법이다.

각 노드는 데이터를 저장하는 부분과 다음 노드를 가리키는 포인터로 구성된다.

 

변수는 dot 연산자( . ), 포인터는 화살표 연산자( - > )를 통해 접근한다.

 

• Self-referential Class(자기 참조 클래스)

 

동일한 클래스 유형의 다른 객체를 가리키는 포인터를 멤버 변수로 포함하는 클래스이다.

 

link라는 포인터에다가 Node라는 주소값을 넣어주면 그 Node를 가리킨다 라고 생각하면 쉽다.

 

• Pros & Cons (vs 배열)

 

장점

• 중간에 아이템 삽입이 용이하다.
  배열은 공간을 한칸씩 다 당겨주어야 하는 불편함이 있다.
• 이론적으로 크기 제한이 없다. 
  배열은 고정된 크기를 가지고 있다.

단점

• 포인터에 따른 공간 추가 할당이 필요하다.
  배열은 데이터만 저장한다.
• 동적 할당에 따른 cost를 무시할 수 없다.

 

• Linked List 구조

 

Head pointer는  첫 노드를 가리킨다.

Nullptr은 리스트의 끝을 나타낸다.

 

• Linked Stack

 

Push Operation

Case 1) 스택이 비어있는 경우 

탑 포인터가 새로운 노드를 가리키게 만들어준다.

(새로운 요소를 스택에 추가하는 것과 같다.)

 

Case 2) 스택이 비어있지 않은 경우

Step 1. 새로운 노드를 동적 할당한다. (P가 임시로 가리키게 한다.)

Step 2. 탑이 새로운 노드를 가리키게 한다.

 

Pop Operation

Case 1) 스택이 비어있는 경우

꺼낼게 없으므로 exception을 던진다.

 

Case 2) 스택이 비어있지 않은 경우

Step 1. 임시 포인터 p를 탑이 가리키는 노드를 가리키도록 만든다.

Step 2. 탑이 다음 노드를 가리키도록 만든다 (top = p -> link)

Step 3. 가리키는 노드의 데이터를 반환한 후 그 노드를 삭제한다.

 

 

코드를 통해 한번 살펴보자.

class LinkedStack{
private:
    Node* top; // 스택의 맨 위를 가리키는 포인터
public:
    // 생성자: top 포인터를 nullptr로 초기화
    LinkedStack(){
        this->top = nullptr;
    }
    
    // 스택이 비어있는지 확인하는 함수
    bool empty(){
        return this->top == nullptr;
    }
    
    // 스택에 데이터를 추가하는 함수
    void push(const Student& data){
        if(this->empty())
            this->top = new Node(data); // 스택이 비어있으면 새 노드를 추가하고 top을 설정
        else{
            Node* p = new Node(data); // 새 노드 생성
            p->set_link(this->top); // 새 노드를 기존의 맨 위 노드와 연결
            this->top = p; // top을 새 노드로 설정
        }
    }
    
    // 스택에서 데이터를 제거하고 반환하는 함수
    Student pop(){
        if(this->empty()){
            throw "error: stack is empty"; // 스택이 비어있으면 에러 발생
        }else{
            Node* p = this->top; // 현재 맨 위 노드를 가리키는 포인터 저장 (step 1)
            this->top = this->top->get_link(); // top을 다음 노드로 이동 (step 2)
            Student data = p->get_data(); // 데이터를 저장 (step 3)
            delete p; // 노드 삭제 (step 3)
            return data; // 데이터 반환
        }
    }
    
    // 소멸자: 스택에 있는 모든 노드를 삭제
    ~LinkedStack(){
        while(!this->empty()){
            this->pop(); // pop 함수를 호출하여 스택을 비움
        }
    }
    
    // 스택에 있는 데이터를 출력하는 함수
    void display(){
        for(Node* p = top; p != nullptr; p = p->get_link())
            p->get_data().display(); // 각 노드의 데이터를 출력
    }
};

 

• Linked Queue

 

Enqueue Operation

Case 1) 큐가 비어있는 경우

front/rear 포인터들이 새로운 노드를 가리키도록 만든다.

 

Case 2) 큐가 비어있지 않은 경우

Step 1. 마지막 노드를 가리키는 rear 포인터가 새로운 노드 p를 가리키도록 만든다.(rear -> link = p)

Step 2. rear를 새로운 노드 p를 가리키도록 만든다. (rear = p)

 

Dequeue Operation

Case 1) 큐가 비어있는 경우

exception을 던진다.

 

Case 2) 큐에 오직 한개의 노드가 존재하는 경우

Step 1. front 포인터가 가리키는 노드의 데이터를 반환하고 그 노드를 삭제한다.

Step 2. front와 rear를 nullptr로 설정한다.

 

Case 3) 큐에 두개 이상의 노드가 존재하는 경우

Step 1. front 포인터가 가리키는 노드를 임시 포인터 p가 가리키도록 만든다.
Step 2. front 포인터를 다음 노드를 가리키도록 설정한다.
Step 3. p가 가리키는 노드의 데이터를 반환한 후 그 노드를 삭제한다. 

 

코드를 통해 살펴보자.

class LinkedQueue {
private:
    Node* front; // 큐의 맨 앞을 가리키는 포인터
    Node* rear; // 큐의 맨 뒤를 가리키는 포인터
public:
    // 생성자: front와 rear를 nullptr로 초기화
    LinkedQueue() {
        this->front = this->rear = nullptr;
    }
    
    // 큐가 비어있는지 확인하는 함수
    bool empty() {
        return this->front == nullptr;
    }
    
    // 소멸자: 큐에 있는 모든 노드를 삭제
    ~LinkedQueue() {
        while (!this->empty())
            this->dequeue(); // dequeue 함수를 호출하여 큐를 비움
    }
    
    // 큐에 있는 데이터를 출력하는 함수
    void display() {
        for (Node* p = front; p != nullptr; p = p->get_link())
            p->get_data().display(); // 각 노드의 데이터를 출력
    }
    
    // 큐에 데이터를 추가하는 함수(enqueue)
    void enqueue(const Student& data) {
        if (this->empty()) {
            this->front = this->rear = new Node(data); // 큐가 비어있으면 새 노드를 추가하고 front와 rear를 설정
        } else {
            Node* p = new Node(data); // 새 노드 생성
            this->rear->set_link(p); // rear와 새 노드를 연결
            this->rear = p; // rear를 새 노드로 설정
        }
    }
    
    // 큐에서 데이터를 제거하고 반환하는 함수(dequeue)
    Student dequeue() {
        if (this->empty()) { // 큐가 비어있으면 에러 발생
            throw "error: queue is empty!";
        } else { // 큐가 비어있지 않은 경우
            Node* p = this->front; // 현재 맨 앞 노드를 가리키는 포인터 저장
            this->front = this->front->get_link(); // front를 다음 노드로 이동
            Student data = p->get_data(); // 데이터를 저장
            delete p; // 노드 삭제
            if (this->front == nullptr) // 큐가 비어있으면 rear도 nullptr로 설정
                this->rear = nullptr;
            return data; // 데이터 반환
        }
    }
};