[Data Structure/자료구조] Stack, Queue / 스택, 큐

sbj·2023년 12월 3일

datastructure 자료구조

Data Structure - 자료구조

목록 보기

4/5

Stack (스택)

들어온 시간 순으로 데이터를 쌓아갈 때, 가장 위 (가장 최근에 삽입)에 있는 데이터를 삭제하거나, 거기에 이어서 새로운 데이터를 삽입할 수 있도록 하는 추상 자료형.
LIFO (Last-In First-Out)

스택 구성도

한 방향으로만 PUSH와 POP을 이용하여 자료를 넣고 꺼낸다.
TOP 은 스택에서 가장 위에있는 데이터로, 스택 포인터(Stack Pointer)라고도 불린다.

스택 연산

스택에는 POP, PUSH가 있다.

연산	설명
push()	데이터를 차례대로 스택에 넣는 연산
pop()	스택의 가장 위에있는 데이터를 제거하고, 꺼내는 연산
peek()	스택의 가장 위에 있는 데이터를 제거하지 않고, 리턴하는 연산.

스택 응용분야

인터럽트 처리
- 현재 진행중인 명령어 위치를 스택에 PUSH하고, 인터럽트 발생 상황을 처리한 후에 인터럽트 전에 진행중이던 명령어 위치를 스택에서 POP을 통해 받아온다.
인터럽트가 발생하면 현재 실행중인 명령어 위치(주소)를 스택 PUSH에 저장한다. 그런 다음 인터럽트를 처리한다. 인터럽트 처리가 완료되면 스택에서 POP(제거 및 반환)을 사용한다. → 인터럽트가 발생하기 전에 실행중이던 명령어의 위치를 다시 가져온다. 이렇게 하면 원래의 작업을 계속 진행할 수 있다!
함수 호출 (재귀호출에 포함)
- 함수를 호출 시, 현재 진행중인 명령어 주소를 스택에 저장한다.
스택 함수호출은 프로그램이 함수를 사용할 때 어떻게 진행되는지 추적하는 방법이다. → 함수가 호출될 때, 그 함수가 시작한 지점의 “주소”가 스택에 저장된다. 특히 재귀호출에 중요한데, 프로그램이 어디서 멈추었는지 알 수 있게 해주기 때문이다. 함수가 모두 실행되고 종료되면, 스택에서 가장 최근에 저장된 주소를 찾아서 그곳으로 돌아간 다음, 프로그램의 실행을 계속 할 수 있는 것이다.
후위표현 연산
- Postfix를 계산할 때 사용한다.
후위표현식(Postfix): 연산자가 피연산자 뒤에 오는 표현식
스택을 사용하면 후위표현식을 효과적으로 사용할 수 있게 된다.
피연산자를 만날때마다 스택에 PUSH 하고, 연산자를 만나면 스택에서 피연산자를 POP하여 연산을 수행하고, 결과를 다시 스택에 PUSH한다. 이 과정을 표현식이 끝날 때 까지 반복하면 최종 결과가 스택의 맨 위에 남게된다!
깊이 우선 탐색 (DFS)
- 깊이 내려갈 때마다 스택에 값을 PUSH 하고, 더 이상 깊이 갈 곳이 없을 경우 스택에서 POP한 노드와 인접한 노드를 찾는다.
  
  깊이우선탐색(DFS) 알고리즘에서는 스택을 사용하여 노드를 탐색한다. 탐색을 시작할 때마다 스택에 값을 PUSH 하고, 더 이상 탐색할 곳이 없을 경우 스택에서 POP한 노드와 인접한 노드를 찾는다.
  ~~DFS 공부하고 다시 복기하기.~~
역순 문자열 만들기
웹 브라우저 방문기록(뒤로가기)
- 가장 나중에 열린 페이지부터 다시 보여준다.
오 신기하다.. 특정 페이지 방문할 때마다 그 정보가 스택에 쌓이고 → ‘뒤로가기’를 클릭하면 가장 최근에 방문한 페이지 정보가 스택에서 ‘POP’ 되어 이전 페이지를 보여주게 되는 것이다.
실행 취소(undo)
- 가장 나중에 실행된 것부터 실행을 취소한다.
수식의 괄호 검사
- 연산자 우선순위 표현을 위한 괄호 검사

Java Stack Basics

public class Main {
	public static void main(String[] args) {

		Stack stack = new Stack(); // create a stack
		Stack<String> stack2 = new Stack<String>(); // create a stack with a Generic type
		Stack<Integer> stack3 = new Stack<Integer>();

		stack2.push("Hi"); // push element on Stack

		for (int i = 0; i < 5; i++) {
			int a = i++;
			stack3.push(a);
		}
		System.out.println(stack3);
	}

}

[0, 2, 4]

~~왜 1, 3은 PUSH 되지 않는걸까? 아니 나 뭐한거지?..~~

0회차 반복에서 0 push & i는 1로 중가 → for문의 i++로 인해 i는 2회차로 넘어감

2회차 반복에서 2 push & i는 3으로 증가 → for문의 i++로 인해 i는 4회차로 넘어감

4회차 반복에서 4 push

~~다시 본론으로 돌아간다.~~

public class Main {
	public static void main(String[] args) {

		Stack stack = new Stack(); // create a stack
		Stack<String> stack2 = new Stack<String>(); // create a stack with a Generic type
		Stack<Integer> stack3 = new Stack<Integer>();

		stack2.push("Hi"); // push element on Stack

		for (int i = 0; i < 5;) {
			int a = ++i;
			stack3.push(a);
		}
		System.out.println(stack3);
		stack3.pop();
		System.out.println(stack3); // pop element from stack
		System.out.println(stack3.peek()); // peek at top element of stack
		stack3.search(3);
		System.out.println(stack3.search(3)); // index = 2
		System.out.println(stack3.size()); // size = 4

	}
}