[자료구조] 스택(Stack) 기본 개념과 구현

아는벌·2023년 2월 1일

자료구조

목록 보기

2/8

스택(Stack)

정의

한 쪽 긑에서만 item(항목)을 삭제하거나 새로운 item을 저장하는 자료구조
push : 새 item을 저장하는 연산
pop : Top item을 삭제하는 연산
후입선출(Last-in Frist-Out, LIFO)

응용

프로그램 실행 시 함수 구동을 위한 시스템 스택
미로 찾기
컴파일러의 괄호 짝 맞추기
회문 검사
문서 편집기의 undo
후위표기법(Postfix Notation) 수식 계산
중위표기법(Infix Notation) 수식의 후위표기법 변환
트리 방문
그래프의 깊이우선탐색

스택의 구현

배열로 구현한 스택

top은 정수로서 스택의 가장 위의 item이 저장된 배열 원소의 인덱스를 저장한다. 단, 스택이 empty인 경우 top = -1이다.

구현 소스코드

import java.util.EmptyStackException;

public class ArrayStack <E> {
    private E   s[];    // 스택을 위한 배열
    private int top;    // 스택의 top 항목의 배열 원소 인덱스
    public ArrayStack(){
        s = (E[]) new Object[1];    // 초기에 크기가 1인 배열 생성
        top = -1;
    }
    public int size()   {return (top+1);} //스택에 있는 항목의 수를 리텅
    public boolean isEmpty()   {return (top == -1);}    // 스택이 empty라면 true 출력

    // 배열의 크기 조절
    public void resize(int newSize){
        Object[] t = new Object[newSize];   // newSize 크기의 새로운 배열 생성
        for(int i = 0; i < size(); i++){
            t[i] = s[i];    // 배열 복사
        }
        s = (E[])t; // 배열 t를 a로
    }
    public E peek() {   // 스택 top의 내용만을 리턴
        if(isEmpty())   throw new EmptyStackException();    // 언더플로우 시 프로그램 정지
        return s[top];
    }
    // push 연산
    public void push(E newItem) {
        if (size() == s.length) resize(2*s.length); // 스택을 2배 크기로 확장
        s[++top] = newItem; // 새 항목을 push
    }
    //pop 연산
    public E pop() {
        if(isEmpty())   throw new EmptyStackException();    // 언더플로우 시 프로그램 정지
        E item = s[top];
        s[top--] = null;
        if(size() > 0 && size()==s.length/4){
            resize(s.length/2); // 스택을 1/2로 축소
        }
        return item;
    }
}

결과

    public static void main(String[] args){
        ArrayStack<String> stack = new ArrayStack<>();

        stack.push("apple");
        stack.push("banana");
        stack.push("cherry");
        stack.push("orange");	

        System.out.println("stack.peek() 현재 top은 -> "+stack.peek());
        System.out.println("stack.pop() "+stack.pop());
        System.out.println("stack.peek() 현재 top은 -> "+stack.peek());
        System.out.println("stack.pop() "+stack.pop());
        System.out.println("stack.peek() 현재 top은 -> "+stack.peek());
    }

처음 apple banana cherry orange를 push하여 스택의 top은 orange가 된다.
그 후 stack.pop()을 하면 top인 orange가 pop()되어 top은 cherry가 된다.

단순연결리스트로 구현한 스택

top은 스택의 가장 위에 있는 item을 참조하는 래퍼런스이고, 스택이 empty일 때 top = null이다.

구현 소스코드

import java.util.EmptyStackException;

public class ListStack <E>{
    private Node<E> top;    // 스택 top 항목을 가진 Node를 가리키기 위해
    private int size;   // 스택 항목의 수
    public ListStack(){
        top = null;
        size = 0;
    }
    public int size()   { return size; }
    public boolean isEmpty()    { return size == 0; }   // 스택이 empty이면 ture 리턴

    public E peek(){    // 스택 top 항목만을 리턴
        if (isEmpty())  throw new EmptyStackException(); // 언더플로우 시 프로그램 정지
        return top.getItem();
    }

    public void push(E newItem){
        Node newNode = new Node(newItem, top);   // 리스트 앞부분에 삽입
        top = newNode;  // top이 새 노드를 가리킴
        size ++;

    }
    public E pop() {
        if (isEmpty())  throw new EmptyStackException(); // 언더플로우 시 프로그램 정지
        E topItem = top.getItem();  // 스택 top 항목을 topItem에 저장
        top = top.getNext();    // top이 top 바로 아래 항목을 가리킴
        size--; // 스택 항목 수 감소
        return topItem;
    }
}