스택 (STACK)이란?
📌 스택의 개념
스택(stack)이란 쌓아 올린다는 것을 의미한다.
따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.
📌 스택의 특징
스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고,
top으로 정한 곳을 통해서만 접근할 수 있다.
top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 스택에서 top을 통해 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'이라고 한다.
따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는
구조적 특징을 가지게 된다.
이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조이라고 한다.
그리고 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하며,
스택이 넘치는 경우 stack overflow라고 한다. (그 유명한 사이트 "stack overflow " 의 이름이 여기서 유래 된 것!)
더보기
📌 스택의 활용 예시
스택의 특징인 후입선출(LIFO)을 활용하여 여러 분야에서 활용 가능하다.
- 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
- 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
- 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
- 후위 표기법 계산
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
📌 스택 만들기(코드)
package chap05;
public class IntStack {
private int max; // 스택용량
private int ptr; // 스택 포인터
private int[] stk; // 스택본체
// 실행시 예외 : 스택이 비어있음
public class EmptyIntStackException extends RuntimeException {
public EmptyIntStackException() {
}
}
// 실행시 예외 : 스택이 가득 참
public class OverflowStackException extends RuntimeException {
public OverflowStackException() {
}
}
//생성자
public IntStack(int capacity) {
ptr = 0;// 생성 시 스택은 비어있으므로
max = capacity;
try {
stk = new int[max]; // 스택 본체용 배열 생성
} catch (OutOfMemoryError e) { // 생성할 수 없음
max = 0;
}
}
// 푸시 메서드 push
public int push(int x) throws OverflowStackException {
if (ptr >= max)
throw new OverflowStackException();
// 전달받은 데이터 x를 배열에 저장하고 스택포인터 증가
return stk[ptr++] = x;
}
// 팝 메서드 pop
public int pop() throws EmptyIntStackException {
if (ptr <= 0)
throw new EmptyIntStackException();
return stk[--ptr];
}
// 스택에서 데이터를 피크(정상에 있는 데이터를 들여다봄)
public int peek() throws EmptyIntStackException {
if (ptr <= 0)
throw new EmptyIntStackException();
return stk[ptr - 1];
}
// 검색메서드 IndexOf
// 스택에서 x를 찾아 인덱스를 반환
public int indexOf(int x) {
for (int i = ptr - 1; i >= 0; i--) {
if (stk[i] == x)
return i; // 검색 성공
}
return -1; // 검색 실패
}
// 스택을 비움
public void clear() {
ptr = 0;
}
// 스택의 용량을 반환
public int capacity() {
return max;
}
// 스택에 쌓여 있는 데이터 수를 반환
public int size() {
return ptr;
}
// 스택이 비어 있는가?
public boolean isEmpty() {
return ptr <= 0; // 비어있으면 true
}
// 스택이 가득 찼는가?
public boolean isFull() {
return ptr >= max; // 가득 차면 true
}
// 스택 안에 있는 모든 데이터를 바닥 -> 꼭대기 순서로 출력
public void dump() {
if (ptr <= 0)
System.out.println("스택이 비어있습니다.");
else {
for (int i = 0; i < ptr; i++)
System.out.println(stk[i] + " ");
System.out.println();
}
}
public static void main(String[] args) {
}
}
1. 생성자 IntStack
max = 스택용량
ptr = 스택 포인터
package chap05;
public class IntStack {
private int max; // 스택용량
private int ptr; // 스택 포인터
private int[] stk; // 스택본체
// 실행시 예외 : 스택이 비어있음
public class EmptyIntStackException extends RuntimeException {
public EmptyIntStackException() {
}
}
// 실행시 예외 : 스택이 가득 참
public class OverflowStackException extends RuntimeException {
public OverflowStackException() {
}
}
//생성자
public IntStack(int capacity) {
ptr = 0;//생성 시 스택은 비어있으므로
max = capacity;
try {
stk = new int[max]; //스택 본체용 배열 생성
} catch (OutOfMemoryError e) { //생성할 수 없음
max = 0;
}
}
public static void main(String[] args) {
}
}
2. 푸시메서드 push
전달받은 데이터 x를 배열에 저장하고 스택포인터 증가
스택이 가득 차있어서 푸시를 할 수 없다면 OverflowStackException 던진다.
// 푸시 메서드 push
public int push(int x) throws OverflowStackException {
if (ptr >= max)
throw new OverflowStackException();
// 전달받은 데이터 x를 배열에 저장하고 스택포인터 증가
return stk[ptr++] = x;
}
3. 팝 메서드 pop
스택의 꼭대기에서 데이터를 팝(제거)하고, 그 값을 반환
스택이 비어있어 팝을 할 수 없다면 EmptyIntStackException을 던진다.
// 팝 메서드 pop
public int pop() throws EmptyIntStackException {
if (ptr <= 0)
throw new EmptyIntStackException();
return stk[--ptr];
}
4.피크 메서드 peek
스택 꼭대기에 있는 데이터를 “몰래 엿보는” 메서드입니다.
비어있으면 EmptyIntStackException 던진다.
// 스택에서 데이터를 피크(정상에 있는 데이터를 들여다봄)
public int peek() throws EmptyIntStackException {
if (ptr <= 0)
throw new EmptyIntStackException();
return stk[ptr - 1];
}
비어있지 않으면 return stk[ptr - 1];
5. 검색메서드 IndexOf
스택 본체의 배열 stk에 x와 같은 값의 데이터가 포함되어 있는지, 포함도어 있다면 배열의 어디에 들어 있는지를 조사
// 검색메서드 IndexOf
// 스택에서 x를 찾아 인덱스를 반환
public int indexOf(int x) {
for (int i = ptr - 1; i >= 0; i--) {
if (stk[i] == x)
return i; // 검색 성공
}
return -1; // 검색 실패
}
6. 스택의 모든 요소를 삭제하는 메서드 clear
→ 스택에 쌓여 있는 모든 데이터를 삭제
// 6. 스택을 비움
public void clear() {
ptr = 0;
}
7. 용량을 확인하는 메서드 capacity
→ 용량의 값을 반환. max값을 그대로 반환
// 스택의 용량을 반환
public int capacity() {
return max;
}
8.데이터 수를 확인하는 메서드 size
현재 스택에 쌓여 있는 데이터 수(ptr의 값)을 반환
// 스택에 쌓여 있는 데이터 수를 반환
public int size() {
return ptr;
}
9. 스택이 비어 있는지 검사하는 메서드 IsEmpty
스택이 비어있으면 true dk아니면 false
// 스택이 비어 있는가?
public boolean isEmpty() {
return ptr <= 0; // 비어있으면 true
}
10. 스택이 가득 찼는지 검사하는 메서드 IsFull
// 스택이 가득 찼는가?
public boolean isFull() {
return ptr >= max; // 가득 차면 true
}
11. 스택 안에 있는 모든 데이터를 표시하는 메서드 dump
스택에 쌓여 있는 모든 데이터를 바닥에서 꼭대기 순으로 표시
// 스택 안에 있는 모든 데이터를 바닥 -> 꼭대기 순서로 출력
public void dump() {
if (ptr <= 0)
System.out.println("스택이 비어있습니다.");
else {
for (int i = 0; i < ptr; i++)
System.out.println(stk[i] + " ");
System.out.println();
}
}
📌 예제 코드
package chap05;
import java.util.Scanner;
public class InStackTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
IntStack s = new IntStack(64); // 최대 64개를 푸시할 수 있는 스택
while (true) {
System.out.println("현재 데이터 수 : " + s.size() + " / " + s.capacity());
System.out.println("(1)푸시 (2)팝 (3)피크 (4)덤프 (0)종료");
int menu = sc.nextInt();
if (menu == 0)
break;
int x;
switch (menu) {
case 1: // 푸시
System.out.println("데이터 : ");
x = sc.nextInt();
try {
s.push(x);
} catch (IntStack.OverflowStackException e) {
System.out.println("스택이 가득 찼습니다.");
}
break;
case 2: // 팝
try {
x = s.pop();
System.out.println("팝한 데이터 : " + x);
} catch (IntStack.EmptyIntStackException e) {
System.out.println("스택이 비어 있습니다.");
}
break;
case 3: // 피크
try {
x = s.peek();
System.out.println("피크한 데이터 : " + x);
} catch (IntStack.EmptyIntStackException e) {
System.out.println("스택이 비어 있습니다.");
}
break;
case 4: // 덤프
s.dump();
break;
}
}
sc.close();
}
}
📌 스택 문제 - 백준 10828 스택 자바
백준 10828 자바
스택
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 0.5 초 (추가 시간 없음) | 256 MB | 180414 | 62864 | 46043 | 37.248% |
문제
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
- push X: 정수 X를 스택에 넣는 연산이다.
- pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 스택에 들어있는 정수의 개수를 출력한다.
- empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
- top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
예제 입력 1
예제 출력 1
14
push 1
push 2
top
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
top
2
2
0
2
1
-1
0
1
-1
0
3
예제 입력 2
예제 출력 2
7
pop
top
push 123
top
pop
top
pop
-1
-1
123
123
-1
-1
방법1.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Stack {
private int max; // 스택 용량
private int ptr;// 스택 포인터
private int[] stk; // 스택본체
// 실행시 예외 : 스택이 비어있음
public class EmptyIntStackException extends RuntimeException {
public EmptyIntStackException() {
}
}
// 실행시 예외 : 스택이 가득 참
public class OverflowStackException extends RuntimeException {
public OverflowStackException() {
}
}
// 생성자
public Stack(int capacity) {
ptr = 0;// 생성 시 스택은 비어있으므로
max = capacity;
try {
stk = new int[max]; // 스택 본체용 배열 생성
} catch (OutOfMemoryError e) { // 생성할 수 없음
max = 0;
}
}
// push X: 정수 X를 스택에 넣는 연산이다.
public int push(int x) throws OverflowStackException {
if (ptr >= max)
throw new OverflowStackException();
// 전달받은 데이터 x를 배열에 저장하고 스택포인터 증가
return stk[ptr++] = x;
}
// pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다.
// 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
public int pop() throws EmptyIntStackException {
if (ptr <= 0)
return -1;
return stk[--ptr];
}
// size: 스택에 들어있는 정수의 개수를 출력한다.
public int size() {
return ptr;
}
// empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
public int empty() {
if (ptr <= 0)
return 1;
return 0;
}
// top: 스택의 가장 위에 있는 정수를 출력한다.
// 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
public int top() throws EmptyIntStackException {
if (ptr <= 0)
return -1;
return stk[ptr - 1];
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
Stack s = new Stack(N);
StringTokenizer st;
// 명령어 수만큼 반복.
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
// 출력해야하는 명령
String order = st.nextToken();
switch (order) {
case "push":
s.push(Integer.parseInt(st.nextToken()));
break;
case "pop":
sb.append(s.pop()).append("\\n");
break;
case "size":
sb.append(s.size()).append("\\n");
break;
case "empty":
sb.append(s.empty()).append("\\n");
break;
case "top":
sb.append(s.top()).append("\\n");
break;
}
}
System.out.println(sb);
}
}
근데 사실 오류 안던져도 된다.
package Day1109;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Stack {
private int max; // 스택 용량
private int ptr;// 스택 포인터
private int[] stk; // 스택본체
// 생성자
public Stack(int capacity) {
ptr = 0;// 생성 시 스택은 비어있으므로
max = capacity;
try {
stk = new int[max]; // 스택 본체용 배열 생성
} catch (OutOfMemoryError e) { // 생성할 수 없음
max = 0;
}
}
// push X: 정수 X를 스택에 넣는 연산이다.
public int push(int x) {
// 전달받은 데이터 x를 배열에 저장하고 스택포인터 증가
return stk[ptr++] = x;
}
// pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다.
// 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
public int pop() {
if (ptr <= 0)
return -1;
return stk[--ptr];
}
// size: 스택에 들어있는 정수의 개수를 출력한다.
public int size() {
return ptr;
}
// empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
public int empty() {
if (ptr <= 0)
return 1;
return 0;
}
// top: 스택의 가장 위에 있는 정수를 출력한다.
// 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
public int top() {
if (ptr <= 0)
return -1;
return stk[ptr - 1];
}
}
public class B10828_1 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
Stack s = new Stack(N);
StringTokenizer st;
// 명령어 수만큼 반복.
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
// 출력해야하는 명령
String order = st.nextToken();
switch (order) {
case "push":
s.push(Integer.parseInt(st.nextToken()));
break;
case "pop":
sb.append(s.pop()).append("\\n");
break;
case "size":
sb.append(s.size()).append("\\n");
break;
case "empty":
sb.append(s.empty()).append("\\n");
break;
case "top":
sb.append(s.top()).append("\\n");
break;
}
}
System.out.println(sb);
}
}
방법2 .Stack 클래스
package Day1109;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class B10828_2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
Stack<Integer> stack = new Stack<Integer>();
int N = Integer.parseInt(br.readLine());
StringTokenizer st;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
// 출력해야하는 명령
String order = st.nextToken();
switch (order) {
case "push":
stack.push(Integer.parseInt(st.nextToken()));
break;
case "pop":
sb.append(stack.isEmpty() ? -1 : stack.pop()).append("\\n");
break;
case "size":
sb.append(stack.size()).append("\\n");
break;
case "empty":
sb.append((stack.isEmpty() ? 1 : 0)).append("\\n");
break;
case "top":
sb.append(stack.isEmpty() ? -1 : stack.peek()).append("\\n");
break;
}
}
System.out.println(sb);
}
}
시간 차이는 안난다. 개인적으로 Stack클래스가 더 편한듯
코드가 절반으로 줄어드니..
'알고리즘 공부 > DoIt! 자료구조와 함께하는 알고리즘 입문' 카테고리의 다른 글
| 자바 큐란? - 큐 자바 구현 (QUEUE) (0) | 2022.11.10 |
|---|