[DataStructure] 스택(Stack) feat. C, Java

자료구조 스택에 대해서 정리를 해보자.

 

스택(Stack)이란

스택(Stack)은 컴퓨터 과학에서 사용되는 선형 자료구조 중 하나이다. 스택은 데이터를 일식적으로 저장하거나 관리하는데 사용되며, 데이터를 쌓아 올리거나 데이터를 순서대로 꺼내는 작업을 수행할 수 있다. 이러한 작업은 "Last-In, First-Out" (LIFO) 방식으로 동작한다.

마지막으로 삽입된 데이터가 가장 먼저 상제되는 구조를 가지고 있다.

 

스택은 일상 생활에서 책을 쌓아 올리거나 동전을 쌓아놓는 것과 유사한 개념으로 이해할 수 있다. 책을 쌓으면 가장 위에 샇인 책이 먼저 빠지게 되고, 동전을 쌓아놓으면 가장 마지막에 쌓은 동전이 가장 먼저 나오게 된다.

 

스택의 주요 연산

1. Push : 스택에 데이터를 넣는 연산이다. 새로운 데이터가 스택의 맨 위에 쌓인다.
2. Pop : 스택에서 데이터를 꺼내는 연산이다. 스택의 맨 위에 있는 데이터가 삭제되고 반환된다.
3. Peek 또는 Top : 스택의 맨 위에 잇는 데이터를 조회하는 연산이다. 삭제하지 않고 데이터에 접근만 할 수 있다.
4. isEmpty : 스택이 비어있는지 여부를 확인하는 연산이다. 스택이 비어 있을 경우 true를 반환한다.

 

스택의 주요 연산 시간복잡도

1. Push : 시간복잡도 O(1)이다.
2. Pop : 시간복잡도 O(1)이다.
3. Peek 또는 Top : 시간복잡도 O(1)이다.
4. isEmpty : 시간복잡도 O(1)이다.
5. Search : 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하므로 O(n) 의 시간 복잡도이다.

 

스택의 활용

스택은 컴퓨터 프로그래밍에서 다양한 분야에서 활용되며, 함수 호출이나 재귀 알고리즘, 수식의 계산, 브라우저의 뒤로가기 버튼과 같은 기능에서도 사용된다.

 

stack

https://blog.naver.com/javaking75/220226369586

[자료구조] 자바스크립트로 스택(Stack) 구현

 

스택 with C

스택의 배열 기반 구현

1. ArrayBaseStack.h

#ifndef __AB_STACK_H__
#define __AB_STACK_H__

#define TRUE 1
#define FALSE 0
#define STACK_LEN 100

typedef int Data;

typedef struct _arrayStack
{
    Data stackArr[STACK_LEN];
    int topIndex;
} ArrayStack;

typedef ArrayStack Stack;

void StackInit(Stack * pstack);
int SIsEmpty(Stack * pstack);

void SPush(Stack * pstack, Data data);
Data SPop(Stack * pstack);
Data Speek(Stack * pstack);

#endif

 

2. ArrayBaseStack.c

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

void StackInit(Stack * pstack){
    pstack -> topIndex = -1;
}

int SIsEmpty(Stack * pstack){
    if(pstack -> topIndex == -1){
        return TRUE;
    } else{
        return FALSE;
    }
}

void SPush(Stack * pstack, Data data){
    pstack -> topIndex += 1;
    pstack -> stackArr[pstack -> topIndex] == data;
}

Data SPop(Stack *pstack){
    int rIdx;
    if(SIsEmpty(pstack)){
        printf("Stack Memory Error!");
        exit(-1);
    }
    rIdx = pstack -> topIndex;
    pstack -> topIndex -= 1;

    return pstack -> stackArr[rIdx];
}

Data SPeek(Stack *pstack){
     if(SIsEmpty(pstack)){
        printf("Stack Memory Error!");
        exit(-1);
    }
    return pstack -> stackArr[pstack->topIndex];
}

 

3.ArrayBaseStackMain.c

#include <stdio.h>
#include "ArrayBaseStack.h"

int main(void){
    // Stack 생성 및 초기화
    Stack stack;
    StackInit(&stack);

    // 데이터 넣기
    SPush(&stack, 1);
    SPush(&stack, 2);
    SPush(&stack, 3);
    SPush(&stack, 4);
    SPush(&stack, 5);

    // 데이터 꺼내기
    while(!SIsEmpty(&stack)) printf("%d ", SPop(&stack));
    // 5 4 3 2 1
    
    return 0;

}

 

스택의 연결리스트 기반 구현 

1. ListBaseStack.h

#ifndef __LB_STACK_H__
#define __LB_STACK_H__

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct _node
{
    Data data;
    struct _node *next;
} Node;

typedef struct _listStack
{
    Node *head;
} ListStack;

typedef ListStack Stack;

void StackInit(Stack *pstack);
int SIsEmpty(Stack *pstack);

void SPush(Stack *pstack, Data data);
Data SPop(Stack *pstack);
Data SPeek(Stack *pstack);

#endif

 

2. ListBaseStack.c

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

void StackInit(Stack *pstack){
    pstack->head = NULL;
}

int SIsEmpty(Stack *pstack){
    if(pstack -> head == NULL) return TRUE;
    else return FALSE;
}

void SPush(Stack *pstack, Data data){
    Node * newNode = (Node*)malloc(sizeof(Node));

    newNode->data = data;
    newNode->next = pstack->head; 

    pstack -> head = newNode;
}

Data SPop(Stack *pstack){
    Data rdata;
    Node *rnode;

    if(SIsEmpty(pstack)){
        printf("Stack Memory Erorr!");
        exit(-1);
    }

    rdata = pstack->head->data;
    rnode = pstack->head;

    pstack->head = pstack->head->next;
    free(rnode);

    return rdata;
}

Data SPeek(Stack *pstack){
    if(SIsEmpty(pstack)){
        printf("Stack Memory Erorr!");
        exit(-1);
    }

    return pstack->head->data;
}

 

3. ListBaseStackMain.c

#include <stdio.h>
#include "ListBaseStack.h"

int main(void){

    // Stack 생성 및 초기화
    Stack stack;
    StackInit(&stack);

    // 데이터 넣기
    SPush(&stack, 1);
    SPush(&stack, 2);
    SPush(&stack, 3);
    SPush(&stack, 4);
    SPush(&stack, 5);

    // 데이터 꺼내기
    while (!SIsEmpty(&stack)) printf("%d ", SPop(&stack));
    //5 4 3 2 1
    
    
    return 0;
}

 

스택 with Java

package ch04_Stack;

public class IntStack {

    private int[] stk;
    private int capacity;
    private int ptr;

    // 실행 시 예외 : 스택이 비어있음
    public class EmptyIntStackException extends RuntimeException {
        public EmptyIntStackException() {
        }
    }

    // 실행 시 예외 : 스택이 가득 참
    public class OverflowIntStackException extends RuntimeException {
        public OverflowIntStackException() {
        }
    }

    // 생성자
    public IntStack(int maxlen) {
        ptr = 0;
        capacity = maxlen;
        try {
            stk = new int[capacity];
        } catch (OutOfMemoryError e) {
            capacity = 0;
        }
    }

    // 스택에 X를 푸시
    public int push(int x) throws OverflowIntStackException {
        if (ptr >= capacity)
            throw new OverflowIntStackException();
        return stk[ptr++] = x;
    }

    // 스택에서 데이트를 팝(꼭대기에 있는 데이터를 꺼냄)
    public int pop() throws EmptyIntStackException {
        if (ptr <= 0)
            throw new EmptyIntStackException();
        return stk[--ptr];
    }

    // 스택에서 데이터를 피크(꼭대기에 있는 데이터를 조회)
    public int peek() throws EmptyIntStackException {
        if (ptr <= 0)
            throw new EmptyIntStackException();
        return stk[ptr - 1];
    }

    // 스택을 비움
    public void clear() {
        ptr = 0;
    }

    // 스택에서 x를 찾아 인덱스(없으면 -1)를 반환
    public int indexOf(int x) {
        for (int i = ptr - 1; i >= 0; i++)
            if (stk[i] == x)
                return i;
        return -1;
    }
    
    // 스택의 용량을 반환
    public int getCapacity(){
        return capacity;
    }

    // 스택의 쌓여있는 데이터를 반환
    public int size() {
        return ptr;
    }
    
    // 스택이 비어있는가?
    public boolean isEmpty() {
        return ptr <= 0;
    }
    
    // 스택이 가득 찼는가?
    public boolean isFull() {
        return ptr >= capacity;
    }
    
    // 스택 안의 모든 데이터를 바닥 -> 꼭대기 순서로 출력
    public void dump() {
        if (ptr <= 0) {
            System.out.println("스택이 비어 있습니다.");
        } else {
            for (int i = 0; i < ptr; i++) {
                System.out.println(stk[i] + " ");
            }
            System.out.println();
        }
    }
}

 

참고

열혈 자료구조

Do it! 자료구조와 함께 배우는 알고리즘 입문 자바편

 

Code

https://github.com/ois0886/DataStructure_with_C/tree/main/ch06_Stack