스택(Stack)

LIFO(Last In First Out) 자료구조

 

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

 

• 먼저 들어간 데이터가 나중에 뽑혀 나오게 저장되는 자료구조.
• 우리가 이사를 할 때 짐을 싸게 되는데 박스안에 이삿짐을 차곡차곡 쌓아 저장하고 꺼낼때 나중에 넣어서 위에 저장된 짐을 뺴는 것과 같은 형태를 생각하면 이해하기 편하다.
• 재귀, 시스템 콜, 히스토리를 쌓아 나갈때(ex 인터넷 뒤로가기, 프로그램의 Ctrl+Z) 등에 사용된다.

 

시간복잡도

• 삽입 : O(1)
• 삭제 : O(1)
• 조회 : O(n)

 

공간복잡도

• O(N)

 

Java에서의 사용법

선언

Queue<T> stack = new Stack<>();

 

삽입

stack.push(items);

 

삭제

stack.pop(); // 데이터가 없는 상태에서 호출시 EmptyStackException

 

empty 체크

stack.empty() // Boolean 반환

 

가장 위(최근)의 값 확인

stack.peek() // 데이터가 없다면 EmptyStackException

 

데이터 위치 확인

stack.search(items) // top=1 기준으로 top과 떨어진 거리 반환, 존재하지 않는다면 -1 반환

 

Code

링크드리스트를 활용한 스택 구현

import java.io.*;
import java.util.*;

class Main {

  public static void main(String[] args) {
    StackWithLinkedList<Integer> stack = new StackWithLinkedList<>();
    stack.push(1);
    stack.push(2);
    System.out.println(stack.pop());
    stack.push(3);
    System.out.println(stack.pop());
    stack.printDatas();
  }

}

class Node<T> {
  private T data;
  Node<T> next;

  public Node(T data) {
    this.data = data;
    this.next = null;
  }

  public T get() {
    return data;
  }

}

class StackWithLinkedList<T> {

  private Node<T> top;
  private int size;

  public StackWithLinkedList() {
    this.top = null;
  }

  public void push(T data) {
    Node<T> node = new Node<>(data);
    if (size == 0) {
      node.next = null;
    } else {
      node.next = top;
    }
    top = node;
    size++;
  }

  public T peek() {
  	if (size == 0) {
    	return null;
    }
    return top.get();
  }

  public T pop() {
    if (size <= 0) {
      throw new IndexOutOfBoundsException();
    }
    Node<T> topNode = top;
    top = topNode.next;
    size--;
    T returnData = topNode.get();
    topNode.next = null;
    return returnData;
  }

  public void printDatas() {
    List<T> elements = new ArrayList<>();
    Node<T> topNode = top;
    while (topNode.next != null) {
      elements.add(topNode.get());
      topNode = topNode.next;
    }
    elements.add(topNode.get());
    Collections.reverse(elements);
    System.out.println(elements);
  }
}

 

ArrayList를 활용한 스택 구현

import java.io.*;
import java.util.*;

class Main {

  public static void main(String[] args) {
    StackWithArrayList<Integer> stack = new StackWithArrayList<>();
    stack.push(1);
    stack.push(2);
    stack.push(3);

    stack.printDatas();

    stack.pop();
    stack.pop();
    stack.pop();
    stack.printDatas();

    System.out.println(stack.peek());
  }

}


class StackWithArrayList<T> {

  private int size;
  private List<T> datas;

  public StackWithArrayList() {
    this.datas = new ArrayList<>();
    this.size = 0;  
  }

  public void push(T data) {
    datas.add(data);
    size++;
  }

  public T peek() {
    if (size == 0) {
      return null;
    }
    return datas.get(size-1);
  }

  public T pop() {
    if (size == 0) {
      throw new IndexOutOfBoundsException();
    }
    T returnData = datas.get(size - 1);
    datas.remove(size - 1);
    size--;
    return returnData;
  }

  public void printDatas() {
    System.out.println(datas);
  }
}