반응형
스택을 구현하는 방법은 배열로 구현하는 방법과 연결리스트로 구현하는 방법이 있다.
배열로 구현하는 방법은 메모리를 미리 할당해야 하기 때문에 불필요한 메모리 낭비가 있을 수 있다.
하지만 연결리스트를 통해 스택을 구현하면 불필요한 메모리 낭비가 없다.
연결리스트는 노드의 데이터 필드로 값을 표현하고 링크 필드로 연결성을 표현한다.
링크필드는 포인터이다.
연결리스트로 구현한 스택도 배열로 구현한 스택과 마찬가지로 LIFO를 만족해야한다.
이러한 연결리스트로 스택을 구현하기 위해서 top을 포인터로 사용해야 한다.
### 연결리스트로 구현한 스택 ###
# 노드 #
데이터필드와 링크필드를 갖는 노드를 통해 연결리스트를 만들 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#pragma once
#include "Student.h"
#include <iostream>
class Node : public Student
{
private:
Node* link;
public:
Node(int i=0, char* nam="", char* dep="") :Student(i, nam, dep) {
link = NULL;
}
void setlink(Node* top)
{
link = top;
}
Node* getlink()
{
return link;
}
};
|
cs |
# 삽입연산, push() #
|
1
2
3
4
5
6
7
8
9
|
void push(Node* p)
{
if (isEmpty()) top = p;
else
{
p->setlink(top); // 노드의 링크필드가 top을 가르키게 함
top = p; // top(포인터)가 p를 가르키게 함
}
}
|
cs |
# 삭제연산, pop() #
|
1
2
3
4
5
6
7
8
9
10
|
Node* pop()
{
if (isEmpty()) return NULL;
else
{
Node* p = top; // top이 가르키고 있던(삭제할) 노드
top=top->getlink(); // 삭제할 노드의 링크(다음노드)를 top이 가르킴
return p; // p 반환
}
}
|
cs |
# 전체 code #
|
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
|
#pragma once
#include "Node.h"
class LinkedStack
{
private:
Node* top;
public:
LinkedStack() { top = NULL; }
~LinkedStack()
{
while (!isEmpty())
{
delete pop();
}
}
bool isEmpty()
{
return top == NULL;
}
void push(Node* p)
{
if (isEmpty()) top = p;
else
{
p->setlink(top); // 노드의 링크필드가 top을 가르키게 함
top = p; // top(포인터)가 p를 가르키게 함
}
}
Node* pop()
{
if (isEmpty()) return NULL;
else
{
Node* p = top; // top이 가르키고 있던(삭제할) 노드
top=top->getlink(); // 삭제할 노드의 링크(다음노드)를 top이 가르킴
return p; // p 반환
}
}
void display()
{
printf("[LinkedStack]\n");
for (Node* p = top; p != NULL; p=p->getlink())
// p=p->getlink() 를 통해 뒤로 진행함
{
p->display();
}
printf("\n");
}
};
|
cs |
반응형