[알고리즘 자료구조] 스택(stack)/큐(queue)

1. 스택(Stack)

스택은 쌓다라는 의미로 후입선출법. (LIFO : Last In First Out)

즉 가장 마지막에 들어온 데이터가 가장 먼저 나간다.

제일 처음 쌓인 데이터는 제일 마지막에 나간다.

프링글스 통을 생각하면 이해하기 쉬울 것 같다. 입구가 위에 하나밖에 없는 형태.

 

 

시간복잡도

O(1)

 

 

장점

데이터 접근, 삽입, 삭제가 빠르다.

 

단점

top위치에 있는 자료만 접근할 수 있기 때문에 데이터를 탐색하려면 모든 데이터를 다시 꺼내서 다시 탐색해야 한다.

 

활용

재귀 알고리즘

DFS 알고리즘

괄호검사하기 (🔗지난번 풀었던 코테)

후위연산법

문자역 역순 출력

웹브라우저 방문기록실행취소(UNDO)

 

 

---

 

2. 큐(Queue)

큐는 선입선출법 (FIFO : First In First Out)

즉 가장 먼저 들어왔던 데이터가 나갈 때도 가장 먼저 나간다.

 

리어(rear)에서 이루어지는 삽입연산을 인큐(Enqueue),

프론트(front)에서 이루어지는 삭제연산을 디큐(Dequeue)라고 부른다.

 

시간복잡도

 O(1)

 

장점

데이터 접근, 삽입, 삭제가 빠르다.

 

단점

중간에 위치한 자료 탐색이 불가능하다.

 

활용

대기순서(은행업무, 서비스센터 대기 등)

프로세스 관리

BFS 알고리즘

 

 

 

 

---

 

 

참고링크 :

1.🔗

2.🔗