스택 자료구조에 대해 알아보고, 이를 직접 구현하며 자세히 알아보겠습니다.

스택은 자료구조의 한 종류로, 나중에 입력한 정보를 가장 먼저 꺼낼 수 있는 구조를 갖는 자료구조입니다. 이러한 구조를 LIFO (Last In First Out) 라고 합니다.
항상 넣은 순서의 반대로 꺼낼 수 있게 한쪽 방향이 막혀있습니다.
Stack의 의미를 생각해보면, 무언가가 쌓여있는 것을 생각하게 되는데,
쌓여있는 것의 맨 마지막 것 부터 뺄 수 없는것과 같은 이치입니다.
스택을 구현한다는 것은, 한쪽으로만 꺼낼 수 있는 구조를 만들어 주는 것이라고 볼 수 있겠습니다.
구현
구현은 Array로 해도 되고 Linked List로 해도 되지만, 이 글에선 Linked List를 이용하여 구현합니다.
typedef struct node_t { // node 구조체 정의 int val; struct node_t * next; } node; typedef struct stack_t { // Stack 구조체 정의 struct node_t * front; int size; } Stack;
우선 node와 Stack 타입을 정의해줍니다.
node는 저장할 값과 다음 node로의 포인터를 저장합니다.
Stack은 스택의 가장 맨 위에 있는 node를 가리키는 front와 스택의 사이즈를 저장합니다.
Stack * CreateStack(){ // Stack을 생성하고, 그 포인터를 리턴 Stack * newStack = (Stack *)malloc(sizeof(Stack)); if(newStack==NULL){ printf("Fail when creating Stack pointer"); return NULL; } newStack->front = NULL; newStack->size = 0; return newStack; }
스택을 생성하는 함수를 만듭니다. 스택의 크기에 해당하는 메모리를 할당한 후
front와 size 값을 초기화 한 후 포인터를 리턴합니다.
node * CreateNode(int val){ // node를 생성하고, 그 포인터를 리턴 node * newNode = (node *)malloc(sizeof(node)); if(newNode == NULL){ printf("Fail when creating new node pointer"); return NULL; } newNode->val = val; newNode->next = NULL; return newNode; }
노드를 생성하는 함수를 만듭니다. 값을 넣으면 node에 해당하는 메모리를 동적 할당하여 리턴합니다.
void stackPush(Stack * stack, int val){ // stack과 값을 넣으면 해당 stack에 값을 넣어줌 node * newNode = CreateNode(val); if(newNode == NULL) return; if(stack->front == NULL) stack->front = newNode; else{ newNode->next = stack->front; stack->front = newNode; } stack->size++; }
스택에 Push 합니다. 스택과 넣을 값을 입력하면
함수 내에서 node를 생성하고, 현재 front에 있는 node를 생성한 node가 가르키게 하고,
생성한 node를 front로 지정합니다.
그 후 스택의 사이즈를 증가시킵니다.
int stackPop(Stack *stack){ int ret = stack->front->val; node * del = stack->front; stack->front = stack->front->next; free(del); stack->size--; return ret; }
스택에 Pop 합니다. 스택을 입력하면
스택의 맨 첫번쨰 요소를 꺼내서 리턴하고 스택에서 제거해야 합니다.
스택의 "맨 위"에있는 요소가 가르키는 요소를 "맨 위"로 올려주고
기존에 "맨 위"였던 요소를 제거해줍시다.
물론 값은 반환해야 합니다.
void PrintStackState(Stack *stack){ node * nodePtr = stack->front; int i = stack->size; printf("Stack's total size : %d\n", i); while(nodePtr != NULL){ printf("Stack's %dth floor value : %d\n", i, nodePtr->val); nodePtr = nodePtr->next; i--; } }
스택에 있는 모든 요소를 탐색하고 싶다면
각 node가 가리키고 있는 요소들을 하나씩 탐색해주면 됩니다.
자료구조의 가장 기초가 되는 스택에 대해 알아보았습니다 :)
'자료구조 & 알고리즘 > 자료구조' 카테고리의 다른 글
[6] Heap (0) | 2020.10.28 |
---|---|
[5] 이진 탐색 트리 (2) | 2020.10.28 |
[4] 큐 (0) | 2020.10.25 |
[2] Segment Tree (Lazy Propagation) (0) | 2020.09.28 |
[1] Segment Tree (2) | 2020.09.13 |
댓글