스택

1) 스택(Stack)은 한쪽으로 들어가서 한쪽으로 나오는 자료 구조(Data Structure) 입니다

   즉, 들어가는 곳과 나오는 곳이 동일합니다

2) 이러한 특성 때문에 수식 계산 등의 알고리즘에서 다방면으로 활용됩니다

 

-PUSH: 스택에 데이터를 넣습니다

-POP: 스택에서 데이터를 빼냅니다

 

스택의 구현

1) 스택(Stack)은 배열을 이용한 구현 방법과 연결 리스트를 이용한 구현 방버븡로 나누어 집니다

2) 가장 기본적인 형태의 자료구조로 구현 난이도는 낮은 편입니다

3) 먼저 배열을 이용한 구현 방법에 대해서 알아보겠습니다

 

 

배열을 이용해 스택을 활용한 예시

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10000
#define INF 99999999
 
int stack[SIZE];
int top = -1; //스택의 최상단
 
void push(int data) {
    if (top == SIZE - 1) { //더 이상 데이터를 못 넣을때
        printf("스택 오버플로우가 발생했습니다\n");
        return;
    }
    stack[++top] = data;
}
 
int pop() {
    if (top == -1) { //더 이상 데이터를 못 뺄때
        printf("스택 언어플로우가 발생했습니다\n");
        return -INF;
    }
    return stack[top--];
}
 
void show() {
    printf("--- 스택의 최상단 ---\n");
    for (int i = top; i >= 0; i--) {
        printf("%d\n", stack[i]);
    }
    printf("--- 스택의 최하단 ---\n");
}
 
 
int main (void){
    push(7);
    push(5);
    push(4);
    pop();
    push(6);
    pop();
    show();
 
    return 0;
}
 cs

 

연결 리스트를 이용해 스택을 활용한 예시

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define INF 99999999
 
typedef struct {
    int data;
    struct Node* next;
}Node;
 
typedef struct {
    Node* top;
} Stack;
 
void push(Stack* stack, int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = stack->top;
    stack->top = node;
}
 
void pop(Stack* stack) {
    if (stack-> top == NULL) {
        printf("스택 언더플로우가 발생했습니다\n");
        return -INF;
    }
    Node* node = stack->top;
    int data = node->data;
    stack->top = node->next;
    free(node);
    return data;
}
 
void show(Stack* stack) {
    Node* cur = stack->top;
    printf("--- 스택의 최상단 ---\n");
    while (cur != NULL) {
        printf("%d\n", cur->data);
        cur = cur->next;
    }
    printf("--- 스택의 최하단 ---\n");
}
 
int main (void){
    Stack s;
    s.top = NULL;
    push(&s, 7);
    push(&s, 5);
    push(&s, 4);
    pop(&s);
    push(&s, 6);
    pop(&s);
    show(&s);
    return 0;
}
 cs

 

이렇게 스택은 배열 , 연결 리스트를 이용해서 구현할 수 있습니다

 

'자료구조와 알고리즘' 카테고리의 다른 글

양방향 연결 리스트  (0) 2021.02.27
연결 리스트  (0) 2021.02.17
자료구조의 개요  (0) 2021.02.16

양방향 연결 리스트는 머리(Head)와 꼬리(Tail)를 모두 가진다는 특징이 있습니다

각 노드는 앞 노드와 뒤 노드의 정보를 모두 저장하고 있습니다

prev   next prev   next prev   next
Head 일반 노드 Tail

 

양방향 연결 리스트 선언

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;
 
Node *head, *tail;
 
 cs

 

양방향 연결 리스트 삽입과정

  1. 삽입할 위치에서 그 앞쪽에 있는 노드가 삽입할 노드를 가리키도록 만듭니다
  2. 삽입할 노드가 앞쪽에 있는 노드를 가리키도록 만듭니다
  3. 뒤쪽에 있는 노드가 삽입할 노드를 가리키도록 만듭니다
  4. 삽입할 노드가 뒤쪽에 있는 노드를 가리키도록 만듭니다

순서를 철저하게 지켜주셔야 오류없이 동작하게 됩니다

 

양방향 연결 리스트 예시

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;
 
Node *head, *tail;
 
void insert(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    Node* cur;
    cur = head->next;
    while (cur->data < data && cur != tail) {
        cur = cur->next;
    }
    Node* prev = cur->prev;
    prev->next = node;
    node->prev = prev;
    cur->prev = node;
    node->next = cur;
}
 
void removeFront() {
    Node* node = head->next;
    head->next = node->next;
    Node* next = node->next;
    next->prev = head;
    free(node);
}
 
void show() {
    Node* cur = head->next;
    while (cur != tail) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
}
 
int main (void){
    head = (Node*)malloc(sizeof(Node));
    tail = (Node*)malloc(sizeof(Node));
    head->next = tail;
    head->prev = head;
    tail->next = tail;
    tail->prev = head;
    insert(2);
    insert(1);
    insert(3);
    insert(9);
    insert(7);
    removeFront();
    show();
    return 0;
}
 cs

양방향 연결 리스트 구현에 있어서 주의할 점

위 소스코드에 덧붙여서 삽입 및 삭제 기능에서의 예외 사항을 처리할 필요가 있습니다

더 이상 삭제할 원소가 없는데 삭제하는 경우 등을 체크해야 합니다

 

 

'자료구조와 알고리즘' 카테고리의 다른 글

스택  (0) 2021.02.27
연결 리스트  (0) 2021.02.17
자료구조의 개요  (0) 2021.02.16

연결리스트

일반적으로 연결 리스트는 구조체와 포인터를 함께 사용하여 구현합니다

리스트의 중간 지점에 노드를 추가하거나 삭제할 수 있어야 합니다

포인터 기반의 연결리스트는 필요할 때마다 메모리 공간을 할당 받습니다

 

연결 리스트의 필요성

일반적으로 배열을 사용하여 데이터를 순차적으로 저장하고,나열할 수 있습니다

배열을 사용하는 경우 메모리 공간이 불필요하게 낭비 될 수 있습니다

 

배열 기반의 리스트 예시

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#define INF 10000
 
int arr[INF];
int count = 0;
 
void addBack(int data) {
    arr[count] = data;
    count++;
}
 
void addFirst(int data) {
    for (int i = count; i >= 1; i--) {
        arr[i] = arr[i - 1];
    }
    arr[0] = data;
    count++;
}
 
void removeAt(int index) {
    for (int i = index; i < count - 1; i++) {
        arr[i] = arr[i + 1];
    }
    count--;
}
 
void show() {
    for (int i = 0; i < count; i++) {
        printf("%d ", arr[i]);
    }
}
 
int main(void) {
    addBack(5);
    addBack(8);
    addBack(7);
    addFirst(3);
    addFirst(4);
    show();
}
 cs

 

배열 기반 리스트의 특징

 

배열로 만들었으므로 특정한 위치의 원소에 즉시 접근할 수 있다는 장점이 있습니다

데이터가 들어갈 공간을 미리 메모리에 할당해야 한다는 단점이 있습니다

원하는 위치로의 삽입이나 삭제가 비효율적입니다

 

 

단일 연결 리스트

 

하나의 구조체 안에 두 개의 변수가 들어가게 만듭니다

변수 하나는 데이터를 담고 다른 하나는 다음 구조체를 가리키는 변수입니다

  next data next NULL
Head 일반 노드  

단일 연결 리스트는 위와 같은 형태로 나타낼 수 있습니다

포인터를 이용해 단방향적으로 다음 노드를 가리킵니다

일반적으로 연결리스트의 시작 노드를 헤드(Head)라고 하며 별도로 관리합니다

끝 노드의 다음 위치 값으로는 NULL을 넣습니다

 

연결 리스트 예시

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
    int data;
    struct Node* next;
} Node;
 
Node* head;
 
int main(void) {
    head = (Node*)malloc(sizeof(Node));
    Node* node1 = (Node*)malloc(sizeof(Node));
    node1->data = 1;
    Node *node2 = (Node*)malloc(sizeof(Node));
    node2->data = 2;
    head->next = node1;
    node1->next = node2;
    node2->next = NULL;
    Node* cur = head->next;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    return 0;
}
 cs

 

연결 리스트 삽입 함수

1
2
3
4
5
6
void addFront(Node* root, int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = root->next;
    root->next = node;
}
 cs

 

연결 리스트 삭제 함수

1
2
3
4
5
void removeFront(Node* root) {
    Node* front = root->next;
    root->next = front->next;
    free(front);
}
 cs

 

연결 리스트 메모리 해제 함수

1
2
3
4
5
6
7
8
void freeAll(Node* root) {
    Node* cur = head->next;
    while (cur != NULL) {
        Node* next = cur->next;
        free(cur);
        cur = next;
    }
}
 cs

 

연결 리스트 전체 출력 함수

1
2
3
4
5
6
7
void showAll(Node* root) {
    Node* cur = head->next;
    while (cur != NULL) {
        pritnf("%d ", cur->data);
        cur = cur->next;
    }
}
 cs

 

 

완성된 연결 리스트 사용하는 예시

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(void) {
    head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    addFront(head, 2);
    addFront(head, 1);
    addFront(head, 7);
    addFront(head, 9);
    addFront(head, 8);
    removeFront(head);
    showAll(head);
    freeAll(head);
    return 0;
}
 cs

 

연결 리스트 구현에 있어서 주의할 점

위 소스 코드들에 덧붙여서 삽입 및 삭제 기능에서의 예외 사항을 처리할 필요가 있습니다

(삭제할 원소가 없는데 삭제하는 경우, Head 노드 자체를 잘못 넣은 경우 등을 체크해야합니다)

 

연결 리스트의 특징

삽입과 삭제가 배열 기반 리스트의 비해서 간단합니다

배열 기반 리스트와 다르게 특정 인덱스로 즉시 접근하지 못하며, 원소를 차례대로 검색해야 합니다

추가적인 포인터 변수가 사용되므로 메모리 공간이 낭비됩니다

 

삽입과 삭제가 많은 경우에서 효율적이지만

특정한 인덱스에 바로 참조해야 할 때가 많다면 배열을 이용하는 것이 효율적입니다

 

 

'자료구조와 알고리즘' 카테고리의 다른 글

스택  (0) 2021.02.27
양방향 연결 리스트  (0) 2021.02.27
자료구조의 개요  (0) 2021.02.16

자료구조의 필요성

데이터를 효과적으로 저장하고, 처리하는 방법에 대해서 바르게 이해하기 위해

불필요하게 메모리와 성능을 낭비하지 않기 위해

 

자료구조와 알고리즘

효율적인 자료구조 설계를 하기위해 알고리즘 지식이 필요합니다

또 효율적인 알고리즘을 작성하기 위해서는 문제 상황에 맞는 적절한 자료구조가 사용되어야 합니다

따라서 자료구조론과 알고리즘 이론은 모두 동일선상에 놓을 수 있습니다

 

기본적인 자료구조들

선형구조

(자료를 구성하는 원소들을 순차적으로 나열시킨 형태)

  • 배열
  • 연결 리스트
  • 스택
  • 큐

비선형 구조

  • 트리(Tree)
  • 그래프(Graph)

 

프로그램의 성능 측정 방법론

  • 시간 복잡도(Time Complexity) 알고리즘에 사용되는 연산 횟수를 의미합니다
  • 공간 복잡도(Space Complexity) 알고리즘에 사용되는 메모리의 양을 의미합니다

효율적인 알고리즘을 사용한다고 가정했을 때 일반적으로 시간과 공간은 반비례 관계입니다.

 

시간 복잡도를 표현할 때는 최악의 경우를 나타내는 Big-O 표기법을 사용합니다

이 때 항상 큰 항과 계수만 표시합니다

O(3n^2 + n) = O(n^2)

현실적의 다양한 문제에서는 시간 제한이 1초 정도라고 생각하시면 됩니다

 

공간 복잡도를 표기할 때는 일반적으로 MB 단위로 표기합니다

int a[1000] = 4KB

int a[1000000] = 4MB

int a[2000][2000] = 16MB

 

 

 

'자료구조와 알고리즘' 카테고리의 다른 글

스택  (0) 2021.02.27
양방향 연결 리스트  (0) 2021.02.27
연결 리스트  (0) 2021.02.17

+ Recent posts

티스토리툴바