Dipa's document

C로 구현한 스택

#include<stdio.h>
#include<string.h>
 
#define TRUE 1            //1반환 
#define FALSE 0           //0반환 
#define MINUS -1          //-1반환 
#define MAX_SIZE 10000    //스택 배열 사이즈 
 
typedef struct _stack{    //스택 구조체. 
    int arr[MAX_SIZE];
    int top;
} Stack;
 
void StackInit(Stack * sp){    //스택 초기화 함수 
    sp->top = -1;
}
 
int IsEmpty(Stack * sp){    //스택이 비어있는지 확인 
    if(sp->top == -1) return TRUE;
        
    return FALSE;
}
 
int Size(Stack *sp){    //스택의 size 반환 
    return sp->top + 1;
}
 
 
int IsFull(Stack * sp){        //스택이 꽉 차있는지 확인 
    if(sp->top + 1 >= MAX_SIZE) return TRUE;
    
    return FALSE;
}
 
void Push(Stack * sp, int data){    //스택의 push 
    if(IsFull(sp)==TRUE) return;
    
    //top을 하나 올린 후 data 삽입
    sp->arr[++(sp->top)] = data;    
}
 
int Pop(Stack * sp){    //스택의 pop. 
    if(IsEmpty(sp) == TRUE) return MINUS;
 
    //top이 가리키는 값을 반환 후 top을 하나 내림.
    return sp->arr[(sp->top)--];
}
 
int Peek(Stack *sp){    //스택의 맨위의 인자를 반환합니다. 
    if(IsEmpty(sp) == TRUE) return MINUS;
    
    return sp->arr[sp->top];
}


int main(void){
    int i;
    char str[6];
    Stack stack;
    int n, num;
    
    scanf("%d", &n);
    fgetc(stdin);    //버퍼 비우기 
    StackInit(&stack);    //stack 초기화. 
    
    
    for(i=0; i<n; i++){
    
        scanf("%s", str);
        fgetc(stdin);    //버퍼 비우기. 
 
        if(!strcmp(str, "push")){    //push 인 경우 
            
            scanf("%d", &num);
            fgetc(stdin);    //버퍼 비우기. 
            Push(&stack, num);    
            
        }else if(!strcmp(str, "pop")){    //pop인 경우 
        
            printf("%d\n", Pop(&stack));
        
        }else if(!strcmp(str, "empty")){    //empty인경우 
            
            printf("%d\n", IsEmpty(&stack));
            
        }else if(!strcmp(str, "size")){        //size인 경우  
        
            printf("%d\n", Size(&stack));
        
        }else if(!strcmp(str, "top")){        //top인 경우 
        
            printf("%d\n", Peek(&stack));
        
        }
    }
    
    
    return 0;    
}

JAVA 로 구현한 스택

import java.util.Scanner;
import java.util.Stack;

public class p1 {

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < n; i++) {
            String str = sc.nextLine();
 
            String instruction[] = str.split(" ");
 
            switch (instruction[0]) {
            case "push":
                stack.push(Integer.parseInt(instruction[1]));
                break;
 
            case "pop":
                if(stack.isEmpty()){
                    System.out.println(-1);
                }
                else{
                    System.out.println(stack.pop());
                }
                break;
 
            case "size":
 
                    System.out.println(stack.size());
                break;
 
            case "empty":
                if(stack.isEmpty()){
                    System.out.println(1);
                }
                else{
                    System.out.println(0);
                }
                break;
 
            case "top":
                if(stack.isEmpty()){
                    System.out.println(-1);
                }
                else{
                    System.out.println(stack.peek());
                }
                break;
 
            }
 
        }
	}
}

오늘은 자료구조은 스택(STACK)  에 대해서 알아보도록 하겠습니다.

스택이란 ? 사전적 의미로는 '쌓다'인데 말그대로 정말 쌓는것을 의미를 합니다. 바구니(공간)에 물건(데이터)을 쌓은뒤, 나중에 다시 물건을 뺴는 구조입니다. 

따라서 물건을 계속 쌓다가 나중에 처음에 넣은 물건을 빼려고 할때는, 마지막에 넣은 물건부터 차례차례 뺴야지 처음에 넣음 물건을 뺄 수 있겠죠? 이러한 방법이 자료구조에 '스택' 이라고 정의를 할 수 있습니다. 

그래서 스택의 구조는 먼저들어간 데이터는 나중에 나온다 => 선입후출 (First-In,Last-Out --> FILO)구조라고도 불립니다.

스택의 특징

(1) 삽입 (Push) : 그림과 같이 물건을 집어 넣는 것을 Push라 합니다. Push는 스택의 구조상 마지막 데이터 위치에 삽입이 됩니다. 나중에 코딩 할 때, 마지막 데이터 위치를 기억하기 위해 top이라는 변수를 만듭니다. 삽입을 한다면 top은 +1이 되겠죠?

(2) 삭제 (Pop) : Push와 반대로 물건을 빼는 것을 Pop이라 합니다. Pop도 Push와 마찬가지로 마지막 데이터 위치에서 삭제가 됩니다. Pop을 하게 된다면 top의 위치는 -1이 됩니다. 

(3) 읽기 (Peek) : 마지막 위치(top)에 해당하는 데이터를 읽습니다. 이 때, top의 변화는 없습니다.

이러한 자료구조의 스택을 구현을 할때, JAVA같은 경우는 java.util.stack이 구현이 되어 있어서 쓰기 편하지만.. 그래도 본인이 직접 스택을 구현을 해보는 것이 좋겠죠? ㅎㅎ

알고리즘 카테고리에 C로 구현한 스택과 JAVA로 구현한 스택을 공유 하도록 하겠습니다~