[자료구조] 스택(Stack)

 

목차

스택(Stack)의 개념

스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out), 즉 후입 선출 형식의 자료 구조이다. 따라서 스택에서는 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되는 구조를 가지고 있다. 스택은 완전히 꽉 찼을 때 Overflow 상태라고 하며 완전히 비어 있으면 Underflow 상태라고 한다.

 

 

스택(Stack)의 연산

스택은 LIFO(Last In First Out)를 따른다. 즉, 가장 최근에 스택에 추가한 데이터가 가장 먼저 제거된다.

 

pop(): 스택에서 가장 위에 있는 항목을 제거한다.

push(data): data 하나를 스택의 가장 윗부분에 추가한다.

peek(): 스택의 가장 위에 있는 항목을 반환한다.

isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

 

스택(Stack)의 구현

스택은 보통 연결 리스트(LinkedList)로 구현한다. 문제의 종류에 따라 배열보다 스택에 데이터를 저장하는 것이 더 좋은 방법일 수 있다.

• 배열과 달리 스택은 상수 시간에 i번째 항목에 접근할 수 없다.
• 하지만 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다.
• 배열처럼 원소들을 하나씩 옆으로 밀어 줄 필요가 없다.

 

스택(Stack) 사용법

Stack 선언

import java.util.Stack; //import
Stack<Integer> stack = new Stack<>(); //int형 스택 선언
Stack<String> stack = new Stack<>(); //char형 스택 선언

자바에서 stack을 선언하려면 import java.util.Stack을 import 한 뒤 Stack <Element> stack = new Stack <>();과 같은 형식으로 선언하면 된다.

 

 

Stack 값 추가

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.push(3);     // stack에 값 3 추가

 

 

Stack 값 삭제

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.push(3);     // stack에 값 3 추가
stack.pop();       // stack에 값 제거
stack.clear();     // stack의 전체 값 제거 (초기화)

 

 

Stack의 가장 상단의 값 출력

 

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.push(3);     // stack에 값 3 추가
stack.peek();     // stack의 가장 상단의 값 출력

 

Stack의 기타 메서드

 

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.size();      // stack의 크기 출력 : 2
stack.empty();     // stack이 비어있는제 check (비어있다면 true)
stack.contains(1) // stack에 1이 있는지 check (있다면 true)

 

 

시간 복잡도 (Time complexity)

Operation	Average	Worst
Access	O(n)	O(n)
Search	O(n)	O(n)
Insert (push)	O(1)	O(1)
Delete (pop)	O(1)	O(1)