반응형
728x90
반응형

C++은 다른 언어들처럼 가비지 컬렉터가 없다ㅋㅋ 그래서 메모리 관리를 제대로 하지 않으면, 정확히 Heap 영역에 대한 메모리 관리가 제대로 되지 않는다면,

헬이다. 헬.

그러면 어찌해야하는가? RAII 라는 디자인 패턴이 있다.

Resource Acquisition Is Initialization 

위를 줄여서 RAII 라고 부른다.

RAII의 유래

그럼 왜 RAII일까? 유래를 좀 찾아봤는데 자원의 획득은 초기화이고, 반대로 자원의 반환은 객체 소멸 뭐 이런 식으로 확장하여 나타내는 어떤 관용구 같은 느낌의 디자인 패턴 개념이다.

RAII란?

좀 더 자세하게 관련해서 정의를 알아 보자면 RAII 는 객체의 생명주기에 관련된 내용으로, C++에서 객체가 생성되고 사용된 Scope를 벗어나면 객체의 자원을 해제해주는 방법을 이야기한다.

즉, 힙에 동적 할당되는 객체라고 해도, 프로그램 실행 흐름이 해당 객체의 유효 scope를 벗어나면 객체를 메모리 해체하도록 하는 것이 RAII라고 생각하면 될 것 같다.

근데 아쉽게도 힙 영역에 할당된 객체는 지역 scope를 벗어난다고해서 동적할당된 부분이 해체되지 않는다. 왜냐하면 동적할당이 이루어지는 해당 scope 내에는 객체 포인터가 스택에 쌓이고, 해당 scope가 끝나면 그 객체 포인터만 스택에서 소멸된다. 동적할당된 메모리는 힙 영역에 그대로 남아있다.

다음과 같이 말이다.

번호순으로 읽기

위의 사실을 응용하여,

어떤 scope에서 동적 할당이 이루어졌다면, 해당 scope에서 스택 영역에 할당되는 요소에게 동적 할당한 주소를 넘겨주고, 그 스택 영역에 할당된 요소는 스택에서 제거될 때, 넘겨받은 동적 할당된 주소를 함께 delete 하면서 제거되면 되지 않을까? 라는 발상이 떠오른다. 아래와 같이 말이다.

번호순으로 읽기

문제가 되는 부분

자, 일단은 문제가 되는 코드이다. 위의 그림과는 살짝 다르지만 문제 없다.

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
#include <iostream>
 
class R
{
    private:
        int *data;
    public:
        R(int len)
        {
            this->data = new int[len];
            std::printf("R() call! : new int[%d]\n",len);
        }
        ~R()
        {
            delete []this->data;
            std::printf("~R() call! : delete [] \n");
        }
};
 
void function(void)
{
    R * r = new R(1000);
 
    std::printf("function() 함수 종료\n");
    return;
}
 
int main(void)
{
    function();
    return 0;
}
cs

위의 코드에서 function 함수라는 지역 scope 내에서 객체 R을 동적할당하고, function 함수를 그냥 종료하는 모습이다. 동적 할당된 R 은 소멸되지 않고 그대로 남다가 해당 프로세스가 종료될 때, 비로소 운영체제에 의해서 메모리 자원이 회수된다. 이런 회수를 원한게 아닌데 말이다.

그렇다면 실행 결과를 보자.

분명히, 소멸자가 호출되지 않은 모습이다. 이것이 바로 메모리 누수(Leak)

스마트 포인터

이를 해결할 방법으로 스마트 포인터라는 것이 등장한다. 포인터 역할을 하는 객체로 이 스마트 포인터를 스택 객체로 할당하고 동적 할당 주소를 넘겨주면 스마트 포인터 객체가 소멸될 때 동적 할당된 힙까지 알아서 똑똑하게 삭제를 해주기 때문이다.

이러한 스마트 포인터를 직접 구현해보았다. 다른 이미 구현된 스마트 포인터만큼 스마트하지는 못해서 그냥 오토 포인터라고 이름을 지었다ㅋㅋㅋ

뭐 아래의 연산자 오버로딩 포스팅 때, 구현을 이미 해봤지만 그래도 새롭게 참고하면서 구현해보았다.

 

21 연산자 오버로딩

연산자 오버로딩 연산자 오버로딩 C++언어에서는 연산자의 오버로딩을 통해서 기존에 존재하던 연산자의 기본 기능 이외에 다른 기능을 추가할 수 있다. 먼저 15번 라인을 통해서 operator+ 라는 함

typingdog.tistory.com

코드 및 실행결과

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
60
61
62
63
64
65
66
#include <iostream>
 
class R
{
private:
    int* data;
    int len;
public:
    R(int _len)
    {
        this->len = _len;
        this->data = new int[_len];
        for (int i = 0; i < _len; i++)
            this->data[i] = i * 100000;
        std::printf("R() call! : new int[%d]\n", _len);
    }
    ~R()
    {
        delete[]this->data;
        std::printf("~R() call! : delete [] \n");
    }
    void ShowData(voidconst
    {
        for (int i = 0; i < this->len; i++)
            std::printf("%d, "this->data[i]);
        std::cout << std::endl;
        return;
    }
};
 
template <typename T>
class AutoPointer
{
private:
     const T* ptr;
public:
    AutoPointer(T* _ptr) : ptr(_ptr)
    {
    }
    ~AutoPointer()
    {
        delete this->ptr;
    }
    const T& operator* () const
    {
        return *(this->ptr);
    }
    const T* operator-> () const
    {
        return this->ptr;
    }
};
 
void function(void)
{
    AutoPointer<R> r(new R(10));
    r->ShowData();
    std::printf("function() 함수 종료!\n");
    return;
}
 
int main(void)
{
    function();
    return 0;
}
cs
힙 영역의 객체의 소멸까지 책임지는 스마트 포인터 똑똑해^^7

이렇게 힘들게 만들었는데 이미 C++ 11에서는 다음과 같은 문법을 제공한다.

 

unique_ptr<> : #include <memory>

이미 11 문법에서는 겁나 스마트한 포인터 객체로 제공을 해주었던 것이다... 사용 방법은 내가 만든 오토 포인터와 같으니 바로 예제로 들어가보겠다.

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
#include <iostream>
#include <memory>
 
class R
{
    private:
        int *data;
    public:
        R(int len)
        {
            this->data = new int[len];
            std::printf("R() call! : new int[%d]\n",len);
        }
        ~R()
        {
            delete []this->data;
            std::printf("~R() call! : delete [] \n");
        }
};
 
void function(void)
{
    std::unique_ptr<R> r(new R(1000));//R * r = new R(1000);
    std::printf("function() 함수 종료\n");
    return;
}
 
int main(void)
{
    function();
    return 0;
}
cs

불안정한 메모리 관리를 이러한 패턴으로 처리한다는게 정말 잔머리를? 기가막히게 잘 굴린듯한 느낌이다. 그래도 GC(가비지 컬렉터)가 제공되면 참 좋겠지만 이렇게라도 일부라도 관리를 틈틈이 하는게 좋은 것 같다.

다음 번 포스팅에서는 (공부하다가 필요한 부분부분 정리하는 포스팅이기 때문에 시리즈물처럼 바로 다음 번은 아니지만) 이 unique_ptr 외에 공유 가능한, 그리고 인자로의 전달 시 어떤 형태로 코드를 짜야하는 지 등에 대해서 올려볼 것이다.

728x90
반응형
728x90
반응형

리스트 기반 큐는 뭐 간단하다. 그냥 일반 큐인데 연결 리스트로 이루어진 큐이다.

기본 형태는 다음과 같다.

매우 간단하다. 그래서 행복하다 

기본적으로 배열 기반의 큐와 똑같이 동작한다. 그러나 배열 기반 큐와 다른 점은 크기가 정해져 있지 않고 동적이고 가변이기 때문에 뭐, 꽉 찬 것으로 보이지만 비어있네, 마네 뭐 이런 배열 기반 큐의 치명적인 단점을 생각할 필요가 없다.

Front 노드 포인터를 통해서 가장 먼저 들어온 노드를 가리키며, 삭제 연산을 진행할 때마다 Front 노드 포인터를 한 노드씩 옮긴다. 그리고 Rear 노드 포인터를 통해서 가장 마지막에 추가된 노드를 가리키며, 삽입 연산을 진행할 때마다, Rear 노드 포인터를 새로운 노드로 갱신한다. 

삽입 연산

 

삭제 연산

 

꽉참/비어짐 확인 연산

꽉 찼는지는 연결 리스트이므로 확인할 필요가 없으니, 비어져있는 상태만 확인하면 되는데 이 역시 매우 간단하다.

Front  노드  포인터가 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
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
#include <stdio.h>
#include <stdlib.h>
 
#define STACK_LEN 10
 
#define TRUE 1
#define FALSE 0
 
// 공통 노드 정의
struct node
{
    int data;
    struct node* next;
};
 
// 스택으로 메모리 관리.
struct array_stack
{
    struct node* stack_array[STACK_LEN];
    int top_index;
};
typedef array_stack stack;
 
void StackInit(stack* s);
int SIsEmpty(stack* s);
int SIsFull(stack* s); // 증가시키고 대입이기 때문에 현 index에서 증가시키고 대입이 가능한지를 확인해야함.
void SPush(stack* s, struct node* data); // 증가시키고 대입.
struct node* SPop(stack* s);
struct node* SPeek(stack* s);
void ShowStack(stack* s);
 
struct node* CreateNodeAuto(stack* s);
void RemoveAllNodeAuto(stack* s);
 
// 리스트 기반 큐 자료구조(원형일 필요가 없음)
struct list_queue
{
    struct node* front;
    struct node* rear;
    int count;
};
typedef struct list_queue queue;
 
void QueueInit(queue* q);
int QisEmpty(queue* q);
struct node* Dequeue(queue* q);
void Enqueue(queue* q, stack* s, int data);
void ShowQueue(queue* q);
 
// Main
int main(void)
{
    stack s;
    queue q;
 
    QueueInit(&q);
    StackInit(&s);
 
    printf("큐/스택 생성 시작 --- \n");
 
    Enqueue(&q, &s, 1); ShowQueue(&q);
    Enqueue(&q, &s, 2); ShowQueue(&q);
    Enqueue(&q, &s, 3); ShowQueue(&q);
    Enqueue(&q, &s, 4); ShowQueue(&q);
    Enqueue(&q, &s, 5); ShowQueue(&q);
 
    printf("큐 제거 시작 --- \n");
 
    ShowQueue(&q);
    while (!QisEmpty(&q))
    {
        Dequeue(&q);
        ShowQueue(&q);
    }
    fputc('\n', stdout);
 
    printf("스택 제거 시작 --- \n");
    RemoveAllNodeAuto(&s);
    return 0;
}
 
 
// 메모리 관리 스택 관련 함수
 
void StackInit(stack* s)
{
    int i = 0;
    s->top_index = -1;
    for (i = 0; i < STACK_LEN; i++// 순회를 위해서 모두 초기화
        s->stack_array[i] = NULL;
    return;
}
int SIsEmpty(stack* s)
{
    if (s->top_index == -1)
        return TRUE;
    else
        return FALSE;
}
int SIsFull(stack* s) // 증가시키고 대입이기 때문에 현 index에서 증가시키고 대입이 가능한지를 확인해야함.
{
    if ((s->top_index) + 1 < STACK_LEN)
        return FALSE;
    else
        return TRUE;
}
void SPush(stack* s, struct node* data) // 증가시키고 대입임 (top_index가 -1부터 시작하기 때문에)
{
    if (SIsFull(s))
    {
        printf("스택이 가득찼습니다\n");
        return;
    }
    s->stack_array[++(s->top_index)] = data;
    return;
}
struct node* SPop(stack* s)
{
    struct node* rtarget = NULL;
    if (SIsEmpty(s))
    {
        printf("스택이 비어져있습니다\n");
        return NULL;
    }
    rtarget = s->stack_array[s->top_index];
    s->stack_array[s->top_index--= NULL;
    return rtarget;
}
struct node* SPeek(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 비어져있습니다\n");
        return NULL;
    }
    return s->stack_array[s->top_index];
}
 
void ShowStack(stack* s)
{
    int i = 0;
    printf("{(top:%d)} : ", s->top_index);
    for (i = 0; i < STACK_LEN; i++)
        printf("[%p]", s->stack_array[i]), putc('-', stdout);
    putc('\n', stdout);
    return;
}
 
// 내가 정의하는 함수
 
struct node* CreateNodeAuto(stack* s)
{
    struct node* tmp = (struct node*)malloc(sizeof(struct node));
    // 초기화
    tmp->data = 0;
    tmp->next = NULL// tmp->next = s->head;
    // 메모리 스택에 추가
    SPush(s, tmp);
 
    return tmp;
}
 
void RemoveAllNodeAuto(stack* s)
{
    struct node* rtarget = NULL;
    ShowStack(s);
    while (!SIsEmpty(s))
    {
        rtarget = SPop(s);
        free(rtarget);
        ShowStack(s);
    }
    return;
}
 
// 큐 자료구조 관련 함수
 
void QueueInit(queue* q)
{
    q->front = q->rear = NULL;
    q->count = 0;
    return;
}
int QisEmpty(queue* q)
{
    if (q->front == NULL)
        return TRUE;
    else
        return FALSE;
}
struct node* Dequeue(queue* q)
{
    struct node* target;
    // 기본 동작 - 비었는가 확인 -> 삭제 -> 인덱스 변경
    if (QisEmpty(q))
    {
        printf("Queue가 이미 비었습니다.\n");
        return NULL;
    }
    // target 추출
    target = q->front;
 
    // front를 맨 앞 노드의 다음 노드로 변경
    q->front = q->front->next;
 
    // 카운트 감소
    q->count--;
    return target;
}
void Enqueue(queue* q, stack* s, int data)
{
    // 노드 생성
    struct node* new_node = CreateNodeAuto(s); // 추가되는 노드가 항상 마지막이 된다.
    new_node->data = data;
    new_node->next = NULL;
 
    ShowStack(s);
 
    if (QisEmpty(q)) // 노드가 처음 추가하는 노드라면 front와 rear 모두 갱신
    {
        q->front = q->rear = new_node;
    }
    else // 노드가 처음 추가하는 노드가 아니라면 rear만 갱신
    {
        q->rear->next = new_node;
        q->rear = new_node;
    }
 
    // 카운트 증가
    q->count++;
    return;
}
 
void ShowQueue(queue* q)
{
    struct node* index = NULL;
    printf("{(r:%p/f:%p)} : ", q->rear, q->front);
    for (index = q->front; index != NULL; index = index->next)
        printf("[%p(%d)]", index, index->data), putc('-', stdout);
    putc('\n', stdout);
    return;
}
 
 
 
 
 
 
 
cs

 

728x90
반응형
728x90
반응형

자 오늘도 학습했던 원형 양방향 연결 리스트를 정리할 때가 됐다. 이게 정리를 바로바로 안 하다보니 후, 코드를 다시 이해해야한다. 뭐 복습도 되고 참 좋다;;;

먼저 오늘 할 것은

원형 - 무한 순회가 가능한 -> 그래서 순회에 조건이 꼭 붙는,
양방향 - 노드의 양쪽 링크가 존재하는 -> 그래서 원형 순회 실현이 가능한
연결 리스트

를 포스팅 한다.

원형이라고 해서 개인적으로 위와 같은 형태로  생각하면 혼란만 가중할 것이라고 생각한다. 아래와 같이 말이다.

그래서 우리는 머릿속의 형태를 정해놓고 시작해보고자 한다.

이러한 형태 임을 꼭 기억하고 있어야 한다.

노드 삽입 연산

삽입 연산은 노드가 없을 때와 있을 때로 나눈다.

크 따로 부가 설명이 필요 없을 것 같다ㅋ 

노드 삭제 연산

삭제는 간단하다. 그림 하나로 표현 가능하다.

삭제의 기본이 되는 부분

 

그 이외에 순회 연산

순회 연산은 그냥 노드의 링크를 순방향/역방향으로 타는 인덱스 포인터를 만들어서 순회를 하면 된다. 다만, 원형 연결 리스트인 만큼 무한 반복에 빠질 수 있기 때문에 아래와 같은 조건을 넣어 무한 반복에서 탈출하도록 해야한다.

위 코드는 순방향 순회, 역방향 순회 모두 마찬가지로 해당되는 부분이다.

 

메모리 관리 부분

해당 코드에서 또한 메모리 관리 부분이 따로 있기 때문에 삭제 연산 시에도 바로 메모리를 제거 하지 않고 프로그램 종료 전에 한꺼번에 모두 free 시키도록 되어 있다.

클래스로 stack 컨테이너 어댑터로 아래와 같이 구현되어 있다.

코드 및 실행 결과

 

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
#include <iostream>
#include <stack>
#include <stdio.h>
 
using namespace std;
 
// 구조체 존
struct node {
    int data;
    struct node* prev;
    struct node* next;
};
 
struct list {
    struct node* head;
    struct node* ci; // current index
    int count;
};
 
// 클래스 존
class NodeMemoryManager // 이 클래스 자체에 템플릿을 때려버리면 여러 타입에 대해서 관리할 수 있다ㅋ
{
private:
    int count; // 내부적인 교차 검증을 위한 count;
    stack<struct node*> allocated_node_address;
public:
    NodeMemoryManager()
    {
        this->count = 0;
    }
    ~NodeMemoryManager()
    {
        int free_count = 0;
        int stack_count = this->allocated_node_address.size(); // 제거하기 전 숫자.
 
        // 스택은 내부적으로 벡터니까 -> 임의 접근이 되지 않을까? -> 불가능 -> 그럴거면 벡터를 쓰지 왜 스택을 쓰나? 스택의 탄생 이유이다.
        while (!this->allocated_node_address.empty())
        {
            free(this->allocated_node_address.top()); // c에서 malloc 할 것이니, free 함수.
            this->allocated_node_address.pop();
            free_count++;
        }
        cout << "모든 메모리가 해체되었습니다[" << free_count << "/" << this->count << "(" << stack_count << ")]" << endl;
    }
    struct node* CreateNodeAuto(void)
    {
        struct node* tmp = (struct node*)malloc(sizeof(struct node));
        // 초기화
        tmp->data = 0;
        tmp->prev = NULL;
        tmp->next = NULL;
        // 스택 추가
        this->AddAllocatedNodeAddress(tmp);
        return tmp;
    }
    void AddAllocatedNodeAddress(struct node* addr)
    {
        this->allocated_node_address.push(addr);
        this->count++;
        return;
    }
    int GetCount()
    {
        return this->count;
    }
    int GetCountByStack()
    {
        return this->allocated_node_address.size();
    }
};
 
// 재정의 존
typedef struct list List;
 
// 함수 선언 존
void ListInit(List* list);
void LInsert(List* list, int data);
int LFirst(List* list, int* data);
int LNext(List* list, int* data, int non_exit);
int LPrevious(List* list, int* data, int non_exit);
void LRemove(List* list);
 
// 전역 변수 존
NodeMemoryManager nmm;
 
//메인 함수
int main(void)
{
    List list;
    int data;
 
    ListInit(&list);
 
    // 값 1 ~ 값 8 까지 추가.
    LInsert(&list, 1); LInsert(&list, 2); LInsert(&list, 3); LInsert(&list, 4); LInsert(&list, 5); LInsert(&list, 6); LInsert(&list, 7); LInsert(&list, 8);
 
    LFirst(&list, &data);
 
    // 한 칸 씩 이동
    printf("-------- previous zone \n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LPrevious(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
 
    printf("-------- next zone \n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
    (LNext(&list, &data, 1== 1) ? printf("[%d]\n", data) : printf("LFirst가 실행되지 않았습니다.\n");
 
    // 순회 및 삭제 처리
    printf("-------- remove zone \n\n");
    if (LFirst(&list, &data))
    {
        if (data == 2)
            LRemove(&list);
        while (LNext(&list, &data, 0))
        {
            if (data == 2)
                LRemove(&list);
        }
        while (LPrevious(&list, &data, 0))
        {
            if (data == 6)
                LRemove(&list);
        }
    }
 
    // 순회
    printf("-------- circuit zone \n");
    if (LFirst(&list, &data))
    {
        printf(" - [%p|%p(%d)|%p] - \n", list.ci->prev, list.ci, list.ci->data, list.ci->next);
        while (LNext(&list, &data, 0))
            printf(" - [%p|%p(%d)|%p] - \n", list.ci->prev, list.ci, list.ci->data, list.ci->next);
        while (LPrevious(&list, &data, 0))
            printf(" - [%p|%p(%d)|%p] - \n", list.ci->prev, list.ci, list.ci->data, list.ci->next);
    }
 
    printf("최종으로 남은 노드의 개수는? ( %d )\n", list.count);
 
    return 0;
}
 
// 함수 정의 존
void ListInit(List* list)
{
    // 헤더 생성 및 초기화
    list->head = NULL;
    // 카운트 초기화
    list->count = 0;
    // 인덱스 노드를 초기화
    list->ci = NULL;
 
    return;
}
 
void LInsert(List* list, int data)
{
    // 새 노드 생성
    struct node* new_node = nmm.CreateNodeAuto();
 
    // 새 노드 초기화
    new_node->data = data;
 
    if (list->head == NULL// 자료구조 자체가 비어있으면
    {
        new_node->prev = new_node->next = new_node;
    }
    else
    {
        // 새 노드의 양 링크를 연결.
        new_node->next = list->head; // 1. [새 노드] -> 기존 시작 노드 연결
        new_node->prev = list->head->prev; // 2. 기존 끝 노드 <- [새 노드] 연결
 
        // 양쪽 노드의 prev 링크들을 연결.
        new_node->next->prev = new_node; // 새 노드 <- [기존 시작 노드] 연결
        new_node->prev->next = new_node; // 새 노드 <- [기존 끝 노드] 연결
    }
 
    // 헤드와 빈 노드 연결
    list->head = new_node;
 
    // 노드 추가 완료 시, 카운트 증가
    list->count++;
 
    return;
}
 
int LFirst(List* list, int* data)
{
    // 헤드를 검사한다. 널이면 false 반환, 널이 아니면 진행
    if (list->head == NULL)
        return false;
 
    // 인덱스를 옮긴다.
    list->ci = list->head;
 
    // 데이터 참조하여 값을 변경
    *data = list->ci->data;
 
    // true 반환
    return true;
}
 
int LNext(List* list, int* data, int non_exit)
{
    // LFirst 가 실행되지 않은 경우는 false
    if (list->ci == NULL)
        return false;
 
    // 다음 가리키는 것이 헤드가 가리키는 것과 같은지를 확인한다. -> 끝인지를 확인하는 방법 -> 같으면 false 반환
    // 원형이기 때문에 검사가 필요한데, non_exit인자는 원점을 지나쳐 원형으로 계속해서 순회하기 위해서 넣음.
    if ((non_exit == false&& (list->head == list->ci->next))
        return false;
 
    // 인덱스를 옮긴다.
    list->ci = list->ci->next;
 
    // 데이터 참조하여 값을 변경
    *data = list->ci->data;
 
    // true 반환
    return true;
}
 
int LPrevious(List* list, int* data, int non_exit)
{
    // LFirst 가 실행되지 않은 경우는 false
    if (list->ci == NULL)
        return false;
 
    // 해당 노드의 prev가 가리키는 것이 헤드가 가리키는 것과 같인지를 확인한다 -> 끝인지를 확인하는 방법 -> 같으면 false 반환
    if ((non_exit == false&& (list->head == list->ci->prev))
        return false;
 
    // 인덱스를 역행으로 옮긴다.
    list->ci = list->ci->prev;
 
    // 데이터 참조하여 값을 변경
    *data = list->ci->data;
 
    // true 반환
    return true;
}
 
void LRemove(List* list)
{
    // 타겟의 링크들이 끊기기 전에 따로 주소 값을 기록한다.
    struct node* target = list->ci;
 
    // 삭제할 타겟이 head가 가리키고 있는 노드라면
    if (list->head == target)
    {
        // 삭제할 타겟의 양 링크가 본인을 가리킨다면 삭제할 타겟은 하나!
        if (list->head == list->head->next) 
            list->head = NULL;
        else 
            list->head = target->next; // 헤드를 다음 노드로 옮겨준다.
    }
 
    // 타겟의 전 노드의 next 를 타겟의 next로 바꾼다
    target->prev->next = target->next;
 
    // 타겟의 다음 노드의 prev 를 타겟의 prev로 바꾼다
    target->next->prev = target->prev;
 
    // count를 줄인다.
    list->count--;
 
    // 메모리 해체는 NMM 객체가 알아서 해준다.
    return;
}
cs

728x90
반응형
728x90
반응형

스택을 연결리스트로 구현해 보았다.

일단 기본 구조에 대한 예시를 나타낸 것이다.

먼저, 왼쪽 구조를 보자. 우리 스택이라고 생각하는 구조이다. Head는 삽입 인덱스를 나타낸다. 소위 말하는 top 변수. 그 왼쪽의 구조를 단순화시켜서 보면 오른쪽처럼 나타낼 수 있다. 오른쪽 구조에서 Head 노드는 새롭게 노드가 삽입될 때 마다 가리키는 것을 갱신시키는데, 이 현상을 자세히 보면 왼쪽 구조에서 head가 옮겨다니는 것과 같다. 

다른 현상을 가지고 생각하기 나름으로 같은 본질을 끌어냈다 크.. 윤성우 교수님께 박수를...

암튼 왼쪽이든 오른쪽이든 위와 같은 본질의 구조를 구현할 것이다.

삽입 연산

1) 헤드와 기존 최 상단 노드의 연결을 끊고, 2) 새 노드와 최상단 노드를 연결하여 새 노드를 최상단 노드로 변경하고,  그 3) 최상단 노드를 헤드가 가리키도록 헤드 값을 갱신 

삭제 연산

삭제의 기본 동작은 노란색 글씨와 빨간색 글씨로 표현을 해두었다.

파란색 글씨는 대충 이런 말이다. 할당된 메모리는 따로 이전에 만들어 뒀던 자료구조로 따로 저장하여 관리하고 프로그램 종료 시, 일괄로 삭제하기 때문에 관련 포인터만 변경하고(모든 포인터 연결을 삭제 '처리') 삭제 되었다고 생각하고 진행하라는 의미이다. 

비어짐 확인

이런 구조에서 비어짐을 확인하려면 어떻게 하면 될까? 
> Head가 NULL을 가리키면 텅 빈 상태입니다. (O)
이런 구조에서 꽉 참을 확인하려면 어떻게 하면 될까?
> 연결 리스트 기반이라 꽉 찰 것을 걱정하지 않아도 됩니다.(O) 그 걱정대신 작성자 나이 걱정을.... (ㅜ.ㅜ)

뭐 더 쓸 말이 없다.

 

코드 및 실행 결과

프로그램 코드를 제출하기에 앞서 복습도 할 겸,
이전에 배웠던 원형 큐를 활용하여 메모리가 생성될 때마다 원형 큐에 메모리 주소를 넣고, 프로그램이 종료될 때 일괄적으로 free~~~~~~~ 된다. 그니까 생성만 했다하면 원형 큐에 넣어제끼고, 프로그램이 끝나기 직전에 다 소멸시켜버리는 것이다. 그래서 실행 결과가 지저분하여 실행결과도 약간의 설명을 넣을 예정이다.

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
#include <stdio.h>
#include <stdlib.h>
 
#define QUEUE_LEN 11
 
#define TRUE 1
#define FALSE 0
 
struct node
{
    int data;
    struct node* next;
};
 
struct list_stack
{
    struct node* head;
    int count;
};
typedef struct list_stack stack;
 
/////////////////////////// 건들지 않아도 될 큐 부분(포스팅을 위해 모듈로 나누지 않는다) ///////////////////////////
struct array_queue // 배열 기반 원형 큐 구현
{
    int front;
    int rear;
    int count;
    struct node* queue_array[QUEUE_LEN];
};
typedef struct array_queue queue;
 
void QueueInit(queue* q);
int QisEmpty(queue* q);
struct node* Dequeue(queue* q);
void Enqueue(queue* q, struct node* data);
void ShowQueue(queue* q);
/////////////////////////// 건들지 않아도 될 큐 부분(포스팅을 위해 모듈로 나누지 않는다) ///////////////////////////
 
void RemoveAllNodeAuto(queue* q);
struct node* CreateNodeAuto(stack* s, queue* q);
 
// list stack 
void StackInit(stack* s);
int SIsEmpty(stack* s);
 
void SPush(stack* s, queue* q, int data);
int SPop(stack* s, queue* q);
int SPeek(stack* s);
 
int main(void)
{
    stack s;
    queue q;
 
    QueueInit(&q);
    StackInit(&s);
 
    SPush(&s, &q, 1);
    SPush(&s, &q, 2);
    SPush(&s, &q, 3);
    SPush(&s, &q, 4);
    SPush(&s, &q, 5);
 
    while (!SIsEmpty(&s))
        printf("%d ", SPop(&s, &q));
    fputc('\n', stdout);
 
    ShowQueue(&q);
    printf("----------------------------------------------------------\n");
    RemoveAllNodeAuto(&q);
    return 0;
}
 
/////////////////////////// 건들지 않아도 될 큐 부분(포스팅을 위해 모듈로 나누지 않는다) ///////////////////////////
void QueueInit(queue* q)
{
    int i = 0;
 
    q->front = q->rear = 0;
 
    for (i = 0; i < QUEUE_LEN; i++)
        q->queue_array[i] = NULL// 큐 출력을 위한 초기화
 
    q->count = 0;
    return;
}
int QisEmpty(queue* q)
{
    if (q->front == q->rear)
        return TRUE;
    else
        return FALSE;
}
struct node* Dequeue(queue* q)
{
    struct node* target;
    // 기본 동작 - 비었는가 확인 -> 삭제 -> 인덱스 변경
    if (q->front == q->rear)
    {
        printf("Queue가 이미 비었습니다.\n");
        return NULL;
    }
    target = q->queue_array[q->front];
    q->queue_array[q->front= NULL;
    q->front = (q->front + 1) % QUEUE_LEN;
    return target;
}
void Enqueue(queue* q, struct node* data)
{
    // 기본 동작 - 꽉 찼는가 확인 -> 삽입 -> 인덱스 변경
    if ((q->rear + 1) % QUEUE_LEN == q->front// 가득 찬 경우,
    {
        printf("Queue가 가득 찼습니다.\n");
        return;
    }
    q->queue_array[q->rear] = data;
    q->rear = (q->rear + 1) % QUEUE_LEN;
    q->count++;
    return;
}
 
void ShowQueue(queue* q)
{
    int i = 0;
    printf("{(r:%2d/f:%2d)} : ", q->rear, q->front);
    for (i = 0; i < QUEUE_LEN; i++)
        printf("[%2p]", q->queue_array[i]), putc('-', stdout);
    putc('\n', stdout);
    return;
}
/////////////////////////// 건들지 않아도 될 큐 부분(포스팅을 위해 모듈로 나누지 않는다) ///////////////////////////
 
// 내가 정의하는 함수
struct node* CreateNodeAuto(stack* s, queue* q)
{
    struct node* tmp = (struct node*)malloc(sizeof(struct node));
    // 초기화
    tmp->data = 0;
    tmp->next = NULL// tmp->next = s->head;
    // 큐 추가
    Enqueue(q, tmp);
 
    return tmp;
}
 
void RemoveAllNodeAuto(queue* q)
{
    struct node* rtarget = NULL;
    while (!QisEmpty(q))
    {
        rtarget = Dequeue(q);
        printf("[%p/(%d)]가 제거되었습니다.\n", rtarget, q->count);
        ShowQueue(q);
 
        free(rtarget);
        q->count--;
    }
    return;
}
 
// list stack 
void StackInit(stack* s)
{
    s->count = 0;
    s->head = NULL;
    return;
}
int SIsEmpty(stack* s)
{
    if (s->head == NULL)
        return TRUE;
    else
        return FALSE;
}
 
void SPush(stack* s, queue* q, int data)
{
    // 추가해야할 새로운 노드 생성
    struct node* newnode = CreateNodeAuto(s, q);
    // 새로운 노드의 값 세팅 및 기존 노드로 next 연결
    newnode->data = data;
    newnode->next = s->head;
    // head를 새로운 노드와 연결
    s->head = newnode;
    // count 증가
    s->count++;
    return;
}
int SPop(stack* s, queue* q)
{
    struct node* target = s->head;
    // head 가 Null을 가리키고 있다면 스택이 비어있는 것. 조건 검사 진행
    if (SIsEmpty(s))
    {
        printf("스택이 이미 비어있습니다\n");
        return 0;
    }
    // head 를 target의 next, 다음 노드와 연결한다.
    s->head = target->next;
    // count 감소
    s->count--;
 
    return target->data;
}
int SPeek(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 이미 비어있습니다\n");
        return 0;
    }
    return s->head->data;
}
 
cs

혹시 보는 사람이 있다면 스택 부분만 참고하면 될 듯 합니다. 앞으로도 쭉 요래요..ㅋㅋ

 

728x90
반응형
728x90
반응형

스택이란 정말 간단하다.

분명히 내가 이거 그림 그리면서 포스팅을 한거 같은데 아무리 블로그를 뒤져봐도 없다... 그래서 다시 하는 느낌으로 스택 첫 포스팅을 시작한다.

먼저, 

스택이란 무엇인가?

우리는 스택을 이미 알고 있다. 스택은 프링글스이다. 아래의 그림을 보자.

우리는 세 개의 감자칩 중에서 어떤 감자칩이 제일 먼저 들어갔는지 알 수 있다. 바로 A이다. 어떻게 알았지? 출입구가 하나이고, 원통 내부의 크기는 서로가 뭐 어떻게 비집고 해서 바꿀 수 있는 사이즈가 아니다. 

A가 먼저 들어갔고 -> 그 다음 B가 그 위에 쌓이고 -> 그 후 C가 들어가면서 그 위에 쌓이는 것이다.

이렇듯 스택은 쌓이는 특징을 가지고 있다. 그렇다면 안의 감자칩을 꺼내먹을 때에는 어떻게 할까? 

가장 나중에 들어간 C가 제일 먼저 다시 나오고 -> 그 다음 B가 나오고 -> 가장 먼저 들어간 A가 제일 늦게 나온다. 

이렇게 나중에 들어간 값이 제일 먼저 나오는 구조를 후입선출 구조라고 한다.

단순 배열 기반 스택에서의 삽입

어려울 것이 전혀 없다. 그냥 값이 들어오는데로 쌓아올린다고 생각하고 인덱스를 증가시키면서 값을 추가하면 된다.

82를 삽입 전(왼) / 82를 삽입 후(오)

하나도 어렵지 않다. 이렇게 보면 그냥 배열 끝에 값을 추가하는 것 같다. 우리는 스택에 값을 추가하는 행위push 라고 할 것이다. 삭제 연산을 보자. 

단순 배열 기반 스택에서의 삭제

3 값이 튀어나가면서 삭제 처리가 되어 버리고, 삽입 인덱스가 하나 감소한다.

마지막 하나 남은 1이 튀어 나가며 값이 삭제 처리 되고, 삽입 인덱스가 갈 곳을 잃는데 이 때, 삽입 인덱스를 -1로 하자. 그러면 나중에 빈 스택 상태에서 값을 추가할 때, 삽입 인덱스를 증가시키면 [-1] 에서 [0]으로 바뀌어서 자연스럽게 값을 추가하면 될 뿐만 아니라, 스택이 비어있는지 비어있지 않는지 삽입 인덱스가 -1인지 아닌지를 보면 된다.

그리고 우리는 삭제하는 연산을 pop 한다고 할 것이다.

단순 배열 기반 스택에서의 비워짐과 꽉참을 확인

또한 간단하다.
인덱스가 비워져 있는지를 확인하기 위해선 아까 삭제 연산에의 약속대로 삽입 인덱스가 -1인지를 확인하면 된다. 
인덱스가 가득차 있는지를 확인하기 위해선 현재 삽입 인덱스가 배열의 길이랑 같은지를 확인하면 된다.

코드 및 실행 결과

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
#include <stdio.h>
#define STACK_LEN 10
 
#define TRUE 1
#define FALSE 0
 
struct array_stack
{
    int stack_arr[STACK_LEN];
    int top_index;
};
 
typedef array_stack stack;
 
void StackInit(stack* s);
int SIsEmpty(stack* s);
void SPush(stack* s, int data);
int SPop(stack* s);
int SPeek(stack* s);
 
int main(void)
{
    stack s;
    StackInit(&s);
 
    SPush(&s, 1);
    SPush(&s, 2);
    SPush(&s, 88);
    SPush(&s, 125);
    SPush(&s, 9912);
 
    while (!SIsEmpty(&s))
        printf("[%d] ", SPop(&s));
    fputs("\n", stdout);
 
    if (SIsEmpty(&s))
        printf("스택이 텅 비었습니다.\n");
    return 0;
}
 
void StackInit(stack* s)
{
    s->top_index = -1;
    return;
}
int SIsEmpty(stack* s)
{
    if (s->top_index == -1// 같아도 된다고?
        return TRUE;
    else
        return FALSE;
}
void SPush(stack* s, int data)
{
    if (s->top_index == STACK_LEN)
    {
        printf("스택이 꽉 찼습니다.\n");
        return;
    }
 
    s->stack_arr[++(s->top_index)] = data;
    printf("스택에 %d 값이 추가 되었습니다.\n", s->stack_arr[s->top_index]);
    return;
}
int SPop(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 이미 비어져 있습니다.\n");
        return -1// 적절치 않다. -1 또한 값으로 넣을 수 있기 때문에. -> 차라리 프로그램을 종료시키는게 적절.
    }
    return s->stack_arr[s->top_index--];
}
int SPeek(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 텅 비었습니다.\n");
        return -1;
    }
    return s->stack_arr[s->top_index];
}
cs

728x90
반응형
728x90
반응형

오늘도 역시 공부해놨던 부분을 이제 포스팅하는 시간이다. 역시 미리미리 해야한다.

스택이란?

일단 그림이 먼저다.

A, B, C 순서로 사각형을 넣을 것이다.

이렇게 된다. 그렇다면 다시 뺀다면?

이 때, 담는 용기, 통! 이것이 스택 자료구조이다. 
먼저 들어간 사각형 A가 제일 늦게 나오는 구조인 것이다. 이러한 개념을 후입선출이라고 한다. 나중에 들어간 것이 먼저 나오는 구조!

이를 구현하면 아래와 같다.

코드 및 실행 결과

---

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
#include <stdio.h>
#define STACK_LEN 10
 
#define TRUE 1
#define FALSE 0
 
struct array_stack
{
    int stack_arr[STACK_LEN];
    int top_index;
};
 
typedef array_stack stack;
 
void StackInit(stack* s);
int SIsEmpty(stack* s);
void SPush(stack* s, int data);
int SPop(stack* s);
int SPeek(stack* s);
 
int main(void)
{
    stack s;
    StackInit(&s);
 
    SPush(&s, 1);
    SPush(&s, 2);
    SPush(&s, 88);
    SPush(&s, 125);
    SPush(&s, 9912);
 
    while (!SIsEmpty(&s))
        printf("[%d] ", SPop(&s));
    fputs("\n", stdout);
 
    if (SIsEmpty(&s))
        printf("스택이 텅 비었습니다.\n");
    return 0;
}
 
void StackInit(stack* s)
{
    s->top_index = -1;
    return;
}
int SIsEmpty(stack* s)
{
    if (s->top_index == -1// 같아도 된다고?
        return TRUE;
    else
        return FALSE;
}
void SPush(stack* s, int data)
{
    if (s->top_index == STACK_LEN)
    {
        printf("스택이 꽉 찼습니다.\n");
        return;
    }
 
    s->stack_arr[++(s->top_index)] = data;
    printf("스택에 %d 값이 추가 되었습니다.\n", s->stack_arr[s->top_index]);
    return;
}
int SPop(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 이미 비어져 있습니다.\n");
        return -1// 적절치 않다. -1 또한 값으로 넣을 수 있기 때문에. -> 차라리 프로그램을 종료시키는게 적절.
    }
    return s->stack_arr[s->top_index--];
}
int SPeek(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 텅 비었습니다.\n");
        return -1;
    }
    return s->stack_arr[s->top_index];
}
cs

---

중간 중간에 보완해야할 부분이 있지만 개념 부분에서는 충분하기 때문에 보완하지는 않았다.

728x90
반응형

'프로그래밍응용 > C 자료구조' 카테고리의 다른 글

C Data Structure - 큐  (0) 2021.01.08
C Data Structure - 퀵 정렬  (0) 2021.01.06
C Data Structure - 병합 정렬  (0) 2021.01.05
C Data Structure - 힙 정렬  (0) 2021.01.05
C Data Structure - 연결 리스트  (0) 2021.01.04
728x90
반응형

스택이란?

컨테이너를 확장 및 축소하여 기능을 제한하거나 특정 기능과 특징을 사용하도록 만든 것을 컨테이너 어댑터라고 하는데, 스택이 바로 그것이다.

내부적으로 vector, dequeue, list 등의 컨테이너로 동작하며 기본적으로는 dequeue로 동작한다.

내부 컨테이너를 변경하려면 stack<data type, list<int>> listack; 이러한 식으로 진행하면 된다. ( 스택에서 사용될 data type, 변경할 컨테이너 구조: list or vector 등)

코드 및 실행 결과

----

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
#include <stack>
#include <iostream>
#include <string>
 
using namespace std;
 
int main(void)
{
    stack<string> st;
    string words[3= {
        "Apple",
        "Banana",
        "Corn"
    };
 
    for (int i = 0; i < 3; i++)
        st.push(words[i]);
    
    while (!st.empty())
    {
        cout << st.top() << endl;
        st.pop();
    }
    return 0;
}
cs

----

728x90
반응형

'프로그래밍응용 > Modern & STL' 카테고리의 다른 글

Priority Queue  (0) 2021.01.04
Queue  (0) 2021.01.04
Tuple  (0) 2021.01.03
Pair  (0) 2021.01.03
Map  (0) 2020.09.15

+ Recent posts