자료구조와 알고리즘을 둘러보기 ✨ (3)

📌 스택과 큐

스택과 큐는 익히 알고 있기는 하지만 예시로 간단하게 기억하고 있었으므로..

Stack

선형 자료구조의 하나로, LIFO 라고 부르는 특성을 가지고 있는 자료구조.

** LIFO : Last-In First-Out 의 약자로 마지막으로 들어간 element 가 first out, 즉 처음으로 나오게 되는 구조

 

예) 책을 쌓아두었을 때, 팬케익을 쌓아두었을 때

 

abstraction 해서 표현

ABCD 라는 데이터를 입력 -> 입력된 순서는 ABCD 이지만 하나씩 제거한다고 하면 DCBA 순서로 나오게 되는 형태

따라서, 스택에서는 insertion 혹은 remove 할 때 스택의 최상단(탑) 에서만 이루어진다는 특징

용어

✅ top : 스택의 제일 상단

✅ push :  푸쉬 오퍼레이션, 어떤 아이템을 탑 위치에 추가

✅ pop : 스택의 최상단에서 하나의 아이템을 제거

 

Parenthesis Matching

이런 스택으로 우리는 어떤 문제를 풀 수 있을까 ?

-> 매칭되는 괄호를 하이라이팅 해주는 경우 스택을 이용해서 수행 가능

괄호들이 포함된 문자열을 입력으로 받았을 때, 하나씩 문자들을 보면서

해당 문자가 괄호를 여는 문자라면 그 여는 문자를 스택에 푸쉬

만약 지금 보고 있는 문자가 닫는 괄호 -> 스택에서 하나의 여는 괄호를 꺼내서 매칭

 

따라서, 하나씩 보면서 여는 괄호는 스택에 푸쉬 / 닫는 괄호는 스택의 최상단에서 하나 꺼내서 매칭

모든 문자열을 봤을 때 스택이 비어있을 경우 주어진 문자열은 괄호 차원에서 잘 밸런스가 되어있는 것

 

Queue

FIFO : First-in First-out 구조 , 스택과 반대 -> 먼저 들어간 데이터가 제일 먼저 나오는 자료 구조

 

ex) 줄 서기 : 먼저 줄 선 사람이 먼저 서비스를 받는 형태 / 웹서버 : 먼저 들어온 사람을 먼저 처리해주는 구조

 

insertion: rear or back or tail (큐의 뒤) 에서 발생

deletion : front 에서 발생

linear queue

 

용어

✅ front : 헤드, deletion 이 발생하는 곳

✅ rear, back, tail : insertion 이 발생하는 곳

✅ enqueue : 큐에 아이템을 rear 에서 insertion 하는 것

✅ dequeue : 데이터 삭제, front 에서 발생

 

ex) 비어있는 큐에 2 인큐, 7인큐 -> 디큐하게 되면 2가 밖으로 나옴

그리고 이 부분을 다시 읽다가, 문득 롤에서 5인큐 종종 하는데 설마 그 5인큐가 ,, ? 라는 생각을 했다.
실제로 검색해보니 프로그래밍 용어인 queue 라고 한다. 정말일까? 🤔

 

Linear queue 의 문제점

인큐디큐를 반복하다 보면 front 에 비해 앞서있는 rear 가 어레이의 끝을 가르키게 될 경우

큐 내에 공백이 있어도 더 이상의 데이터를 rear 에 추가할 수 없는 상황 발생

logical 하게 큐를 linear 가 아니라 끝을 동그랗게 붙인 사이클릭한 rear, front 인덱스를 통해

공간을 최대한 활용할 수 있는 형태 사용

 

Circular queue

어느 시점이 되어 rear 가 돌아서 마지막까지 갔을 경우, 다시 0 인덱스로 돌아오는 형태

나머지 연산자를 이용해서 rear 와 front 를 동그랗게 말린 형태로 구현 가능

 

=> 따라서, 실제 큐는 logical 하게는 선형 자료 구조이지만 실제로는 동그랗게 말아서 공간을

전체적으로 활용할 수 있는 형태로 구현한다.

 

예제

팰린드롬의 예 : radar, rotator, level 과 같은 단어는 앞에서부터 읽으나 뒤에서부터 읽으나 똑같이 읽어지는 단어들

펠린드롬 단어인지 체크하기 위해서 스택과 큐를 이용해보기

1. 주어진 문자열 str 에 있는 하나하나의 문자를 스택에 다 넣고
2. 큐에 다 넣은 후
3. 스택에서랑 큐에서 하나씩 팝 하면
4. 스택에서의 팝 아이템은 제일 끝 문자이고 큐에서의 팝 아이템은 제일 앞 문자이므로
5. 이 두 개의 문자가 같을 경우 펠린드롬 단어라고 판정