[Java][자료구조] Stack / 스택 - 배열, 리스트를 사용한 구현

스택

LIFO, Last-in, First-out 이 한마디로도 스택의 모든 것을 설명한다고 볼 수 있다. 삽입과 삭제가 한 방향에서만 이루어지는 자료구조로서 이해를 돕기 위해 현실의 예를 들어보자. 

 

우리가 옷 정리를 안해서 옷 위에 옷을 계속 올리는 구조.. 그것이 바로 스택이다.

 

새로운 옷을 위에 올리는 것, 이것이 Push() 이고 맨 위의 옷을 가져가 다시 입는 것, 이것이 Pop() 이다. 물론 이것은 자바의 컬렉션에서 기가 막히게 제공을 하지만 처음에는 이해를 위해 직접 구현해보도록 하자.

구현을 하기 위해서 배열과 리스트를 사용할 수 있다. 바로 코드를 보도록 하겠다.

 

코드

1. 배열을 이용해 구현한 스택

import java.util.NoSuchElementException;
 
public class Stack_arr <E> {
    private E a[];
    private int top;
    
    public Stack_arr() {
        a = (E[]) new Object[1];
        top = -1;
    }
    //동적인 배열을 만들기 위해 resize()함수를 만든다.
    public void resize(int length) {
        E b[] = (E[]) new Object[length];
        for(int i=0; i<top+1; i++) b[i] = a[i];
        a = b;
    }
    
    public void push(E item) {
        if(top+1 == a.length) resize(2*a.length);
        a[++top] = item;
    }
    
    public E pop() {
        if(isEmpty()) throw new NoSuchElementException();
        if(top == a.length/4) resize(a.length/2);
        E pop = a[top];
        a[top] = null;
        top = top-1;
        return pop;
    }
    
    public E peek() {
        if(isEmpty()) throw new NoSuchElementException();
        return a[top];
    }
    //배열에서는 맨 뒤가 top이 된다.
    public void show() {
        for(int i=0; i<=top; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.print("\t<--top");
        System.out.println();
    }
    
    public boolean isEmpty() {
        return top==-1;
    }
    
    public int getSize() {
        return top+1;
    }
}
 

2. 리스트를 이용해 구현한 스택

import java.util.EmptyStackException;
import java.util.NoSuchElementException;
 
public class Stack_linkedlist <E> {
    private Node top;
    private int size;
    //isEmpty(), getSize() 알아서
    public Stack_linkedlist() {
        top = null;
        size = 0;
    }
    
    public void push(E item) {
        top = new Node(item, top);
        size++;
    }
    
    public E pop() {
        if(isEmpty()) throw new EmptyStackException();
        E item = (E)top.getItem();
        top = top.getNext();
        size--;
        return item;
    }
    
    public E peek() {
        if(isEmpty()) throw new NoSuchElementException();
        return (E) top.getItem();
    }
    
    public void show() {
        System.out.print("top-->\t");
        Node a = top;
        while(a!=null) {
            System.out.print(a.getItem() + " ");
            a = a.getNext();
        }
        System.out.println();
    }
    
    public boolean isEmpty() {
        return size==0;
    }
    
    public int size() {
        return size;
    }
}
 
 
class Node <E> {
    private E item;
    private Node next;
    
    public Node(E item, Node next) {
        this.item = item;
        this.next = next;
    }
    
    public E getItem() {
        return item;
    }
 
    public void setItem(E item) {
        this.item = item;
    }
 
    public Node getNext() {
        return next;
    }
 
    public void setNext(Node next) {
        this.next = next;
    }
 
}