💻코딩테스트
[이코테_코딩테스트] 스택과 큐 자료구조
date
Jul 16, 2023
slug
coding-test-stack-queue
author
status
Public
tags
Python
코딩테스트
summary
스택과 큐 자료구조를 알아보자
type
Post
thumbnail
category
💻코딩테스트
updatedAt
Jul 16, 2023 06:08 PM
스택(Stack)
- 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
- 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F2bb9a5a5-f656-4bc1-86dc-8c5b24239cb4%2FUntitled.png?table=block&id=9cc0457c-3cc3-48eb-981d-9fc637d63aec&cache=v2)
스택 동작 예시
- 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
동작 | Data |
삽입(5) | 5 |
삽입(2) | 5 - 2 |
삽입(3) | 5 - 2 - 3 |
삽입(7) | 5 - 2 - 3 - 7 |
삭제 | 5 - 2 - 3 |
삽입(1) | 5 - 2 - 3 - 1 |
삽입(4) | 5 - 2 - 3 - 1 - 4 |
삭제() | 5 - 2 - 3 - 1 |
스택 구현 예제 (Python)
stack = [] stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack[::-1]) print(stack)
스택 구현 예제 (Java)
import java.util.*; public class Main { public static void main(String[] args) { Stack<Integer> s = new Stack<>(); // 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() s.push(5); s.push(2); s.push(3); s.push(7); s.pop(); s.push(1); s.push(4); s.pop(); // 스택의 최상단 원소부터 출력 while (!s.empty()) { System.out.println(s.peek()); s.pop(); } } }
큐(Queue)
- 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
- 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fd850ad2f-48a7-40f3-927e-02142fa095f7%2FUntitled.png?table=block&id=726fdcd5-1ba6-465a-abf6-4474a5dcd534&cache=v2)
큐 동작 예시
- 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
동작 | Data |
삽입(5) | 5 |
삽입(2) | 5 - 2 |
삽입(3) | 5 - 2 - 3 |
삽입(7) | 5 - 2 - 3 - 7 |
삭제 | 2 - 3 - 7 |
삽입(1) | 2 - 3 - 7 - 1 |
삽입(4) | 2 - 3 - 7 - 1 - 4 |
삭제() | 3 - 7 - 1 - 4 |
큐 구현 예제 (Python)
from collections import deque # 큐(Queue) 구현을 위해 deque 라이브러리 사용 queue = deque() # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() queue.append(5) queue.append(2) queue.append(3) queue.append(7) queue.popleft() queue.append(1) queue.append(4) queue.popleft() print(queue) # 먼저 들어온 순서대로 출력 queue.reverse() # 다음 출력을 위해 역순으로 바꾸기 print(queue) # 나중에 들어온 원소부터 출력
- 단순 리스트 자료형을 통해 큐(queue) 자료구조 구현이 가능하지만, 시간복잡도가 더 높아 비효율적일 수 있음
deque
통해 사용
큐 구현 예제 (Java)
import java.util.*; public class Main { public static void main(String[] args) { Queue<Integer> q = new LinkedList<>(); // 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() q.offer(5); q.offer(2); q.offer(3); q.offer(7); q.poll(); q.offer(1); q.offer(4); q.poll(); // 먼저 들어온 원소부터 추출 while (!q.isEmpty()) { System.out.println(q.poll()); } } }
이 글은 유튜브 “동빈나” 채널의 “(이코테 2021 강의 몰아보기) 3. DFS & BFS” 영상을 보고 작성하였습니다.