[자료구조] 스택(Stack)

스스로 공부하기

스택(Stack) 이란

사전적 의미로는 '쌓다', '더미'라는 뜻이 있습니다. 스택을 흔히 후입 선출(선출 후입), LIFO라고 부르는데 쉽게 설명하자면 아래가 막힌 어떤 물체를 생각하시면 됩니다. 쓰레기통, 마트용 음료수 진열대 등 이러한 것이 스택 구조입니다. 즉 한쪽 끝에서만 자료(데이터)를 넣고 뺄 수 있는 형식의 자료 구조입니다. 스택을 실제 개발환경에서 사용하는 경우는 인터넷 브라우저의 '뒤로 가기', '앞으로 가기' 버튼을 생각하시면 됩니다. 따라서 Stack은 데이터를 쌓는 형식으로 저장하는데 따라서 조회, 추가, 삭제 모두 가장 위에 있는 즉 가장 최근의 값에서 이루어진다. 스택 구조에서 가장 상단에 있는 데이터를 Top이라고 한다.

Stack의 특징

• LIFO (Last In First Out) 구조 : 먼저 들어간 자료가 나중에 나옴
• 스택에 데이터를 push하면 항상 top에 들어가고, pop하면 가장 최근에 푸시한 데이터가 나옴.
• 자료가 없을 때 pop하는 오류를 stack underflow, 스택의 크기 이상의 자료를 push 하려고 할 때의 오류를 stack overflow라고 함.
• 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함
• 인터럽트 처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임
• 재귀적(Recursion) 함수를 호출할 때 사용

사용하는 문제
-- 괄호 검사
-- 역순 문자열 만들기
-- 후위 표기법으로의 변환

 

스택(Stack) 사용법

Stack 생성

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

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

Stack 값 추가

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

tack에 값을 추가하고 싶다면 push(value)라는 메서드를 활용하면 됩니다. Stack에 위의 예제와 같이 값을 계속해서 추가해나간다면 아래 그림처럼 데이터가 쌓이게 됩니다.

 

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의 전체 값 제거 (초기화)

 스택에서 값을 제거하고 싶다면 pop()이라는 메서드를 사용하면 됩니다. pop을 하면 가장 위쪽에 있는 원소의 값이 아래 그림과 같이 제거됩니다. 스택의 값을 모두 제거하고싶다면 clear()라는 메서드를 사용하면 됩니다.

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의 가장 상단의 값 출력

스택의 가장 위에 있는 값을 출력하고 싶다면 peek()라는 함수를 사용하면 됩니다. 아래 그림과 같이 가장 마지막에 들어간 값이 출력됩니다.

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)

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

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

stack의 값을 search 하는 contains(int value) 메서드(값이 있다면 true, 그렇지 않다면 false를 return) 함수가 있습니다.

 

 

기본적인 메서드 구현

Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < 5; i++) {
            stack.push(i + 1);
            System.out.println(stack.peek());
        } // 1, 2, 3, 4, 5 가 현재 들어가 있음
        stack.pop(); // 1, 2, 3, 4
        System.out.println(stack.peek()); // 4
        System.out.println(stack.search(2)); // 3
        System.out.println(stack.empty()); // false

 

 

---

출처  
https://coding-factory.tistory.com/
https://velog.io/@choiiis
https://velog.io/@lshjh4848