데이터 구조 및 알고리즘 Vol.4
13046 단어 C데이터 구조 및 알고리즘초보자
Vol.4: Stack
Stack 자료의 구조의 생각과 활용 방법에 대해 배웁니다.
C언어를 이용하여 Stack의 자료구조를 직접 구현할 수 있습니다.
Stack이란?
👌 Stack은 한쪽에 들어가서 한쪽에 나오는 자료 구조(Data Structure)입니다.
이 특성으로부터 수식 계산 등의 알고리즘에 있어서 다방면에 활용됩니다.
👌 Doubly Linked List의 각 노드는 이전 노드와 뒤 노드 정보를 모두 저장합니다.
기본적으로 push와 pop으로 구성되어 있습니다.
PUSH:Stack에 데이터를 넣습니다.
POP: Stack에서 데이터를 추출합니다.
예)
PUSH(7)-PUSH(5)-PUSH(4)-POP()-PUSH(6)-POP()
🤔 결과는?
Stack 구현
👌Stack은 배열을 이용한 구현 방법과 연결 목록을 이용한 구현 방법으로 나뉩니다.
👌 가장 기본적인 형태의 자료구조이며, 실현의 난이도는 낮은 편입니다.
배열을 이용한 Stack 실현
예) 실행할 코드의 예
//Stackの宣言
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10000
#define INF 9999999 //INF = infinite
int stack[SIZE];
int top = 1; //Stackの最上段(=入り口)を意味
//Stack挿入関数
void push(int data) {
if (top == SIZE - 1) {
printf("Stack overflowが発生しました。\n");
return;
}
stack[++top] = data;
}
//Stack抽出関数
int pop() {
if (top == -1) {
printf("Stack underflowが発生しました。\n");
return -INF;
}
return stack[top--];
}
//Stack全体の出力関数
void show() {
printf("--- Stackの最上段 ---\n");
for (int i = top; i >= 0; i--) {
printf("%d\n", stack[i]);
}
printf("--- Stackの最下段 ---\n");
}
//完成したStackを使用する
int main(void) {
push(7);
push(5);
push(4);
pop();
push(6);
pop();
show();
system("pause");
return 0;
}
🤔 결과는?result->
--- Stackの最上段 ---
5
7
--- Stackの最下段 ---
Linked List를 이용한 Stack 실현
예) 실행할 코드의 예
//Stackの宣言
#include <stdio.h>
#include <stdlib.h>
#define INF 99999999
typedef struct {
int data;
struct Node *next;
} Node;
typedef struct {
Node *top;
} Stack;
//Stack挿入関数
void push(Stack *stack, int data) {
Node *node = (Node*) malloc(sizeof(Node));
node->data = data;
node->next = stack->top;
stack->top = node;
}
//Stack抽出関数
int pop(Stack *stack) {
if (stack->top == NULL) {
printf("Stack underflowが発生しました。\n");
return -INF;
}
Node *node = stack->top;
int data = node->data;
stack->top = node->next;
free(node);
return data;
}
//Stack全体の出力関数
void show(Stack *stack) {
Node *cur = stack->top;
printf("--- Stackの最上段 ---\n");
while (cur != NULL) {
printf("%d\n", cur->data);
cur = cur->next;
}
printf("--- Stackの最下段 ---\n");
}
//完成したStackを使用する
int main(void) {
Stack stack;
stack.top = NULL;
show(&stack);
push(&stack, 7);
push(&stack, 5);
push(&stack, 4);
pop(&stack);
push(&stack, 6);
pop(&stack);
show(&stack);
system("pause");
return 0;
}
🤔 결과는?result->
--- Stackの最上段 ---
5
7
--- Stackの最下段 ---
STACK 구현의 주의점
❗Linked List로 Stack을 실현할 때 메모리 공간의 낭비 없이 효율적으로 구현할 수 있습니다.
요약
👌 Stack은 배열 또는 연결 목록을 사용하여 구현할 수 있습니다.
📚 참고 강의: 컴퓨터 공학 전공 필수 올인원 패키지 Online
👆 위의 강의는 C와 C++ 언어를 전제로 설명합니다.
Reference
이 문제에 관하여(데이터 구조 및 알고리즘 Vol.4), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/nys9302/items/752a103fcb7e4f3ac1a6
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
👌 Stack은 한쪽에 들어가서 한쪽에 나오는 자료 구조(Data Structure)입니다.
이 특성으로부터 수식 계산 등의 알고리즘에 있어서 다방면에 활용됩니다.
👌 Doubly Linked List의 각 노드는 이전 노드와 뒤 노드 정보를 모두 저장합니다.
기본적으로 push와 pop으로 구성되어 있습니다.
PUSH:Stack에 데이터를 넣습니다.
POP: Stack에서 데이터를 추출합니다.
예)
PUSH(7)-PUSH(5)-PUSH(4)-POP()-PUSH(6)-POP()
🤔 결과는?
Stack 구현
👌Stack은 배열을 이용한 구현 방법과 연결 목록을 이용한 구현 방법으로 나뉩니다.
👌 가장 기본적인 형태의 자료구조이며, 실현의 난이도는 낮은 편입니다.
배열을 이용한 Stack 실현
예) 실행할 코드의 예
//Stackの宣言
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10000
#define INF 9999999 //INF = infinite
int stack[SIZE];
int top = 1; //Stackの最上段(=入り口)を意味
//Stack挿入関数
void push(int data) {
if (top == SIZE - 1) {
printf("Stack overflowが発生しました。\n");
return;
}
stack[++top] = data;
}
//Stack抽出関数
int pop() {
if (top == -1) {
printf("Stack underflowが発生しました。\n");
return -INF;
}
return stack[top--];
}
//Stack全体の出力関数
void show() {
printf("--- Stackの最上段 ---\n");
for (int i = top; i >= 0; i--) {
printf("%d\n", stack[i]);
}
printf("--- Stackの最下段 ---\n");
}
//完成したStackを使用する
int main(void) {
push(7);
push(5);
push(4);
pop();
push(6);
pop();
show();
system("pause");
return 0;
}
🤔 결과는?result->
--- Stackの最上段 ---
5
7
--- Stackの最下段 ---
Linked List를 이용한 Stack 실현
예) 실행할 코드의 예
//Stackの宣言
#include <stdio.h>
#include <stdlib.h>
#define INF 99999999
typedef struct {
int data;
struct Node *next;
} Node;
typedef struct {
Node *top;
} Stack;
//Stack挿入関数
void push(Stack *stack, int data) {
Node *node = (Node*) malloc(sizeof(Node));
node->data = data;
node->next = stack->top;
stack->top = node;
}
//Stack抽出関数
int pop(Stack *stack) {
if (stack->top == NULL) {
printf("Stack underflowが発生しました。\n");
return -INF;
}
Node *node = stack->top;
int data = node->data;
stack->top = node->next;
free(node);
return data;
}
//Stack全体の出力関数
void show(Stack *stack) {
Node *cur = stack->top;
printf("--- Stackの最上段 ---\n");
while (cur != NULL) {
printf("%d\n", cur->data);
cur = cur->next;
}
printf("--- Stackの最下段 ---\n");
}
//完成したStackを使用する
int main(void) {
Stack stack;
stack.top = NULL;
show(&stack);
push(&stack, 7);
push(&stack, 5);
push(&stack, 4);
pop(&stack);
push(&stack, 6);
pop(&stack);
show(&stack);
system("pause");
return 0;
}
🤔 결과는?result->
--- Stackの最上段 ---
5
7
--- Stackの最下段 ---
STACK 구현의 주의점
❗Linked List로 Stack을 실현할 때 메모리 공간의 낭비 없이 효율적으로 구현할 수 있습니다.
요약
👌 Stack은 배열 또는 연결 목록을 사용하여 구현할 수 있습니다.
📚 참고 강의: 컴퓨터 공학 전공 필수 올인원 패키지 Online
👆 위의 강의는 C와 C++ 언어를 전제로 설명합니다.
Reference
이 문제에 관하여(데이터 구조 및 알고리즘 Vol.4), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/nys9302/items/752a103fcb7e4f3ac1a6
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
//Stackの宣言
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10000
#define INF 9999999 //INF = infinite
int stack[SIZE];
int top = 1; //Stackの最上段(=入り口)を意味
//Stack挿入関数
void push(int data) {
if (top == SIZE - 1) {
printf("Stack overflowが発生しました。\n");
return;
}
stack[++top] = data;
}
//Stack抽出関数
int pop() {
if (top == -1) {
printf("Stack underflowが発生しました。\n");
return -INF;
}
return stack[top--];
}
//Stack全体の出力関数
void show() {
printf("--- Stackの最上段 ---\n");
for (int i = top; i >= 0; i--) {
printf("%d\n", stack[i]);
}
printf("--- Stackの最下段 ---\n");
}
//完成したStackを使用する
int main(void) {
push(7);
push(5);
push(4);
pop();
push(6);
pop();
show();
system("pause");
return 0;
}
5
7
--- Stackの最下段 ---
//Stackの宣言
#include <stdio.h>
#include <stdlib.h>
#define INF 99999999
typedef struct {
int data;
struct Node *next;
} Node;
typedef struct {
Node *top;
} Stack;
//Stack挿入関数
void push(Stack *stack, int data) {
Node *node = (Node*) malloc(sizeof(Node));
node->data = data;
node->next = stack->top;
stack->top = node;
}
//Stack抽出関数
int pop(Stack *stack) {
if (stack->top == NULL) {
printf("Stack underflowが発生しました。\n");
return -INF;
}
Node *node = stack->top;
int data = node->data;
stack->top = node->next;
free(node);
return data;
}
//Stack全体の出力関数
void show(Stack *stack) {
Node *cur = stack->top;
printf("--- Stackの最上段 ---\n");
while (cur != NULL) {
printf("%d\n", cur->data);
cur = cur->next;
}
printf("--- Stackの最下段 ---\n");
}
//完成したStackを使用する
int main(void) {
Stack stack;
stack.top = NULL;
show(&stack);
push(&stack, 7);
push(&stack, 5);
push(&stack, 4);
pop(&stack);
push(&stack, 6);
pop(&stack);
show(&stack);
system("pause");
return 0;
}
5
7
--- Stackの最下段 ---
Reference
이 문제에 관하여(데이터 구조 및 알고리즘 Vol.4), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/nys9302/items/752a103fcb7e4f3ac1a6텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)