자료구조(10)_ 연결리스트 정리

작성일

array_stack 과 연결리스트 stack 코드 보기

#include<stdio.h>
#include<malloc.h>
#define SIZE 5

void push(int * stack, int * top, int data);
void pop(int * stack, int * top);
void peek(int * stack, int * top);

int main(void)
{
     int * stack = (int *)malloc(sizeof(int)*SIZE);
     int top = 0;
     push(stack, &top, 10);
     push(stack, &top, 20);
     push(stack, &top, 30);
     push(stack, &top, 40);
     push(stack, &top, 50);
     push(stack, &top, 60);
     peek(stack, &top);
     pop(stack, &top);
     pop(stack, &top);
     pop(stack, &top);
     pop(stack, &top);
     pop(stack, &top);
     pop(stack, &top);
     peek(stack, &top);
     return 0;
}

void push(int * stack, int * top, int data)
{
    if (*top == SIZE)
    {
    printf("stack overflow!!!\n");
    return;
    }
    stack[*top] = data;
    (*top)++;
}

void pop(int * stack, int * top)
{
    if (*top == 0)
    {
    printf("stack underflow!!!\n");
    return;
    }
    (*top)--;
    printf("%d 삭제\n", stack[*top]);
}

void peek(int * stack, int * top)
{
    if (*top == 0)
    {
    printf("no data!!!\n");
    return;
    }
    printf("top의 data : %d\n", stack[*top - 1]);
}

정리

스택이 하는 일을 소프트웨어에서 구현한 것. 동그란 원통이 stack이라고 생각하자.

프로그램 실행하면 -> main이 스택에 자리잡는다.

중요한 건 함수 실행시 가장 먼저 실행된 게 가장 나중에 삭제된다.

  1. 가장 나중에 들어온 데이터가 가장 먼저 삭제
  2. 탑을 통해서만 데이터의 입력과 삭제가 이루어진다.
  3. 동그란 원통을 생각해라

구현 방법은 두가지 1차원 배열과 연결리스트.

top은 0과 -1이 들어갈 수 있다.

0일 경우 데이터의 갯수 -1은 탑의 index 값을 이용하기 위해서

매개변수는 함수의 지역변수라고 이야기 했었다. top이 int 형이라면 반환값을 매번 써줘야 한다. 그런데 포인터를 쓰니까 직접 공간을 가리켜서 제어한다. 주소값을 전달하여 함수를 전달하는 방식을 콜바이 레퍼런스라고 한다.

콜바이 밸류는 기존 공간을 보호해야할 때 사용한다.

연결리스트

데이터가 필요할 때 마다 공간을 할당해준다. 즉 stack에 제한이 있으면 array로 구현. 제한이 없으면 연결리스트로 구현.

참고자료

kg아이티뱅크학원 (자료구조 수업)

문자열 포인터 참고 블로그

[동적할당을 이용한 문자열 처리]{https://m.blog.naver.com/PostView.nhn?blogId=kgsshow1994&logNo=140171859874&proxyReferer=https%3A%2F%2Fwww.google.com%2F}

0%