[자료구조 - C언어] 자료구조 제15강: 스택(Stack) 개념과 구현(2)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

1. 배열을 이용한 스택의 구현

//stack.c

#define MAX_CAPACITY 100

int is_full();

//문자들을 저장하는 스택
//스택에 저장되는 데이터의 타입을 문자(char)라고 가정
char stack[MAX_CAPACITY];
//스택의 top을 표시하는 변수 ~ 스택의 어디까지 데이터가 차 있다를 표시
int top = -1;       //-1은 실제 스택 데이터의 위치를 반영

//새로운 데이터를 추가 함수
void push(char ch){
    if(is_full())    //스택이 가득차면 push할 수 없다.
        return;
    top++;
    stack[top]=ch;
    
    //만약 int top=0;으로 시작하면 아래와 같은 순서로 구현
    //stack[top]=ch;
    //top++;
}

int is_full(){
    return top==MAX_CAPACITY-1;    //배열은 0부터 시작
}

//스택의 top에 있는 값 삭제 후 반환 함수
char pop(){
    if(is_empty())    //스택이 비어있지 않을 때만 동작
        return NULL;
    char tmp = stack[top];
    top--;
    return tmp;
}

//스택의 top에 있는 값 리턴 함수
char peek(){
    //peek을 호출하기 전에 먼저 empty인지 검사해야 한다.
    return stack[top];
}

char is_empty(){
    return top==-1;    //top이 -1인지
}

 

2. 연결 리스트를 이용한 스택의 구현

• 연결 리스트의 맨 앞이 노드를 삽입/삭제하기에 편하다 → 맨 앞을 stack의 top으로 한다.
  • 단방향 연결 리스트에서 노드를 삭제할 때 이전 노드의 주소가 필요하다.

    

    • 맨 마지막이 top이라면 삭제 시 그 앞의 노드의 주소가 필요한데
      • 이는 곧 전체 노드를 순회한다는 의미와 동일
  • add_first → push 역할
  • remove_first → pop 역할

2-1. 노드 구조

struct node{
    char *data;
    struct node *next;
};
typedef struct node Node;

Node *top = NULL;

2-2. 스택 구현

//stack.c

#include <stdio.h>
#include <stdlib.h>

int is_empty();

struct node{
    char *data;
    struct node *next;
};
typedef struct node Node;

Node *top = NULL;

//연결리스트로 보자면 add_first()와 동일
void push(char *item){
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = item;
    p->next = top;
    top = p;
}

char *pop(){
    if(is_empty())   //스택이 비어있지 않을 때만 동작
        return NULL;
    Node *p = top;
    char *result = p->data;  //top 노드에 저장되어 있는 데이터를 임시 보호
    top = p->next;           //top 한 칸 전진
    free(p);
    return result;
}

char *peek(){
    if(is_empty())
        return NULL;
    return top->data;
}

int is_empty(){
    return top==NULL;
}

 

3. 문제점

• 만약 스택이 동시에 2개 이상 필요하다면?
  • 같은 로직이지만 이름이 다른 변수

  char stack1[];
  int top1 = -1;
  void push1(char *ch);
  char *pop1();
  ...
  
  char stack2[];
  int top2 = -1;
  void push2(char *ch);
  char *pop2();
  ...
  

• 서로 다른 타입의 데이터를 저장할 스택이 필요하다면?

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://www.youtube.com/watch?v=Vj_JOmL1nyE&t=1109s