스택(Stack)

스택(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 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 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 { private T data; Node next; public Node(T data) { this.data = data; this.next = null; } public T get() { return data; } } class StackWithLinkedList { private Node top; private int size; public StackWithLinkedList() { this.top = null; } public void push(T data) { Node 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() { T returnData; if (size <= 0) { throw new IndexOutOfBoundsException(); } Node topNode = top; top = topNode.next; size--; returnData = topNode.get(); topNode.next = null; return returnData; } public void printDatas() { List elements = new ArrayList<>(); Node 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 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 { private int size; private List 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); } }

from http://epser.tistory.com/31 by ccl(A) rewrite - 2021-12-21 20:27:25