(CS) 단일 연결 리스트 vs 원형 연결 리스트, Stack으로 Queue 구현, 원형 큐 구현

단일 연결 리스트 vs 원형 연결 리스트

단일 연결 리스트와 원형 연결 리스트는 연결 리스트의 일종으로, 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다. 데이터를 노드에 저장하고 노드들을 링크로 연결하여 데이터를 관리하는 자료구조이다.

하지만 다음과 같은 차이점이 있다.

단일 연결 리스트(Singly Linked List)	원형 연결 리스트(Circular Linked List)
리스트의 끝은 NULL로 표시 리스트의 순회는 단방향으로만 가능	리스트의 끝은 NULL이 아닌, 첫 번째 노드를 가리키는 포인터로 표시 마지막 노드의 다음 노드는 첫 번째 노드가 되어 원형적인 형태 리스트의 순회는 양방향으로 가능
다음 노드만을 가리키는 포인터만으로 구현되기 때문에 구현이 간단하고 메모리를 적게 사용	구현이 복잡하고 메모리 사용량이 많지만 순환적인 형태를 가지므로 자유롭게 데이터 추가 및 삭제 가능

따라서 단일 연결 리스트는 데이터를 순차적으로 추가하고 삭제하는 경우에 적합하고, 원형 연결 리스트는 리스트의 처음과 끝을 구분하지 않아야 할 때 적합하다.

Stack으로 Queue 구현

class Queue {
    private:
        stack<int> s1, s2; // s1은 저장하는 스택, s2는 pop을 위한 스택
    
    public:
        void push(int x){
            s1.push(x);
        }

        int pop(){
            if(s2.empty()){
                while(!s1.empty()){
                    int tmp = s1.top();
                    s1.pop();
                    s2.push(tmp);
                }
            }
            int front = s2.top();
            s2.pop();
            return front;
        }

        int size(){
            return s1.size() + s2.size();
        }

        bool empty(){
            return s1.empty() && s2.empty();
        }
};

원형 큐 구현

#include <iostream>

using namespace std;

const int MAX_SIZE = 5; // 원형 큐의 최대 크기

class CircularQueue {
private:
    int front, rear; // 큐의 첫번째 위치와 마지막 위치
    int arr[MAX_SIZE]; // 원형 큐로 쓸 array

public:
    CircularQueue() { // 생성자
        front = -1;
        rear = -1;
    }

    bool isEmpty() { // 둘 다 -1이면 원형 큐는 빈 상태
        return front == -1 && rear == -1;
    }

    bool isFull() { // rear의 바로 다음이 front인지 확인
        return (rear + 1) % MAX_SIZE == front;
    }

    void enQueue(int x) { // 원형 큐에 값 삽입
        if(isFull()) {
            cout << "원형 큐가 꽉 찼습니다..." << "\n";
            return;
        }
        if(isEmpty()) { // 원형 큐가 비었을 경우
            front = 0;
            rear = 0;
        }else {
            rear = (rear + 1) % MAX_SIZE; // 원형 큐에 값이 삽입되었으므로 rear index 1 증가
        }
        arr[rear] = x;
    }

    void deQueue() { // 원형 큐의 front의 값 반환
        if(isEmpty()) {
            cout << "원형 큐가 비었습니다..." << "\n";
            return;
        }
        if(front == rear) { // 원형 큐에 값이 하나만 들어있을 때
            front = -1;
            rear = -1;
        }else {
            front = (front + 1) % MAX_SIZE; // 큐에서 값이 하나 빠졌으므로 front index 1 증가
        }
    }

    int peek() { // Front에 위치한 값 반환
        if(isEmpty()) {
            cout << "원형 큐가 비었습니다..." << "\n";
            return -1;
        }
        return arr[front];
    }

    void display() { // 원형 큐 전체 출력
        if(isEmpty()) {
            cout << "원형 큐가 비었습니다..." << "\n";
            return;
        }
        int i = front;
        while (i != rear) { // 원형 큐의 끝까지
            cout << arr[i] << " ";
            i = (i + 1) % MAX_SIZE; // 원형 큐의 다음 index
        }
        cout << arr[rear] << "\n"; // 원형 큐의 마지막 값 출력
    }
};

출처

ChatGPT(https://chat.openai.com/)