- Stack
- Queue
1. Stack
스택은 데이터를 저장하는 선형 자료구조로, 데이터를 쌓아 올리는 형태의 특징을 가지고 있습니다. 이를테면, 접시를 쌓는 것처럼 가장 위에 추가된 데이터가 가장 먼저 제거되어야 하는 구조입니다.이러한 특성 때문에 스택은 'Last-In,First-Out'(LIFO)라고도 불립니다.
1-2. 활용사례
- 재귀 알고리즘
재귀적으로 함수를 호출할 때 스택을 사용하여 함수 호출의 순서와 관련된 정보를 관리합니다. - 후위 표기법 계산
수식을 후위 표기법으로 변환하고, 이를 스택을 이용하여 계산합니다. - 웹 브라이저의 뒤로가기
방문한 웹 페이지를 스택에 저장하여 뒤로가기 기능을 구현합니다. - 함수의 호출 스택
프로그램에서 함수 호출과 복귀 주소 등을 스택에 저장하여 함수의 호출과 제어 흐름을 관리합니다.
1-3. 연산
pop(): 스택에서 가장 위에 있는 항목을 제거한다.
push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
peek(): 스택의 가장 위에 있는 항목을 반환한다.
isEmpty(): 스택이 비어 있을 때에 true를 반환한다.
1-4. Java 라이브러리 Stack 관련 메서드
- push(E item)
- 해당 item을 Stack의 top에 삽입
- Vector의 addElement(item)과 동일
- pop()
- Stack의 top에 있는 item을 삭제하고 해당 item을 반환
- peek()
- Stack의 top에 있는 item을 삭제하지않고 해당 item을 반환
- empty()
- Stack이 비어있으면 true를 반환 그렇지않으면 false를 반환
- search(Object o)
- 해당 Object의 위치를 반환
1-5. 구현
MyStack
package com.example.datastructure.Stack;
import com.example.datastructure.List.MyLinkedList;
public class MyStack<T> implements IStack<T>{
private int size;
private Node head;
public MyStack() {
this.size = size();
this.head = new Node(null);
}
@Override
public void push(T data) {
Node node = new Node(data, this.head.next);
this.head.next = node;
this.size++;
}
// 하나 가져오기
@Override
public T pop() {
if(this.isEmpty()){
return null;
}
Node curr = this.head.next;
this.head.next = curr.next;
curr.next = null;
this.size--;
return curr.data;
}
// 데이터 확인
@Override
public T peek() {
if(this.isEmpty()){
return null;
}
return this.head.next.data;
}
private boolean isEmpty() {
return this.head.next == null;
}
@Override
public int size() {
return this.size;
}
private class Node{
T data;
Node next;
Node(T data){
this.data = data;
}
Node(T data, Node next){
this.data = data;
this.next = next;
}
}
}
1-6. 관련 알고리즘 문제
백준 9012. 괄호
package com.example.datastructure.Stack;
import java.util.Scanner;
import java.util.Stack;
public class Baekjoon_9012 {
public static void logic(String s){
Stack<Character> stack = new Stack<>();
int i = 0;
while(i < s.length()){
char c = s.charAt(i);
if(c == '('){
stack.push(c);
}else{
if(stack.size() < 1)
{
System.out.println("NO");
return;
}
stack.pop();
}
i++;
}
if(stack.size() > 0){
System.out.println("NO");
}else{
System.out.println("YES");
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
for(int i = 0; i < num; i++){
logic(sc.next());
}
}
}
2. Queue
스택과 마찬가지로 큐(Queue)도 데이터를 저장하는 선형 자료구조입니다. 하지만 스택과는 다르게 큐는 데이터를 '선입선출(First-In, First-Out, FIFO)' 방식으로 관리합니다. 큐는 일상 생활에서 줄을 서는 것을 생각하면 이해하기 쉽습니다. 먼저 온 사람이 먼저 나가는 것과 마찬가지로, 큐에 들어온 데이터 중 가장 먼저 들어온 데이터가 먼저 처리되는 구조입니다.
1-2. 활용사례
- 탐색 알고리즘
너비 우선 탐색(Breadth-First Search, BFS)에서 큐를 이용하여 노드들을 순차적으로 방문합니다. - 작업 스케줄링
작업들을 순차적으로 처리하는 작업 스케줄러에서 큐를 사용하여 작업들을 관리합니다. - 버퍼(Buffer) 관리
데이터를 일시적으로 저장하기 위해 버퍼를 큐의 형태로 구현합니다. - 인터페이스 요청 처리
네트워크 통신이나 입출력 연산을 큐를 이용하여 비동기적으로 처리합니다.
1-3. 연산
Enqueue: 큐에 데이터를 추가하는 연산입니다. 이때 데이터는 큐의 뒤쪽에 추가됩니다.
Dequeue: 큐에서 가장 앞에 있는 데이터를 제거하고 반환하는 연산입니다.
1-4. Java 라이브러리 Queue 관련 메서드
- offer()
- 요소를 우선순위 큐에 추가합니다.
- add()
- 요소를 우선순위 큐에 추가합니다.
- peek()
- 우선순위 큐에서 가장 우선순위가 높은 요소를 반환합니다. 큐가 비어있을 경우 null을 반환합니다.
- poll()
- 우선순위 큐에서 가장 우선순위가 높은 요소를 제거하고 반환합니다. 큐가 비어있을 경우 null을 반환합니다.
1-5. 선형 큐(Linear Queue) 구현
- Node를 이용한 구현
MyLinkedQueue
package com.example.datastructure.Queue;
public class MyLinkedQueue<T> implements IQueue<T>{
private Node head;
public Node tail;
private int size;
public MyLinkedQueue(){
this.size = 0;
this.head = new Node(null);
this.tail = this.head;
}
@Override
public void offer(T data) {
Node node = new Node(data);
this.tail.next = node;
this.tail = this.tail.next;
this.size++;
}
@Override
public T poll() {
if(this.isEmpty()){
throw new IllegalStateException();
}
Node node = this.head.next;
this.head.next = node.next;
node.next = null;
this.size--;
if(this.head.next == null){
this.tail = this.head;
}
return node.data;
}
// 데이터를 빼지 않고 가장 앞에 있는 데이터를 가지고 나옴
@Override
public T peek() {
if(this.isEmpty()){
throw new IllegalStateException();
}
return this.head.data;
}
@Override
public int size() {
return this.size;
}
@Override
public void clear() {
this.head.next = null;
this.tail = this.tail.next;
this.size++;
}
@Override
public boolean isEmpty() {
return this.head.next == null;
}
private class Node{
T data;
Node next;
Node(T data){
this.data = data;
}
Node(T data, Node next){
this.data = data;
this.next = next;
}
}
}
1-6. 원형 큐(Circular Queue) 구현
- 배열을 이용한 구현
MyCircularQueue
package com.example.datastructure.Queue;
public class MyCircularQueue<T> implements IQueue<T>{
// 배열을 통해 구현
private T[] elements;
private int front;
private int rear;
private int maxSize;
public MyCircularQueue(int size){
this.elements = (T[]) new Object[size + 1];
this.front = 0;
this.rear = 0;
this.maxSize = size + 1;
}
@Override
public void offer(T data) {
if(this.isFull()){
throw new IllegalStateException();
}
this.rear = (this.rear + 1) % this.maxSize;
this.elements[this.rear] = data;
}
@Override
public T poll() {
if(this.isEmpty()){
throw new IllegalStateException();
}
this.front = (this.front + 1) % this.maxSize;
return this.elements[this.front];
}
@Override
public T peek() {
if(this.isEmpty()){
throw new IllegalStateException();
}
return this.elements[this.front + 1];
}
@Override
public int size() {
if(this.front <= this.rear){
return this.rear - this.front;
}
return this.maxSize - this.front + this.rear;
}
@Override
public void clear() {
this.front = 0;
this.rear = 0;
}
@Override
public boolean isEmpty() {
return this.front == this.rear;
}
private boolean isFull(){
return (this.rear + 1) % this.maxSize == this.front;
}
}
1-7. 관련 알고리즘 문제
백준 2164번. 카드2
package com.example.datastructure.Queue;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Baekjoon_2164 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < num; i++) // if 4
queue.add(i + 1); // 1, 2, 3, 4
int count = 1;
while(queue.size() != 1){
int q = queue.poll();
if(count % 2 == 0){
queue.offer(q);
}
count++;
}
System.out.println(queue.peek());
}
}
