스택(Stack)

스택이란 한쪽으로 들어가서 한쪽으로 나오는 구조이다.

후입선출(Last In First Out)으로 나중에 들어간 값이 먼저 빠져나온다.

이러한 특성대문에 수식계산등의 알고리즘에서 다방면으로 활용된다.

push 와 pop이 존재하며 push는 데이터 삽입, pop은 제거다.

스택은 배열을 이용한 구현방법과 연결 리스트를 이용한 구현방법으로 나누어진다.

가장 기본적인 형태의 자료구조로 구현난이도는 낮은편이다.

 

스택의 처리방식은 후입선출이라고 위에 말했듯이 들어간 값들 중 제일 마지막에 들어간 값부터

빠져나온다.

2 4 3 1 5 7 6 의 순서로 값을 넣어주었다고 했을 때 스택에서 값을 하나 없애라고 한다면

제일 마지막에 들어간 6이 제거된다.

 

배열을 이용한 구현

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10000
#define INF 99999999

int stack[SIZE];
int top = -1;

void push(int data){
  if(top == SIZE - 1){
    printf("스택 오버플로우 발생\n");
    return;
  }
  stack[++top] = data;
}

int pop(){
  if(top == -1){
    printf("스택 언더플로우 발생");
    return -INF;
  }
  return stack[top--];
}

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

int main(void){
  push(7);
  push(5);
  push(4);
  pop();
  push(6);
  show();
  system("pause");
  return 0;
}

  위 코드의 결과값은

  6

  5

  7 이다.

  여기서 top은 스택의 최상단을 의미한다. 최상단이란 스택의 입구이다.

  삽입은 기본적인 배열에서의 삽입과 마찬가지이다. top을 계속 증가시켜주면서 값을 넣어주기 때문에

  뒤 인덱스로 값이 들어간다.

  pop부분을 보면 top을 --로 후치감소 시키면서 stack을 리턴한다.

  

  main함수내에서 7 5 4 의 순서로 값을 넣어줬기 때문에 그 순서 그대로 stack에 들어가게 되고

  pop에서는 가장 뒤에있는 값을 지워주기 때문에 7 5만이 stack에 남고 6을 다시 넣어주었으니 6이 추가로 들어가게

  되면서 7 5 6 의 순서가 되는것이다.

  

  출력이 6 5 7 순서로 나오게 된 것은 스택의 입구가 맨 위라고 가정했을때의 출력이기 때문이다.

 

연결리스트를 이용한 스택

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define INF 99999999

typedef struct{
  int data;
  struct Node *next;
} Node;

typedef struct{
  Node *top;
} Stack;

void push(Stack *stack, int data){
  Node *node = (Node*)malloc(sizeof(Node));
  node->data = data;
  node->next = stack->top;
  stack->top = node;
}

int pop(Stack *stack){
  if(stack->top == NULL){
    printf("스택 언더플로우 발생.\n");
    return -INF;
  }
  Node *node = stack->top;
  int data = node->data;
  stack->top = node->next;
  free(node);
  return data;
}

void show(Stack *stack){
  Node *cur = stack->top;
  
  while(cur != NULL){
    printf("%d\n", cur->data);
    cur = cur->next;
  }
}

int main(void){
  Stack stack;
  stack.top = NULL;
  push(&stack, 7);
  push(&stack, 5);
  push(&stack, 4);
  pop(&stack);
  push(&stack, 6);
  show(&stack);
  system("pause");
  return 0;
}

  이 코드역시 마찬가지로 결과값은

  6

  5 

  7 이다.

  처리방식은 배열과 동일하다. 첫 구조체인 Node에서는 연결리스트 형태이기 때문에 node를 정의하고

  Stack이라는 구조체를 따로 생성한 후에 top이라는 노드를 생성한다.

  

  push에서는 node를 새로 메모리할당 받고 그 node의 data에 원하는 값을 넣어준다.

  node의 next는 stack의 top에 연결되며 stack의 top은 node의 값을 갖게 된다.

  여기서 이해가 안되서 한참을 켜놓고 고민했는데

  top이라는 노드는 말그대로 최상단 노드를 의미하는것일 뿐이다.

  코드만 있는 그대로 보자면 node의 next가 top에 연결되는데 stack의 top은 node의 data가 된다?

  node7의 next는 top인데 top을 node7로 만들어준다는게 뭔소린가......... 그러고 계속 고민을 했다.

  top이라는 것은 stack구조체에서 만든 node이고 껍데기 정도라고 생각하면 될것 같다.

  그냥 타이틀정도? 니가 1등이야 이정도 생각하면 될것같다.

  1등은 node7이라는 것이고 node7은 다음 노드로 top을 갖고 있다는 것이다.

  다음 입력을 보면 5가 들어오는데 그럼 node5는 top을 next로 갖는것이지만 실질적으로 top은

  node7이기 때문에 node5는 next로 node7을 갖게 되고 top은 node5로 넘어가게 되는것이다.

  그렇다면 top인 node 5는 node7을 next로 갖게 되니까 5 7 형태로 연결되게 되는것이다.

  같은 형태로 4까지 들어가 4 5 7이 들어가고 다음 pop을 처리한다.

 

  pop에서는 top이 NULL이라면 스택에 아무런 노드가 존재하지 않는다는 것이 되므로 언더플로우가 발생했다고

  알린다.

  그게 아니라면 stack의 top을 의미하는 node를 정의하고 top의 data를 data라고 정의한다.

  여기서 stack의 top을 의미하는 node를 topNode라고 한다면 

  stack의 top은 topNode의 next가 되는 것인데 처리된 현황으로 본다면 4가 topNode이고 next는 5를 갖고 있으므로

  top은 node5가 되는 것이다.

  그런 다음 free()를 이용해 삭제하고자했던 노드의 메모리할당을 해제해준다.

  

  show의 경우는 아까와 같은 상단인 입구가 윗부분이라는 전제하에 출력하도록 한 부분이다.

 

 

레퍼런스

패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직