스택(Stack)


스택(Stack)?

스택은 LIFO(Last In First Out)구조로 


가장 나중에 들어간 값이 가장먼저 나오는 구조입니다.


삽입하는 PUSH와 삭제하는 POP 동작이 있습니다.


1. 스택 형태


2. PUSH


3. POP



배열을 이용한 예제


스택으로 사용할 int형 배열 선언 및 초기화 함수


#include "stdio.h"
#define MAX 10


int stack[MAX];
int top;


void init_stack(void){
top = -1;
}


스택에 push하는 함수


스택 크기보다 크면 오버플로우 발생


int push(int t){
if(top >=MAX-1){
printf("########### STACK OVER FLOW ###########\n");
return -1;
}else{
stack[++top] = t;
return t;
}
}


스택에서 pop하는 함수


스택 크기보다 작으면 오버플로우 발생


int pop(void){
if(top<0){
printf("########### STACK UNDER FLOW ###########\n");
return -1;
}
return stack[top--];
}

스택의 값을 출력하는 함수


void print_stack(void){
printf("PRINT STACK \n");
for(int i=top; i>=0; i--){
printf("%-6d",stack[i]);
}
printf("\n");
}

메인함수

11개의 값을 push할 경우 10개는 정상적으로 push 되지만,
나머지 1개의 값은 스택 오버플로우가 발생합니다.

두번째 pop을 수행할 때 5개의 값은 정상적으로 pop 되지만,
나머지 1개의 값은 스택 언더플로우가 발생합니다.

void main(){
init_stack();
printf("########### PUSH ###########\n");
for(int i=0; i<11; i++){
push(i);
}
print_stack();
printf("########### POP ###########\n");
for(int i=0; i<5; i++){
pop();
}
print_stack();
for(int i=0; i<6; i++){
pop();
}
}

실행 결과

참고 : C로 배우는 알고리즘 (이재규)






저작자표시 비영리

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 삽입 정렬(Insertion Sort)  (0) 2019.04.19
[C] 선택 정렬(Selection Sort)  (0) 2019.04.19
[C] 트리(Tree)  (0) 2019.04.07
[C] 큐(Queue)  (2) 2019.04.01
[C] 연결리스트(LinkedList)  (0) 2019.03.28

연결리스트(LinkedList)



연결리스트(LinkedList)?

연결리스트는 동적인 자료구조로 배열처럼 메모리에 연속된 공간을 차지하지 않습니다.


1. 단순 연결리스트(Simple LinkedList)


노드와 다음링크를 가리키는 링크로 구성


처음 시작을 의미하는 head와 마지막 노드인 tail로 구성

2. 환형 연결리스트(Circular LinkedList)


가장 마지막 노드가 처음의 노드를 가리키는 연결리스트

3. 이중 연결리스트(Doubly LinkedList)


전, 후 노드를 가리키는 링크를 가지는 연결리스트


단순 연결리스트 예제


구조체 (key, value, 다음을 가리키는 링크로 구성) 선언


typedef struct _node
{
int key; // key
char *value; // value
struct _node *next; // 다음 노드의 위치
} node;
node *head, *tail; // head, tail


초기화 함수

head 와 tail 초기화


void init_list(void){
head = (node*)malloc(sizeof(node));
tail = (node*)malloc(sizeof(node));
head -> next = tail;
tail -> next = tail;
}

노드 삽입 함수
입력받은 노드의 다음에 삽입


node *insert_list(int key, char *value, node *t){
node *s;
s = (node*)malloc(sizeof(node));
s->key = key;
s->value = value;
s->next = t->next;
t->next = s;
return s;
}

노드 삭제 함수
입력받은 노드를 삭제

int delete_list(node *t){
node *s = head;
while(s->next != tail){
if(s->next==t){
s->next = t->next;
free(t);
break;
}else{
s = s->next;
}
}
}

노드 검색 함수
key를 이용해서 원하는 노드를 검색

node *find_node(int key){
node *s = head->next;
while(s != tail->next){
if(key == s->key){
break;
}else{
s = s->next;
}
}
return s;
}


전체 검색 함수

void findAll(){
node * t = head->next;
printf("#########findAll()########\n");
while(t != tail){
printf("find(%d) = %s , address = %d\n",t->key,find_node(t->key)->value,&t->next);
t = t->next;
}
printf("##########################\n");
}

메인 함수
노드 초기화 후 5개 데이터를 추가하고 2개의 데이터 삭제 후 전체 출력

void main(){
init_list();
insert_list(0,"apple",head);
insert_list(1,"banana",find_node(0));
insert_list(2,"melon",find_node(1));
insert_list(3,"grape",find_node(2));
insert_list(4,"pineapple",find_node(3));

delete_list(find_node(2));
delete_list(find_node(1));
findAll();
}

실행 결과


참고 : C로 배우는 알고리즘 (이재규)


관련 포스팅


[Data Strcuture] - 트리(Tree)

[Data Strcuture] - 큐(Queue)

[Data Strcuture] - 스택(Stack)

[Data Strcuture] - 연결리스트(LinkedList)




저작자표시 비영리

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 삽입 정렬(Insertion Sort)  (0) 2019.04.19
[C] 선택 정렬(Selection Sort)  (0) 2019.04.19
[C] 트리(Tree)  (0) 2019.04.07
[C] 큐(Queue)  (2) 2019.04.01
[C] 스택(Stack)  (1) 2019.03.29

+ Recent posts

티스토리툴바