[자료구조] 스택 (Stack)

🚩스택 (Stack)의 개념

한 쪽  끝에서만 자료를 넣고 뺄 수 있는 LIFO (Last In First Out) 형식의 자료 구조

 

 

 

❓스택 (Stack)의 특징

1. 먼저 들어간 자료가 나중에 나옴. LIFO구조

2. 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함

3. 인터럽트 처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임

4. 그래프의 깊이 우선 탐색 (DFS)에서 사용

5. 재귀적(Recursion) 함수를 호출할 때 사용

 

 

 

💻스택 (Stack)의 연산

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

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

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

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

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

 

 

 

💡스택 (Stack)의 구현

문제의 종류에 따라 배열보다 스택에 데이터를 저장하는 것이 더 적합한 방법일 수 있다.

 

- 배열과 달리 스택은 상수 시간에 i번째 항목에 접근할 수 없다.

- 하지만 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다,

- 배열처럼 원소들을 하나씩 옆으로 밀어 줄 필요가 없다.

 

 

 

🔎Stack 사용법

Stack 선언

import java.util.Stack; //import

public class MyStack {
	Stack<Integer> stack = new Stack<>(); //int형 스택 선언
	Stack<String> stack1 = new Stack<>(); //char형 스택 선언
}

import java.util.Stack; 선언 뒤

Stack<Element> stack = new Stack<>(); 과 같은 형식으로 선언하면 된다.

 

 

 

 

Stack 값 추가

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

스택 출력 값

 

Stack에 값을 추가하고 싶다면 push(value)라는 메소드를 활용하면 된다.

Stack에 위의 예제와 같이 값을 계속해서 추가해나간다면 아래 그림처럼 데이터가 쌓이게 된다.

 

 

 

Stack 값 삭제

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop(); // stack에 맨 위 값 제거

스택의 출력값

 

스택에서 값을 제거하고 싶다면 pop() 이라는 메서드를 사용하면 된다.

pop을 하면 가장 위쪽에 있는 원소의 값이 아래 그림과 같이 제거된다.

스택의 값을 모두 제거하고 싶다면 clear()라는 메서드를 사용하면 된다.

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

스택의 출력값

 

 

 

 

Stack의 가장 상단의 값 출력

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

stack.peek()의 출력값

 

스택의 가장 위에 있는 값을 출력하고 싶다면 peek()라는 함수를 사용하면 된다.

가장 마지막에 들어간 값이 출력된다.

 

 

 

 

Stack의 기타 메서드

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

기타 메서드 출력값

 

그 밖에도 stack에는 크기를 구하는 size()메서드와 

stack이 비어있는지 확인하는 empty() 메서드(비어있다면 true, 값이 있다면 false를 return)

stack의 값을 search하는 contains(int value)함수가 있습니다.

 

 

 

 

 

스택 (Stack)의 사용 사례

재귀 알고리즘을 사용하는 경우 스택이 유용하다.

 

• 재귀 알고리즘
  • 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
  • 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼줘야한다.
  • 스택은 이런 일련의 행위를 직관적으로 가능하게 해준다.
  • 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
• 웹 브라우저 방문기록 (뒤로가기)
• 실행 취소 (undo)
• 역순 문자열 만들기
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
  • Ex) 올바른 괄호 문자열 (VPS, Vaild Parenthesis String) 판단하기
• 후위 표기법 계산

 

---

참고

https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html

[자료구조] 스택(Stack)이란 - Heee's Development Blog

https://coding-factory.tistory.com/601

[Java] 자바 Stack 클래스 사용법 & 예제 총정리