[c/c++] 스택 ( Stack )

Stack 이란 ?

LIFO ( Last In First Out ) 형식의 자료구조

 

Stack 의 연산

• is_empty() : 스택이 비어있는지 검사한다.
• is_full() : 스택이 꽉 차있는지 검사한다.
• push( item ) : item 을 스택에 넣어준다.
• pop () : 스택의 가장 위의 항목을 제거한다.

Stack 구현

1. Array ( 배열 )
2. Linked List (연결리스트) ===> 연결리스트

 

1. Array ( 배열 )

전역변수로 구현 .

xxxxxxxxxx
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
​
//-----전역변수로 구현
typedef int element;
element stack[MAX_SIZE];
int top = -1;
​
int is_empty(){
    return top == -1;
}
​
int is_full(){
    return top == MAX_SIZE;
}
​
void push(element item)
{
    stack[++top] = item;
}
​
element pop()
{
    return stack[top--];
}
​
int main()
{
    push(1);
    push(2);
    push(3);
    
    printf("%d ",pop());//출력 : 3 2 1
}
​

 

저장해야 하는 정보의 요소가 복잡한 구조 일 때 Struct 기반의 Array 로 구현

x
//헤더 위와 같음
#define MAX_STACK_SIZE 100
#define MAX_STRING 100
​
typedef struct{
    int student_no;
    char name[MAX_STRING];
    char address[MAX_STRING];
}element;
​
element stack[MAX_STACK_SIZE];
int top = -1;
​
//is_empty , is_full , push , pop 위의 함수랑 똑같음
​
int main()
{
    element oi,oe;
    oi.student_no = 1;
    strcpy(oi.name,"우디");
    strcpy(oi.address,"앤디 방");
    
    push(oi);
    oe=pop();
    
    printf("학번 : %d\n",oe.student_no);
    printf("이름 : %s\n",oe.name);
    printf("주소 : %s\n",oe.address);
}

 

2. Linked List ( 연결리스트 )

노드들을 수직으로 나열하여 각 노드들이 아래의 노드를 가르키도록 하면 스택의 모양이 된다.

 

스택의 가장 위의 항목을 가르키는 top 변수는 전역변수로 두었다.

x
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
​
typedef int element;
typedef struct Stack {
    element data;
    struct Stack *link;
}Stack;
​
Stack *top = NULL;
​
void push(element item)
{
    Stack *s = (Stack*)malloc(sizeof(Stack));//노드 동적할당
    s->data = item;
    s->link = top;
    top = s;
}
​
element pop()
{
    Stack *removed = top;
    int data = top->data;
    top = top->link;
    free(removed);
    return data;
}
​
int main() {
    push(1);
    push(2);
    push(3);
    printf("%d ", pop());
    printf("%d ", pop());
    printf("%d ", pop());//출력 : 3 2 1
​
}
​
​