이번 포스팅에서는 저번 포스팅에 이어서 Stack에 대한 소스코드 및 시간복잡도에 알아보고자 한다. 이를 배열과 연결리스트일 때로 나누어서 설명하겠다.
(1) 배열
- 시간복잡도
: Stack이 배열로 구현된 경우 탐색이 없고, top의 위치에만 삽입과 삭제를 하기 때문에 top의 위치만 알고 있으면 되는데, top을 변수로 놓고 위치를 체크할 수 있으므로 top으로 바로 접근이 가능하다. 따라서, 삽입과 삭제의 시간복잡도만 따져주면 되므로 배열로 구현된 Stack의 시간복잡도는 O(1)이다.
- 삽입
: 삽입은 쉽다. top을 +1 시켜주면서 그 자리에 데이터를 삽입하면 된다.
- 삭제
: 원래 구현하려고 했던 것은 연결리스트처럼 실제로 데이터를 삭제하는 방향으로 하려고 했는데 C언어로 하려다보니 생각보다 배열의 요소를 제거하는 것이 여간 귀찮은 게 아니었다. 그래서, 데이터를 직접 지우는 방식이 아니라 top의 위치를 -1 해주면서 처음부터 top의 위치까지만 출력해 Stack을 보여주게 했다.
그럼 이런 의문이 들 수 있다. Stack이 꽉 찬 다음 데이터를 하나 제거하고 새로운 데이터가 들어오는 경우는 어떻게 처리할 것인가? 필자는 덮어쓰기 방식을 이용했다.
- 소스코드
#include <stdio.h>
#include <stdlib.h>
int top;
void print_stack(int stack[]) { // Stack에 있는 데이터를 출력해주는 함수
for (int i=top; i>=0; i--){ // 배열의 마지막->처음 순으로 출력 => 데이터가 push될 때마다 위로 쌓이도록 출력
printf("%d\n", stack[i]);
}
printf("\n");
}
int main()
{
int stack_data;
int stack_size;
int num;
printf("생성할 스택의 크기를 입력하세요. : ");
scanf("%d", &stack_size);
int stack[stack_size]; // Stack 초기화 및 생성
top = -1; // 배열은 처음 데이터가 저장될 때 index=0에 저장되므로 top은 -1로 초기화
while(1){
printf("해당 번호를 선택해주세요(1 -> 데이터 추가, 2 -> 데이터 삭제) : ");
scanf("%d", &num);
if(num == 1){ // 1번, 즉, 데이터를 push하는 경우
printf("스택에 넣을 데이터를 입력하세요 : ");
scanf("%d", &stack_data);
if (top == stack_size-1) { // 배열은 0부터 시작하므로 배열의 마지막 index는 (배열의 크기 - 1)
printf("Stack이 가득 찼습니다.\n");
}
else{
stack[++top] = stack_data;
}
print_stack(stack);
}
else if(num == 2){ // 2번, 즉, 데이터를 pop하는 경우 => 여기서 구현한 pop기능은 데이터를 삭제하는 것이 아닌 top의 위치만 -1칸 이동시켜 처음부터 top까지 출력
if (top == -1) {
printf("Stack이 비어 있습니다.\n");
}
else{
--top;
}
print_stack(stack);
}
else{ // 1번과 2번을 고르지 않고 다른 숫자를 입력한 경우
printf("1번과 2번만 선택 가능합니다.\n");
}
}
return 0;
}
위는 Stack을 배열로 구현한 소스코드이다. 실행을 해보면
11 => 22 => 33 => 44 순으로 push해서 화면에는 44 => 33 => 22 => 11으로 보인다. 또한 삭제를 하면 44 => 33 => 22 순으로 삭제된다.
(2) 연결리스트
- 시간복잡도
: Stack이 연결리스트로 구현된 경우 연결리스트는 특정 위치로 갈 때 탐색을 하면서 가야하지만 Stack의 경우는 탐색이 따로 필요가 없다. 왜냐하면, top의 위치에만 삽입과 삭제를 하기 때문이다. 따라서, top의 위치를 기점으로 삽입/삭제만 하면 되므로 이 역시 시간복잡도는 O(1)이다.
- 삽입
: top의 위치에서만 삽입을 하므로 탐색을 따로 할 필요가 없어 시간복잡도가 O(1)이다.
- 삭제
: top의 위치에서만 삭제를 하므로 탐색을 따로 할 필요가 없어 시간복잡도가 O(1)이다.
- 소스코드
#include <stdio.h>
#include <stdlib.h>
struct NODE { // 연결 리스트의 노드 구조체
struct NODE *next; // 다음 노드의 주소를 저장할 포인터
int data; // 데이터를 저장할 공간
};
void Node_Insert(struct NODE *top, int list_data) // 노드를 삽입하는 함수 => 매개변수로 삽입할 노드의 이전 노드, 삽입할 데이터를 받음
{
struct NODE *newNode = malloc(sizeof(struct NODE)); // 새 노드 생성
newNode->next = top->next; // 새 노드의 next값에 이전 노드의 next값을 저장 => 쉽게 말해, 노드1->노드2를 노드3(삽입)->노드2로 연결
newNode->data = list_data; // 데이터 저장
top->next = newNode; // 이전 노드의 next값에 삽입 노드의 주소값 저장 => 쉽게 말해, 노드1->노드3(삽입)로 연결
}
void Node_Delete(struct NODE *top) // 노드를 삭제하는 함수 => 매개변수로 삭제할 노드의 이전 노드를 받음
{
struct NODE *removeNode = top->next; // 이전 노드의 next값, 즉, 다음 노드 주소를 저장(이전 노드는 head가 될 수도 있음)
if (removeNode == NULL){ // 삭제할 노드가 없는 경우 => main함수에서 맨 처음에 head를 생성하고 head의 next값을 NULL로 초기화하므로 아무 노드도 없으면 head->next=NULL로 됨
printf("삭제할 노드가 없습니다.\n");
return;
}
else{
top->next = removeNode->next; // 이전 노드의 next값에 삭제할 노드의 next값, 즉, 삭제할 노드의 다음 노드 주소값을 저장 => 쉽게 말해, 노드1->노드2(삭제)->노드3를 노드1->노드3로 연결
free(removeNode); // 노드 메모리 해제
}
}
void Stack_Print(struct NODE *stack_node)
{
while (stack_node != NULL){ // 각 노드를 보여주는 부분, 포인터가 NULL일 때까지 계속 반복 => 즉, 리스트의 끝부분으로 갈 때까지 계속 print함으로써 리스트의 요소들을 보여줌 -> 만약, 아무 노드도 없다면 while문이 돌지 않아 아무것도 출력 X
printf("%d\n", stack_node->data); // 현재 노드의 데이터 출력
stack_node = stack_node->next; // 포인터에 다음 노드의 주소 저장
}
}
int main()
{
int list_data;
int num;
int list_num;
struct NODE *head = malloc(sizeof(struct NODE)); // head 노드 생성
head->next = NULL; // head 노드의 next는 NULL로 초기화
while(1){
printf("해당 번호를 선택해주세요(1 -> 데이터 추가, 2 -> 데이터 삭제) : ");
scanf("%d", &num);
if(num == 1){ // 1번, 즉, node를 삽입하는 경우 (Queue에 데이터를 삽입하는 경우)
printf("스택에 넣을 데이터를 입력하세요 : ");
scanf("%d", &list_data);
struct NODE *top = head;
Node_Insert(top, list_data); // 리스트의 마지막 부분에 새 노드 삽입 => Stack는 마지막 부분에 데이터를 삽입 => 현재 노드 뒤에 삽입할 것이므로 인자값으로 현재 노드를 넣음
Stack_Print(top->next); // 각 노드들을 보여주기 위한 첫 번째 부분 => head->next부터 첫 노드가 시작되므로 head->next가 첫 부분
printf("\n");
}
else if(num == 2){ // 2번, 즉, node를 삭제하는 경우 (큐에 데이터를 삭제하는 경우)
struct NODE *top = head;
Node_Delete(top); // 리스트의 마지막 노드 삭제 -> Stack는 맨 마지막의 데이터를 삭제 => 단, 이전 노드를 마지막 노드로 바꿔주기 위해 인자값으로 이전 노드를 넣음
Stack_Print(top->next); // 각 노드들을 보여주기 위한 첫 번째 부분 => head->next부터 첫 노드가 시작되므로 head->next가 첫 부분
printf("\n");
}
else{ // 1번과 2번을 고르지 않고 다른 숫자를 입력한 경우
printf("1번과 2번만 선택 가능합니다.\n");
}
}
return 0;
}
위는 Stack을 연결리스트로 구현한 소스코드이다. 실행을 해보면
아까 배열과는 다르게 Stack의 크기를 지정하는 부분이 없다. 연결리스트이기 때문에 Stack의 크기에 제한이 없기 때문이다. 그래서 Overflow가 발생할 일도 없다.
보면, 11 => 22 => 33 => 44 순으로 push해서 화면에는 44 => 33 => 22 => 11으로 보인다. 삭제는 top 부분이 맨 앞이므로 출력화면에서는 맨 윗부분부터 삭제되는 것을 확인할 수 있다.
P.S : 비효율적으로 짠 Stack (연결리스트이긴 하지만 삽입/삭제의 시간복잡도가 O(n)인 코드)
=> 이 코드는 필자가 맨 처음에 짰던 코드이다. 구현은 됐지만 잘 보면 엄청 비효율적으로 짰다. 필자가 만든 Node_Insert나 Node_Delete는 위의 연결리스트로 구현한 코드와 똑같은데 잘 만들어놓고 막상 Stack을 쌓을 때
(연결리스트를 만들 때) 비효율적으로 짠 것이다.
그 이유는 아까 위에서 설명했던 것처럼 연결리스트로 구현 시 포인터(top)를 하나 놓고 top에만 삽입/삭제를 하면 되는데, top은 맨 앞에 놓고 정작 데이터의 삽입/삭제는 뒤에서 하게끔 구현했기 때문이다.
이렇게 하면 데이터를 삽입/삭제할 때마다 연결리스트를 처음부터 끝까지 탐색해야한다. 물론 데이터의 양이 적으면 문제가 안되겠지만 데이터의 양이 엄청 많으면 비효율적일 수 밖에 없다. 그림으로 간단하게 나타내보면
(1) 삽입
: 그림을 보면 삽입을 할 시 연결리스트의 마지막부분에 삽입을 하는데 그림처럼 삽입을 하려면 연결리스트의 맨 뒤까지 탐색한 다음 삽입을 해야한다. 따라서, O(n)의 시간복잡도가 소요된다. 또한 이따가 나오겠지만 단일 연결리스트이기 때문에 위에서 쌓이는 것처럼 보이게끔 마지막 값부터 출력할 수가 없다.
마지막값부터 출력을 하려면 그 이전값으로 이동해야하는데 이전 노드의 주소를 가지고 있지 않기 때문이다. 이를 가능케한 것이 양방향 연결리스트이다. 양방향 연결리스트는 추후에 포스팅할 예정이다.
그래서, 출력은 Data1 => Data2 => Data3 => ... => Data n으로 나와 배열과 연결리스트와 다르게 데이터가 아래로 쌓이는 것처럼 보인다. 물론 방향만 반대일 뿐 마지막으로 들어온 데이터가 제일 먼저 삭제되는 것은 똑같다.
(2) 삭제
: 삭제도 삽입과 동일하다. 삭제를 할 시 연결리스트의 마지막부분을 삭제하는데 그림처럼 삭제를 하려면 연결리스트의 맨 뒤까지 탐색한 다음 삭제를 해야한다. 따라서, O(n)의 시간복잡도가 소요된다.
- 소스코드
#include <stdio.h>
#include <stdlib.h>
struct NODE { // 연결 리스트의 노드 구조체
struct NODE *next; // 다음 노드의 주소를 저장할 포인터
int data; // 데이터를 저장할 공간
};
void Node_Insert(struct NODE *prev_node, int list_data) // 노드를 삽입하는 함수 => 매개변수로 삽입할 노드의 이전 노드, 삽입할 데이터를 받음
{
struct NODE *newNode = malloc(sizeof(struct NODE)); // 새 노드 생성
newNode->next = prev_node->next; // 새 노드의 next값에 이전 노드의 next값을 저장 => 쉽게 말해, 노드1->노드2를 노드3(삽입)->노드2로 연결
newNode->data = list_data; // 데이터 저장
prev_node->next = newNode; // 이전 노드의 next값에 삽입 노드의 주소값 저장 => 쉽게 말해, 노드1->노드3(삽입)로 연결
}
void Node_Delete(struct NODE *prev_node) // 노드를 삭제하는 함수 => 매개변수로 삭제할 노드의 이전 노드를 받음
{
struct NODE *removeNode = prev_node->next; // 이전 노드의 next값, 즉, 다음 노드 주소를 저장(이전 노드는 head가 될 수도 있음)
if (removeNode == NULL){ // 삭제할 노드가 없는 경우 => main함수에서 맨 처음에 head를 생성하고 head의 next값을 NULL로 초기화하므로 아무 노드도 없으면 head->next=NULL로 됨
printf("삭제할 노드가 없습니다.\n");
return;
}
else{
prev_node->next = removeNode->next; // 이전 노드의 next값에 삭제할 노드의 next값, 즉, 삭제할 노드의 다음 노드 주소값을 저장 => 쉽게 말해, 노드1->노드2(삭제)->노드3를 노드1->노드3로 연결
free(removeNode); // 노드 메모리 해제
}
}
void Stack_Print(struct NODE *stack_node)
{
while (stack_node != NULL){ // 각 노드를 보여주는 부분, 포인터가 NULL일 때까지 계속 반복 => 즉, 리스트의 끝부분으로 갈 때까지 계속 print함으로써 리스트의 요소들을 보여줌 -> 만약, 아무 노드도 없다면 while문이 돌지 않아 아무것도 출력 X
printf("%d\n", stack_node->data); // 현재 노드의 데이터 출력
stack_node = stack_node->next; // 포인터에 다음 노드의 주소 저장
}
}
int main()
{
int list_data;
int num;
int list_num;
struct NODE *head = malloc(sizeof(struct NODE)); // head 노드 생성
head->next = NULL; // head 노드의 next는 NULL로 초기화
while(1){
printf("해당 번호를 선택해주세요(1 -> 데이터 추가, 2 -> 데이터 삭제) : ");
scanf("%d", &num);
if(num == 1){ // 1번, 즉, node를 삽입하는 경우 (Queue에 데이터를 삽입하는 경우)
printf("스택에 넣을 데이터를 입력하세요 : ");
scanf("%d", &list_data);
int list_count = 0;
struct NODE *current_node = head;
while(current_node->next != NULL){ // 포인터가 NULL일 때까지 계속 반복, 즉, 리스트의 마지막 부분까지 감
list_count++;
current_node = current_node->next;
}
Node_Insert(current_node, list_data); // 리스트의 마지막 부분에 새 노드 삽입 => Stack는 마지막 부분에 데이터를 삽입 => 현재 노드 뒤에 삽입할 것이므로 인자값으로 현재 노드를 넣음
struct NODE *stack_node = head->next; // 각 노드들을 보여주기 위한 첫 번째 부분 => head->next부터 첫 노드가 시작되므로 head->next가 첫 부분
Stack_Print(stack_node);
printf("\n");
}
else if(num == 2){ // 2번, 즉, node를 삭제하는 경우 (큐에 데이터를 삭제하는 경우)
int list_count = 0;
struct NODE *prev_node = head; // prev_node를 NULL이 아니라 head로 초기화하는 이유는 노드가 비어 있을 때 아래 while문이 돌지 않아 Node_Delete에 NULL이 들어가기 때문
struct NODE *current_node = head;
while(current_node->next != NULL){ // 포인터가 NULL일 때까지 계속 반복, 즉, 리스트의 마지막 부분까지 감
list_count++;
prev_node = current_node; // prev_node는 이전 노드
current_node = prev_node->next; // current_node는 prev_node->next, 즉, prev_node의 다음 노드
}
Node_Delete(prev_node); // 리스트의 마지막 노드 삭제 -> Stack는 맨 마지막의 데이터를 삭제 => 단, 이전 노드를 마지막 노드로 바꿔주기 위해 인자값으로 이전 노드를 넣음
struct NODE *stack_node = head->next; // 각 노드들을 보여주기 위한 첫 번째 부분 => head->next부터 첫 노드가 시작되므로 head->next가 첫 부분
Stack_Print(stack_node);
printf("\n");
}
else{ // 1번과 2번을 고르지 않고 다른 숫자를 입력한 경우
printf("1번과 2번만 선택 가능합니다.\n");
}
}
return 0;
}
위 코드는 push/pop 할 때마다 끝까지 탐색하여 연결리스트를 추가/삭제 하므로 시간복잡도가 O(n)이다.
또한 단일 연결리스트이기 때문에 앞에서부터 뒤로 출력하게끔 했는데 데이터가 뒤에 쌓이므로 결국 top부분이 뒤에 있는 것이다(물론 위에서 구현한 연결리스트처럼 top 부분을 포인터로 만들진 X).
그래서, 출력 시에도 위의 실행문들과는 다르게 Stack을 뒤집어놓은 모양으로 출력이 된다.
하지만 방향만 바뀌어서 그렇지 구현 자체는 문제가 없는 Stack이다. 11 => 22 => 33 => 44 순으로 push했는데 맨 마지막이 top이므로 아래로 쌓이는 것을 확인할 수 있다. 따라서, 화면에도 11 => 22 => 33 => 44로 보이고 삭제는 top 부분이 맨 마지막이므로 맨 마지막 부분부터 삭제되는 것을 확인할 수 있다.
참고 사이트
- https://daimhada.tistory.com/72?category=820522
- https://woovictory.github.io/2018/12/27/DataStructure-Diff-of-Array-LinkedList/
- https://mailmail.tistory.com/24?category=724615
- https://joshuajangblog.wordpress.com/2016/09/21/time_complexity_big_o_in_easy_explanation/
- https://dojang.io/mod/page/view.php?id=647
- https://milvus.tistory.com/17
'Algorithm' 카테고리의 다른 글
| Stack(스택) (1) (0) | 2020.09.24 |
|---|
댓글