[선형 자료구조] 스택(Stack)

스택(Stack)

컴퓨터의 기본 선형 자료구조 중 하나로 LIFO(Last In First Out), 후입선출의 특징을 갖는다.

기본적으로 데이터 추가(Push), 꺼내기(Pop), 스택 공간 확인 동작으로 이루어진다. 가장 먼저 데이터가 들어온 위치를 Bottom, 가장 마지막에 데이터가 들어온 위치를 Top이라고 한다.

 

스택 오버플로우(Overflow), 언더플로우(Underflow)

오버플로우 - 스택 크기만큼 데이터가 꽉 차서 더이상 들어가지 않을 때

언더플로우 - 스택이 비어있는데 데이터를 꺼내려고 하는 경우

 

스택 사용처

• 데이터가 입력된 순서의 역순으로 처리되어야 할 때
• 함수 콜 스택(함수1 안에서 함수2 안에서 함수3을 호출했을 때, 함수3이 끝나고 다시 함수2로 넘어가고 함수2가 끝나고 다시 함수1로 넘어가는 그런 것의 정보가 함수 콜 스택이라는 공간에 저장된다.)
• 수식 계산(숫자와 연산자를 처리할 때 스택 자료구조를 이용하면 좀 편리하게 계산이 가능하다고 한다.)
• 인터럽트 처리(인터럽트는 갑작스럽게 발생한 일)
• 그래프 깊이우선탐색(DFS - Depth First Search)
• 재귀함수 호출시 사용
• 뒤로가기(undo)

스택 시간복잡도 ( Big O )

• 삽입(Insertion) - O(1)
• 삭제(Deletion) - O(1)(pop) / O(N)(remove)
• 검색(Search) O(N)

삽입과 삭제는 top에서만 일어나므로 O(1)이다.

스택(Java)

자바에서는 java.util.Stack;에 만들어진 스택 자료구조가 존재한다.  컬렉션 프레임워크의 일부이다.

 

주로 사용하는 메소드

 

메소드 이름	사용 예시	설명
push	stack.push(1);	스택에 데이터를 넣는다. 제네릭으로 타입에 제한을 두지 않는다면 어떤 타입이든 들어갈 수 있다.
pop	stack.pop();	스택에서 데이터를 빼는 함수, 가장 최근에 들어간 데이터를 뺀다. 데이터가 더이상 없는데 pop을 해주면 에러가 나오므로 예외처리를 해줘야한다.
peek	stack.peek();	pop()과 같은 데이터를 가져오는 함수. pop()은 뽑은 데이터가 사라지지만 peek()는 사라지지 않는다. 데이터가 더이상 없는데 peek을 해주면 에러가 나오므로 예외처리를 해줘야한다.
contains	stack.contains(1);	contains 내부의 값이 스택 내부에 있는지 확인하는 함수. boolean 타입으로 반환한다.
size	stack.size();	현재 스택 크기를 반환한다.
empty / isEmpty	stack.empty(); stack.isEmpty();	빈 스택이라면 true, 아니면 false를 반환한다.
clear	stack.clear();	빈 스택으로 만들어주는 함수.
add	stack.add(3); stack.add(4, 3);	인자가 하나면 push()와 같고, 둘이면 (인덱스, 데이터)이다. 원하는 위치에 데이터를 넣을 수 있다. 인덱스가 스택 크기를 초과하면 안된다.
search	stack.search(3);	스택에 해당 데이터가 있는 인덱스를 반환한다.

사용 예시

 

    public static void main(String[] args) {
        Stack stack1=new Stack();
        Stack <Integer>stack2=new Stack(); // 정수형 stack
        Stack <? super Number>stack3=new Stack(); // 숫자만 받는 stack
        String[] arr = {"Hi", "Im", "Ian"};

        stack1.push(1);
        stack1.push(3.14);
        stack1.push('a');
        stack1.push("문자열");
        stack1.push(arr);
        stack1.push(5);
        System.out.println(stack1);         // [1, 3.14, a, 문자열, [Ljava.lang.String;@1b6d3586, 5]
        System.out.println(stack1.pop());   // 5
        System.out.println(stack1);         // [1, 3.14, a, 문자열, [Ljava.lang.String;@1b6d3586]
        System.out.println(stack1.peek());  // [Ljava.lang.String;@1b6d3586
        System.out.println(stack1);         // [1, 3.14, a, 문자열, [Ljava.lang.String;@1b6d3586]
        System.out.println(stack1.size());  // 5
        System.out.println(stack1.empty()); // false
        System.out.println(stack1.isEmpty()); // false
        stack1.clear();
        System.out.println(stack1.isEmpty()); // true

        stack2.push(1);
        stack2.push(3.14);  //에러
        stack2.push('a');   //에러
        stack2.push("문자열");//에러
        stack2.push(arr);       //에러

        stack3.push(1);
        stack3.push(3.14);
        stack3.push('a');   //에러
        stack3.push("문자열");//에러
        stack3.push(arr);       //에러

위 스택을 사용할 수 없는 경우, 직접 스택을 구현해야 한다. 직접 구현에는 보통 2가지 방법이 있다.

 

1) ArrayList를 이용한 스택 구현

 

import java.util.ArrayList;

class MyStack {
    ArrayList list;

    MyStack() {
        this.list = new ArrayList();
    }

    public boolean isEmpty() {
        if(this.list.size()==0) return true;
        return false;
    }

    public void push(int data) {
        this.list.add(data);
    }

    public Integer pop() {
        if(this.isEmpty()){ // 예외처리
            System.out.println("Stack is empty!");
            return null;
        }
        int data= (int) this.list.get(this.list.size()-1);
        this.list.remove(this.list.size()-1);
        return data;
    }

    public Integer peek() {
        if(this.isEmpty()){
            System.out.println("Stack is empty!");
            return null;
        }
        int data= (int) this.list.get(this.list.size()-1);
        return data;
    }
    
}

ArrayList를 이용하여 만들면 크기(size)가 유기적이다.

 

2) 배열을 이용한 스택 구현

 

class MyStack {
    int[] arr;
    int top = -1; // 빈 스택일 경우 top은 -1로 설정한다.

    MyStack(int size) {
        arr = new int[size];
    }

    public boolean isEmpty() {
        if(this.top==-1) return true;
        return false;
    }

    public boolean isFull() {
        if(this.top==this.arr.length-1) return true;
        return false;
    }

    public void push(int data) {
        if(this.isFull()) {
            System.out.println("Stack is Full");
            return;
        }
        this.top++;
        this.arr[this.top]=data;
    }

    public Integer pop() {
        if(this.isEmpty()){
            System.out.println("Stack is Empty");
            return null;
        }
        int data=this.arr[this.top];
        this.top--;
        return data;
    }

    public Integer peek() {
        if(this.isEmpty()){
            System.out.println("Stack is Empty");
            return null;
        }
        return this.arr[this.top];
    }
    
}

배열은 크기가 정해져있기 때문에 isFull()이 필요하다.

스택(Python)

파이썬 파이썬 내장모듈에서는 따로 스택 라이브러리가 존재하지 않는다.

그래서 보통 덱 라이브러리를 import 해서 스택 대신 사용하기도 한다.

직접 구현시 파이썬에서는 리스트 혹은 연결리스트로 스택을 만들어내거나 클래스를 이용해 구현한다.

리스트에는 append(=push), pop 기능이 있다.

 

리스트를 이용한 스택 구현

 

class stack:
    def __init__(self):  # 스택 객체 생성
        self.items = []

    def push(self, item):  # 스택 요소 추가 push(.append())
        self.items.append(item)

    def pop(self):  # 스택 맨 뒤 요소 삭제하고 리턴 pop()
        return self.items.pop()

    def peek(self):  # 스택 맨 뒤 요소 리턴
        return self.items[-1]

    def isEmpty(self):  # 스택이 비었는지 확인(비었으면 True 리턴)
        return not self.items