💡 스택 (Stack)
한 쪽 끝에서만 원소를 넣고 뺄 수 있는 자료구조 : 후입선출 (LIFO)
- 원소의 추가 & 제거 & 상단의 원소 확인 :
O(1)→ 원칙적으로 상단의 원소를 제외한 나머지 원소를 확인할 수 없음
📒 구현
배열 혹은 연결 리스트를 사용하여 구현 가능
- dat[] : 스택을 구현할 배열
- pos : 상단 원소의 위치push(): 스택에 원소 추가
void push(int x) {
dat[pos++] = x;
}pop(): 스택에서 원소 제거
void pop() {
pos--;
}top(): 스택의 상단 원소 확인
int top() {
return dat[pos-1];
}📒 연습문제
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Stack<Integer> stack = new Stack<>();
int k = Integer.parseInt(br.readLine());
for(int i=0;i<k;i++) {
int num = Integer.parseInt(br.readLine());
if(num == 0) stack.pop();
else stack.push(num);
}
int sum = 0;
for (Integer i : stack) {
sum += i;
}
bw.write(sum + "");
bw.close();
}
}public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Stack<int[]> stack = new Stack<>();
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
for(int i=0;i<n;i++) {
int tmp = Integer.parseInt(st.nextToken());
while(!stack.isEmpty()) {
if(stack.peek()[0] < tmp) stack.pop();
else {
sb.append(stack.peek()[1] + " "); break;
}
}
if(stack.isEmpty()) sb.append("0 ");
stack.push(new int[] {tmp, i+1});
}
bw.write(sb + "");
bw.close();
}
}💡 큐 (Queue)
한 쪽 끝에서 원소를 넣고, 반대쪽 끝에서 원소를 뺄 수 있는 자료구조 : 선입선출 (FIFO)
- 원소의 추가 & 제거 & 앞 뒤 원소 확인 :
O(1)→ 앞/뒤가 아닌 나머지 원소들의 확인 및 변경은 원칙적으로 불가능
📒 구현
원형 배열을 사용한 구현
- dat[] : 큐를 구현할 배열
- head = 0 : 가장 앞 원소의 인덱스 (제거할 위치)
- tail = 0 : 가장 뒤 원소의 인덱스 + 1 (삽입할 위치)
- mx : 배열 크기
: 큐를 배열로 구현하게 되면 원소를 하나씩 꺼낼 때마다 head가 증가하는데, 이 때 head가 한 칸씩 밀리게 되면서 앞 공간에는 더이상 원소를 넣을 수 없게 된다.
: 이를 해결하기 위해, 원형 배열을 구현하여 head가 배열의 마지막 원소까지 도달한 경우 tail을 비어있던 앞 공간으로 이동시켜 데이터를 삽입할 수 있다. (입력 개수가 정해진 코딩 테스트의 경우, 벼열의 크기를 입력 개수보다 크게 선언하여 사용하면 선형 배열으로 사용 가능)
push(): 큐에 원소 삽입
void push(int x) {
if(tail == mx) tail = 0;
dat[tail++] = x;
}pop(): 큐의 원소 제거
void pop() {
if(head == mx) head = 0;
else head++;
}fornt()/back(): 큐의 가장 앞/뒤 원소 반환
int front() { return dat[head]; }
int back() { return dat[tail-1]; }📒 연습문제
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Queue<Integer> q = new LinkedList<>();
int n = Integer.parseInt(br.readLine());
for(int i=1;i<=n;i++) {
q.offer(i);
}
while(q.size() != 1) {
q.poll();
q.offer(q.poll());
}
bw.write(q.poll() + "");
bw.close();
}
}💡 덱 (Deque)
양쪽 끝에서 원소를 넣고 뺄 수 있는 자료구조
- 원소의 추가 & 제거 & 앞 뒤 원소 확인 :
O(1)→ 가장 앞/뒤가 아닌 나머지 원소들의 확인이 원칙적으로 불가능
📒 구현
배열이나 연결 리스트를 사용하여 구현
- mx : 배열의 크기
- dat[2*mx+1] : 덱을 구현할 배열
- head = mx / tail = mx 
: 덱에서는 양쪽에서 삽입과 제거가 이루어지기 때문에, head와 tail의 시작 지점을 mx로 두고, 배열의 크기를 2*mx+1로 두어 양쪽으로 확장 가능하게 설계해야 한다.
push_front/back(): 앞/뒤쪽에서 원소 삽입
void push_front(int x) { dat[--head] = x; }
vois push_back(int x) { dat[tail++] = x; }pop_front/back(): 앞/뒤쪽에서 원소 제거
void pop_front() { head++; }
void pop_back() { tail--; }front/back(): 앞/뒤 원소 반환
int front() { return dat[head]; }
int back() { return dat[tail-1]; }📒 연습문제
- 중간 인덱스를 기준으로 특정 원소의 인덱스가 작으면 2번 연산, 크면 3번 연산 수행 → 앞/뒤 원소가 아닌 중간 원소의 인덱스에 접근 하므로 연결 리스트를 사용하여 구현
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
LinkedList<Integer> deque = new LinkedList<>();
for(int i=1;i<=n;i++) {
deque.add(i);
}
int[] arr = new int[m];
st = new StringTokenizer(br.readLine());
for(int i=0;i<m;i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int cnt = 0;
for(int i=0;i<m;i++) {
int target = deque.indexOf(arr[i]);
int mid = 0;
if(deque.size() % 2 == 0) mid = deque.size() / 2 - 1;
else mid = deque.size() / 2;
if(target <= mid) {
for(int j=0;j<target;j++) {
deque.addLast(deque.pollFirst());
cnt++;
}
}
else {
for(int j=0;j<deque.size()-target;j++) {
deque.addFirst(deque.pollLast());
cnt++;
}
}
deque.pollFirst();
}
bw.write(cnt + "");
bw.close();
}
}🙇🏻♀️ 출처
백엔드 개발자👩🏻💻가 되고 싶다