[자료구조와 알고리즘] 선형구조 - 스택, 큐, 데크, 링크드리스트 (2023.04.07)

🎈 스택(stack)

영어 뜻 : 쌓다

자료가 쌓아져 있음. 맨 아래에 있는 애들은 사용하기 어려움. 위에 있는 데이터부터 사용하는 구조

데이터를 일시적으로 쌓아 놓는 자료구조

가장 나중에 넣은 데이터를 가장 먼저 꺼냄 (후입선출 Last In First Out)

자바 프로그램에서 메서드를 호출하고 실행할 때 내부에서 사용

푸쉬(push)와 팝(pop)을 통해 데이터를 다룸

 

① 프로그램 시작 → main 메서드 push
    → main 메서드를 스택에 넣음 (main push)
② main안에서 z라는 메서드 호출(push)
    → z 메서드를 스택에 넣음
③ z 메서드 안에 x와 y 메서드 호출
    → x 호출(push) > 마무리(pop)
    → y 호출(push) > 마무리(pop)
④ z 팝 
⑤ main 팝

 

스택을 다룰 때 사용하는 명령어

① 푸쉬(push) : 구조에 값을 넣는다

② 팝(pop) : 맨 위 데이터를 꺼낸다. 

스택에서는 데이터가 top에서만 들어가고 나갈 수 있음

 

관련문제

정답 : ④번
① A, B, C push > C, B, A pop > D push > D pop > A , B, C push > C, B, A pop
② A, B push > B pop > C push > C pop > D push > D pop > A push > A pop
③ A, B, C push > C, B, A pop > D push > D pop
④ A, B, C, D push > D pop > 불가능

 

※ 스택 메서드에 vector와 컬렉션 메서드가 있는 이유

컬렉션은 모든 자료구조를 포함(조부모)

그 아래에 vector가 있음(부모)

그 아래에 stack이 있음

컬렉션이 가지고 있는 기능들을 하위의 부모(vector), 손자(stack)가 쓸 수 있음. 벡터가 가지고 있는 기능들을 하위의 stack이 쓸 수 있음 → 상속 / 부모 혹은 조부모가 가진 객체를 자식 객체가 쓸 수 있음. 대신 stack이 가진 기능은 부모, 조부모가 쓸 수 없음. 

 

 

⚙️ 스택의 활용

1. 웹 브라우저 뒤로가기(방문기록)

2. ctrl + z 

3. 역순 문자열 만들기

4. 후위 표기법 계산 

후위표기법
연산식. 컴퓨터가 계산하기 쉬운 형식, 괄호가 없고 연산자가 뒤에 있음
8 2 / 3 - 

일반적인 표기법 - 중위 표기법 (8 / 2 - 3)

 

5. 재귀적 알고리즘

재귀함수 - 자기 자신을 호출하는 함수

스택 오버플로우 : 자기자신을 너무 많이 호출하여 스택 메모리를 다 쓰는 경우

 

▼ 재귀함수 예시 ▼

 

⚙️ 스택 주요 메서드

 

🎈 큐

단어 의미 : 줄 서 있는 것 

제일 먼저 들어온 것이 먼저 나가는 자료 구조

가장 먼저 넣은 데이터를 가장 먼저 꺼냄 (선입선출, First In First Out)

Enqueue 데이터 들어가는거 

Dequeue 데이터 꺼내는거 / 앞쪽부터 데이터가 나감

스택은 bottom/top 수직구조인 반면 큐는 수평구조(앞/뒤)

 

Stack	Queue
부모가 vector - ArrayList → 연속된 공간 할당	LinkedList의 형식을 따서 만들어짐 → 공간이 연속적이지 않음 다음 데이터의 주소값(참조값)을 함께 저장하고 있어서 주소값을 가지고 다음 데이터를 찾을 수 있음 Dequeue를 하면 공간을 다른 곳에 쓸 수 있도록 함

 

 

 

⚙️ 큐의 활용

1. 통신(데이터 통신) ex.영상의 앞부분부터 데이터를 가지고 옴

2. 프린터 출력 : 가장 먼저 대기열에 오른 문서 먼저 출력

3. 운영체제의 테스크 스케줄링 : 선입선출 처리 스케줄링 정책 사용

 

⚙️ 큐 주요 메서드

 

🎈 데크

삽입과 삭제가 리스트 양쪽 끝에서 모두 발생할 수 있는 자료구조

스택과 큐가 합쳐진 구조

생긴건 큐와 비슷

큐는 뒤에서는 들어오기, 나가는건 앞에서만 가능

데크는 리스트 양쪽 끝에서 모두 삽입, 삭제 가능

가장 먼저 넣은 데이터가 빨리 나갈수도, 가장 늦게 나갈수도 있음

데크를 가지고 스택처럼 혹은 큐처럼 사용하는 경우가 많음 → 내가 규칙을 정할 수 있음

- 한쪽에서 삽입, 삭제 동시에 → 스택

- 한쪽에서 삽입, 한쪽에서 삭제 → 큐

데큐를 쓰는 이유: 시간이 더 빠르기 때문에 

 

⚙️ 데크 주요 메서드

 

🎈 링크드리스트

데이터가 연속된 위치에 저장되지 않고 모든 데이터가 데이터 부분과 다음 데이터의 주소 부분을 별도로 가지고 있는 구조

각 데이터는 노드라 부름

자주 삽입이나 삭제가 이루어지는 경우 사용(연속된 공간에서는 효율적이지 않음. 링크드 리스트는 끊어버리면 그만)

검색은 느림

 

⚙️ 링크드리스트 종류 

 

단일

단방향 구조 , 주소부가 1개 → 다음데이터의 주소만 가지고 있음 (절대 앞으로 다시 돌아갈 수 없음)

이전 노드에 접근하기 위해서는 첫번째 노드부터 다시 순회해야 함

이중

주소부가 2개 → 왼쪽에는 이전 데이터의 주소 오른쪽에는 이후 데이터의 주소

원형

단일 링크드리스트를 쓸 때 순회가 가능하도록(다시 1번으로 돌아갈 수 있음) 

마지막 노드가 첫번째 노드의 주소값을 가지고 있기 때문에 이전 노드에 접근할 수 있음

 

⚙️ 링크드리스트의 활용

1. 배열보다 메모리를 자유롭게 사용할 수 있음.

연속된 메모리를 가지는 구조는 메모리의 사용이 제한이 있음. 삽입 삭제가 빈번하게 되면 연속된 메모리를 사용하는 것은 비효율적

2. 삽입, 삭제가 빈번한 경우 사용