[ 스택이란? ]
스택이라는 의미는 쌓다 , 더미 라는 의미를 가진 단어 입니다.
접시를 차곡차곡 쌓아 올리듯 데이터를 쌓아 올리는 것을 생각하면 쉽습니다.
쉽게 생각해 우리가 어떠한 상자에 책을 차곡차곡 담습니다.
그리고 나중에 이 책을 다시 꺼낼려고 할때 어떻게 꺼내나요?
제일 위에 있는 책을 꺼내고 그다음 밑에 있는 책을 꺼내고
제일 위에 있는 책부터 하나하나씩 꺼내게 됩니다.
이것이 바로 스택이 원리이며
Quque와 더불어 자바의 기본적인 자료구조 입니다.
[스택의 특징]
스택의 특징으로는 마지막의 추가된 데이터가 가장 먼저 나오는 특징을 가지고 있습니다.
이렇듯 데이터가 있으면 1 -> 2 - > 3 이런씩으로 순서대로 들어갑니다.
들어가는 방법은 일반적인 배열과 같습니다.
그럼 이런 의문이 들 것 입니다.
스택에 인덱스는 어떻게 매기는 것인지 햇갈릴 수 있습니다.
만약 1 - > 2 - > 3의 값이 들어오면 3을 인덱스 0부터 하는 것인지?
아니면 1을 인덱스 0부터 하는 것인지?
햇갈릴 수 있는데 무조건 배열이랑 똑같습니다.
무조건 제일 먼저 들어온 값이 인덱스 0번입니다.
즉 1의 값이 제일 먼저 들어왔기 때문에 인덱스 0번
2의 값은 인덱스 1번
3의 값은 인덱스 2번 입니다.
쉽게 생각해서 배열이랑 똑같은 인덱스 방식을 가집니다.
들어갈 때는 1 -> 2 -> 3 의 데이터로 들어가게 되지만
나올때는 3 -> 2 -> 1로 꺼낼 수 있게 됩니다.
즉 넣을 때와 반대로 꺼낼 수 있는 것이 스택이며
이것을 LIFO 방식이라 합니다.
Last In First Out
즉 직역한다면 가장 늦게 들어온 값을 제일 먼저 뺀다.
[스택의 구현]
일단 자바에서 스택은 기본적으로 다 구현이 되어있지만
쓰기 전에 간단하게 자바로 구현해보도록 합시다.
package com.algorithm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static int top = -1;
static int [] array = new int[10];
public static void main(String[] args) throws IOException {
push(1);
push(2);
push(3);
System.out.println(pop());
System.out.println(pop());
}
static void push(int item){
if(is_full()){
System.out.println("스택이 비었습니다. 에러");
return;
}else {
array[++top] = item;
}
}
static int pop(){
if(is_empty()){
System.out.println("스택이 가득 찼습니다.");
System.exit(1);
}
return array[top--];
}
static boolean is_full(){
return (top == array.length-1);
}
static int peek(){
if(is_empty()) {
System.out.println("스택이 비었습니다.");
System.exit(1);
}
return array[top];
}
static boolean is_empty(){
return (top == -1);
}
}
간단하게 배열로 구현해봤는데 이정도 구현은 한번 해보는 걸 추천 합니다.
어렵지 않기 떄문이죠.
[스택의 사용 방법]
일단은 스택의 값을 넣는 것을 Push라고 하며
값을 뺄떄는 Pop이라고 합니다.
당연 Pop메서드를 실행시 가장 늦게 들어간 데이터가 빠지게 됩니다.
자바는 java.util.Stack의 클래스를 통해 Stack을 제공하고 있습니다.
이러한 스택은 코팅 테스트를 활용할때 많이 사용되는 자료구조 중 하나 입니다.
일단 스택을 사용하기 전에 어떠한 메서드가 있는지 알아보도록 합시다.
[스택의 메서드]
Stack<Integer> stack = new Stack<>();
스택의 생성방법입니다. 스택은 인터페이스가 아닌 클래스로 제공 되기 때문에 일반 클래스처럼 생성 하면 됩니다.
stack.push()
스택의 값을 넣을 때 사용되는 메서드 입니다.
stack.peek()
peek은 엿보다 라는 뜻임으로 데이터의 값들을 엿보는 메서드 입니다.
기본적으로 peek을 사용 할 시 데이터를 배열처럼 마음대로 볼 수 있는 것이 아닌
스택에 쌓여있는 맨위에 메서드만 볼 수 있습니다.
즉 스택에 있는 인덱스의 값을 맨위만 볼 수 있으며 다른 인덱스의 값들은 볼 수 없습니다.
stack.pop()
스택의 값들을 뺄 수 있는 메서드 입니다.
기본적으로 pop메서드를 사용한다면 스택에 맨위에 있는 값 부터 순차적으로 빠지게 됩니다.
주의 해야 할 점이 있는데 pop의 메서드를 사용하면 그 해당 값들을 출력하고 그 값을 삭제 해버립니다.
값을 뺌과 동시에 값이 삭제 됨으로 삭제 메서드와 동일한 메서드입니다.
즉 3번의 데이터를 꺼내면 이 데이터의 값은 삭제가 되고 1번 데이터와 2번 데이터만이 존재 하게 됩니다.
stack.search();
search 인자 값에는 인덱스 값이 들어가는 것이 아닌 오브젝트 형이 들어갑니다.
만약 스택에 111 , 222 , 333 가 들어있다고 치면
serach(111)를 할 시 이 111의 값이 스택의 맨 꼭대기에 있다면 1을 반환하고
이 값이 꼭대기에 있지 않다면 스택의 위치 하나씩 내려가면서 +1을 해줍니다.
333 (1)
222 (2)
111 (3) 이렇게 스택에 값들이 존재한다면 찾는 값이 맨 꼭대기에 있다면 1
찾는 값이 맨 꼭대기에 없다면 +1을 증가하면서 찾습니다.
이 값이 있다면 위치의 값 = 3을 출력할 것이고 없다면 -1을 출력합니다.
즉 예시로 보자면 이렇습니다.
push로 11 , 22 , 33 을 넣는다면
인덱스 0번 = 11
인덱스 1번 = 22
인덱스 2번 = 33
이 들어갑니다.
하지만 search(33)을 하면 값이 3이 반환 됩니다.
즉 search()메서드는 인덱스 값을 찾아주는게 아니고 이 33이란 값이 "몇번 째" 위치하는지 알려주는 메서드입니다. 33은 3번째로 들어갔기 때문에 3을 반환 합니다.
다시 한번 얘기하지만 search()는 인덱스 번호 값을 반환 하는게 아닌 이 값이 몇번째 위치하는지 알려주는 메서드 입니다. 즉 이 search()메서드는 첫번째는 반드시 1번째 부터 시작합니다.
stack.empty()
stack이 비어있는지 확인하는 메서드 입니다.
반복문에서 주로 사용되는 메서드 입니다.
stack.set(index,value);
1번째 인자 값에 인덱스번호 , 2번째 인자 값에 값을 넣습니다.
이 메서드는 n번째 인덱스에 있는 값을 변경 시켜주는 역활을 합니다.
즉 set(2,10)을 한다면 Stack안에 있는 2번째 인덱스에 있는 값을 10으로 바꾸라는 의미입니다.
stack.elementAt(index);
인덱스 번호 입력시 그 인덱스 번호안에 있는 값들을 가져옵니다.
예를 들어 stack에 [1,2,3]이 있다고 한다면
elementAt(2)를 한다면 인덱스 번호 2번인 3의 값을 반환 합니다.
stack.stream()
stack의 스트림입니다. 기본적으로 Collections의 stream람다와 형식이 거의 같습니다.
스트림 람다를 사용 할 줄 안다면 구조는 똑같습니다.
package com.algorithm;
import java.util.*;
import java.io.*;
public class Main{
public static void main(String args[])throws IOException{
Stack stack = new Stack(); // 스택 생성
stack.push("Hello"); // 스택 1번
stack.push("World"); // 스택 2번
stack.push("good"); // 스택 3번
while (!stack.empty()){
System.out.println(stack.pop());
}
System.out.println(stack.search(1)); // 1번의 스택에 있는 값들을 가져옴 하지만 pop을 하는 순간
//값이 없어지기 떄문에 -1를 출력하게 됨.
}
}
간단하게 스택의 코드를 보자면 이렇습니다.
push로 값을 넣고
값을 출력하고
search()를 통해 값을 확인하는 메서드 입니다.
결과를 본다면 맨위에 있는 값 good -> World -> Hello 부터 빠지게 됐습니다.
또한 위에서 설명 드렸다 싶이 pop의 메서드 경우 스택에서 값을 빼면
이 데이터는 사라집니다.
그렇기 때문에 search() 메서드로 값들을 확인해봐도
값들이 다 사라졌기 때문에 -1을 반환 한 것 입니다.
public static void main(String args[])throws IOException{
Stack stack = new Stack(); // 스택 생성
stack.push("Hello"); // 스택 1번
stack.push("World"); // 스택 2번
stack.push("good"); // 스택 3번
Optional hello = stack.stream().filter(result -> result.equals("Hello")).findAny();
System.out.println(hello);
}
스트림 람다 사용방법입니다.
기본적으로 다른 자료구조 스트림 람다와 똑같기 때문에 똑같이 사용하면 됩니다.