본문으로 바로가기

[AL] 3. 자료구조 (Linked List, Stack, Queue)

category CS/Algorithm 2019. 3. 28. 05:54
3_자료구조 (Linked List, Stack, Queue)

3. 자료구조 (Linked List, Stack, Queue)

  1. Linked List
  2. Stack
  3. Queue

 

1. Linked List

각 노드가 데이터 와 포인터 를 가지고 한 줄로 연결되어 있는 자료구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

 

1.1. 특징

각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. 따라서, 이 부분만 다른 값으로 바꿔주면 삽입과 삭제를 O(1) 만에 해결할 수 있는 것이다.

하지만 Linked List 는 한 가지 문제를 가지고 있다. 원하는 위치에 삽입을 하고자 하면 위치를 Search 하는 과정에서 첫번째 원소부터 전부 확인해야 한다는 점이다. Array 와는 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문이다. 이러한 이유 때문에 어떠한 원소를 삽입 또는 삭제 시, 그 원소를 찾기 위해서 O(n) 의 시간이 추가적으로 발생하게 된다.

결국, Linked List 는 search, add, remove 에서 O(n) 의 시간복잡도를 가지게 된다.

 

1.2. 소스코드 (C++)

#include <iostream>
using namespace std;

// Node
class Node {
public:
    int data;
    Node *preNode;
    Node *nxtNode;
    
    Node() {
        data = 0;
        preNode = NULL;
        nxtNode = NULL;
    }
    
    Node(int _data){
        data = _data;
        preNode = NULL;
        nxtNode = NULL;
    }
};

// List
class List {
private:
    Node *head;
    int size;
    
public:
    List();
    void Valid(int ind);
    int Size();
    
    void add(int data);
    void add(int data,int ind);
    
    void remove(int ind);
    
    void set(int data,int ind);
    int get(int ind);
    
    void print();
    bool isEmpty();
};

List::List(){
    head = new Node;
    size = 0;
}

void List::Valid(int ind){
    if(ind > size)
        throw "ERROR 잘못된 인덱스입니다.\n";
}

int List::Size(){
    return size;
}

void List::add(int data){
    Node *newNode = new Node(data);
    
    if(head->nxtNode == NULL){
        head->nxtNode = newNode;
        newNode->preNode = head;
    }else{
        Node *tmp = head;
        
        while(tmp->nxtNode != NULL){
            tmp = tmp->nxtNode;
        }
        
        tmp->nxtNode = newNode;
        newNode->preNode = tmp;
    }
    
    size++;
}

/*
 ! 마지막 인덱스에 접근 불가함
*/
void List::add(int data,int ind){
    try {
        Valid(ind);
    } catch (const char* msg) {
        cout << msg << "\n";
        return;
    }
    
    Node *newNode = new Node(data);
    Node *tmp1 = head;
    Node *tmp2;
    
    if(head->nxtNode == NULL){
        head->nxtNode = newNode;
        newNode->preNode = head;
    }else{
        for(int i=1; i<ind; i++){
            tmp1 = tmp1->nxtNode;
        }
        tmp2 = tmp1->nxtNode;
        
        tmp1->nxtNode = newNode;
        newNode->preNode = tmp1;
        
        newNode->nxtNode = tmp2;
        tmp2->preNode = newNode;
    }
    
    size++;
}

void List::remove(int ind){
    try {
        Valid(ind);
    } catch (const char* msg) {
        cout << msg << "\n";
        return;
    }
    
    Node *tmp1 = head;
    Node *deleteNode;
    
    for(int i=1; i<ind; i++){
        tmp1 = tmp1->nxtNode;
    }
    deleteNode = tmp1->nxtNode;
    
    // 삭제 노드가 마지막 노드라면
    if(deleteNode->nxtNode == NULL){
        tmp1->nxtNode = NULL;
    }else{
        Node *tmp2 = deleteNode->nxtNode;
        
        tmp1->nxtNode = tmp2;
        tmp2->preNode = tmp1;
    }
    
    deleteNode->preNode = NULL;
    deleteNode->nxtNode = NULL;
    delete deleteNode;
    
    size--;
}

void List::set(int data,int ind){
    try {
        Valid(ind);
    } catch (const char* msg) {
        cout << msg << "\n";
        return;
    }
    
    Node *tmp = head;
    
    for(int i=1; i<=ind; i++){
        tmp = tmp->nxtNode;
    }
    
    tmp->data = data;
}

int List::get(int ind){
    try {
        Valid(ind);
    } catch (const char* msg) {
        cout << msg << "\n";
        return 0;
    }
    
    Node *tmp = head;
    
    for(int i=1; i<=ind; i++){
        tmp = tmp->nxtNode;
    }
    
    return tmp->data;
}

void List::print(){
    Node *tmp = head->nxtNode;
    
    while(1){
        cout << tmp->data << " ";
        
        if(tmp->nxtNode == NULL) break;
        
        tmp = tmp->nxtNode;
    }
    cout << "\n";
}

bool List::isEmpty(){
    if(head->nxtNode == NULL) return true;
    else return false;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    List list;
    
    list.add(2);
    list.add(4);
    list.add(6);
    list.add(8);
    list.add(10);
    list.print();
    list.remove(3);
    list.print();
    list.set(7, 2);
    list.print();
    list.remove(1);
    list.remove(3);
    list.add(6, 1);
    list.print();
    return 0;
}

 

 

2. Stack

선형 자료구조의 일종으로 LIFO(Last In First Out) 형식의 자료구조이다. 차곡 차곡 쌓이는 구조로 먼저 Stack 에 들어간 원소는 맨 바닥에 깔리게 된다. 그렇기 때문에 늦게 들어간 원소는 그 위에 쌓이게 되고, 호출 시 가장 Top 에 있는 원소가 호출되는 구조이다.

 

2.1. 소스코드 (C++)

#include <iostream>
using namespace std;

// Node
class Node {
public:
    int data;
    Node *preNode;
    
    Node() {
        data = 0;
        preNode = NULL;
    }
    
    Node(int _data){
        data = _data;
        preNode = NULL;
    }
};

// Stack
class Stack {
private:
    Node *top;
    int size;
    
public:
    Stack();
    int Size();
    int Top();
    
    void push(int data);
    void pop();
    
    void print();
    bool isEmpty();
};

Stack::Stack(){
    top = NULL;
    size = 0;
}

int Stack::Size(){
    return size;
}

int Stack::Top(){
    return top->data;
}

void Stack::push(int data){
    Node *newNode = new Node(data);
    
    if(size == 0){
        top = newNode;
    }else{
        Node *tmp = top;
        top = newNode;
        newNode->preNode = tmp;
    }
    
    size++;
}

void Stack::pop(){
    if(isEmpty()){
        cout << "스택이 비어있습니다.\n";
        return;
    }
    
    Node *tmp = top;
    top = tmp->preNode;
    delete tmp;
    
    size--;
}

void Stack::print(){
    if(isEmpty()){
        cout << "스택이 비어있습니다.\n";
        return;
    }
    
    Node *tmp = top;
    
    while(1){
        cout << tmp->data << "\n";
        
        if(tmp->preNode == NULL) break;
        
        tmp = tmp->preNode;
    }
    cout << "\n";
}

bool Stack::isEmpty(){
    if(top == NULL) return true;
    else return false;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    Stack s;
    s.push(3);
    s.push(4);
    s.push(5);
    s.pop();
    s.printStack();
    s.push(6);
    s.push(7);
    s.push(8);
    s.printStack();
    cout << ">> Top Value is " << s.Top() << "\n";
    s.pop();
    s.printStack();
    
    return 0;
}

 

 

3. Queue

선형 자료구조의 일종으로 FIFO(Fist In First Out) 형식의 자료구조이다. Stack 과는 반대로 먼저 들어간 원소가 맨앞에서 대기하다가, 먼저 나오게 된다. rear 에 데이터를 삽입하는 enQueue 연산과 front 의 데이터를 삭제하는 deQueue 연산을 수행한다. 이에 대한 활용으로는 Priority Queue 가 존재한다.

 

3.1. 소스코드 (C++)

#include <iostream>
using namespace std;

// Node
class Node {
public:
    int data;
    Node *preNode;
    Node *nxtNode;
    
    Node() {
        data = 0;
        preNode = NULL;
        nxtNode = NULL;
    }
    
    Node(int _data){
        data = _data;
        preNode = NULL;
        nxtNode = NULL;
    }
};

// Queue
class Queue {
private:
    Node *front;
    Node *rear;
    int size;
    
public:
    Queue();
    int Size();
    int Front();
    
    void enQueue(int data);
    void deQueue();
    
    void print();
    bool isEmpty();
};

Queue::Queue(){
    size = 0;
    front = NULL;
    rear = NULL;
}

int Queue::Size(){
    return size;
}

int Queue::Front(){
    return front->data;
}

void Queue::enQueue(int data){
    Node *newNode = new Node(data);
    
    if(size == 0){
        front = newNode;
        rear = newNode;
    }else{
        newNode->preNode = rear;
        rear->nxtNode = newNode;
        rear = newNode;
    }
    
    size++;
}

void Queue::deQueue(){
    Node *tmp = front;
    front = tmp->nxtNode;
    delete tmp;
    
    size--;
}

void Queue::print(){
    Node *tmp = front;
    
    if(isEmpty()){
        cout << "큐가 비어있습니다.\n";
        return;
    }
    
    while(1){
        cout << tmp->data << " ";
        
        if(tmp->nxtNode == NULL) break;
        
        tmp = tmp->nxtNode;
    }
    cout << "\n";
}

bool Queue::isEmpty(){
    if(front == NULL) return true;
    else return false;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    Queue q;
    q.push(3);
    q.push(4);
    q.push(5);
    q.pop();
    q.printQueue();
    q.push(6);
    q.push(7);
    q.push(8);
    q.printQueue();
    cout << ">> Front Value is " << q.Front() << "\n";
    q.pop();
    q.printQueue();
    
    return 0;
}
저작자표시

'CS > Algorithm' 카테고리의 다른 글

[AL] 6. Union-Find 알고리즘  (0) 2019.04.05
[AL] 5. 자료구조 (Heap, Hash)  (0) 2019.04.01
[AL] 4. 자료구조 (Graph)  (0) 2019.04.01
[AL] 2. 자료구조 (Tree)  (0) 2019.03.11
[AL] 1. 정렬 알고리즘  (0) 2019.03.05
댓글 , 엮인글
SuperM
블로그 이미지 슈퍼마리호 님의 블로그
MENU
CATEGORY
VISITOR 오늘 / 전체

티스토리툴바