[알고리즘] 스택 / 큐 / 환형 큐 / 연결 리스트

📍1. 스택(Stack)

데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다.

따라서 가장 마지막에 들어온 자료가 가장 먼저 삭제되는 구조이다.

스택은 정해진 방향으로만 쌓을 수 있어, top으로 정한 곳을 통해서만 접근할 수 있다.

 

- First In, Last Out 구조(후입선출)

 

 

👉 스택(Stack)이 사용되는 예시

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

- 실행취소(cmd + z)

 

 

💻  스택을 활용한 문제풀이 (Javascript)

https://www.acmicpc.net/problem/10828

 

이 문제는 시간초과 때문에 애를 먹었다..

[내 답안] 을 보면 console.log가 주석처리 되어 있는걸 볼 수 있는데,

이게 초기 코드였고 계속 시간초과가 발생했다.

 

그래서 출력할 답을 담을 배열인 result를 생성하고

for문을 모두 종류한 후에 result의 답을 console.log로 찍어서 시간초과를 해결했다.

 

 

[입력]

7
pop
top
push 123
top
pop
top
pop

 

[내 답안]

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n'); // 한 줄씩 입력 읽기
// input =['7', 'pop', 'top', 'push 123', 'top', 'pop', 'top', 'pop']

input.shift(); // 배열의 첫 번째 원소는 명령문이 아니므로 삭제한다.

let arr = []; // 스택
let result = []; // 출력할 답을 담을 배열

input.forEach((el) => {
    const [명령어, num] = el.trim().split(' ');
    if (명령어 === 'push') {
        arr.push(num);
    } else if (명령어 === 'top') {
        // arr.length !== 0 ? console.log(arr[arr.length - 1]) : console.log('-1');
        arr.length !== 0 ? result.push(arr[arr.length - 1]) : result.push('-1');
    } else if (명령어 === 'size') {
        // console.log(arr.length);
        result.push(arr.length);
    } else if (명령어 === 'empty') {
        // arr.length !== 0 ? console.log('0') : console.log('1');
        arr.length !== 0 ? result.push('0') : result.push('1');
    } else if (명령어 === 'pop') {
        // arr.length === 0 ? console.log(-1) : console.log(arr.pop());
        arr.length === 0 ? result.push(-1) : result.push(arr.pop());
    }
});

console.log(result.join('\n'));

 

 

 

📍 2. 큐 (Queue)

 

큐(Queue)는 스택(Stack)과 다르게 먼저 들어온 것이 먼저 나가는 "선입선출" 자료구조이다.

삭제 연산이 수행되는 프론트(front), 삽입 연산이 이루어지는 곳은 리어(rear)라고 한다.

 

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

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

 

- First In, First Out 구조(선입선출)

 

 

큐(Queue)가 사용되는 예시

- 카페에서 먼저 와서 주문한 손님이 음료를 먼저 받고 나가는 프로세스 등

 

 

 

 

📍3. 환형 큐(Circular Queues)

 

"원형 큐"라고도 한다.

앞서 애기한 큐(Queue)는 크기가 정해져 있지 않은 반면, 환형 큐(Circular Queue)는 크기가 고정된 큐이다.

둥근 환형으로 큐를 만들고, 큐의 원리대로 프론트(front)에서 삭제 연산인 디큐(Dequeue)를 리어(rear)에서 삽입 연산인 인큐(Enqueue)를 수행할 수 있다.

 

 

원형 큐는 크기가 고정되어있기 때문에,

큐가 가득 차면 더이상 원소를 넣을 수 없다,

 

 

 

 

환형 큐에 사용되는 개념

size() : 현재 큐에 들어 있는 데이터 원소의 수를 구함

isEmpty() : 현재 큐가 비어 있는지를 판단

isFull() : 큐에 데이터 원소가 꼭 차 있는지를 판단

qneueue(x) : 데이터 원소 x를 큐에 추가

dequeue() : 큐의 맨 앞에 저장된 데이터 원소를 제거(또한, 반환)

peek() : 큐의 맨 앞에 저장된 데이터 원소를 반환(제거하지 않음)

 

 

 

 

📍4. 연결리스트(Linked List)

데이터를 포인터로 연결한 구조이다.

데이터를 중간에 삽입하거나, 삭제하기에 편하다.

데이터의 삽입과 삭제가 빈번한 테이블에 주로 사용된다.

 

# 연결리스트의 종류

 

1. 단방향 연결 리스트

 

다음 노드를 가리키기 위한 포인터 필드 next만을 가지고 있다.

class Node { 
	Node next; // 다음 노드 주소를 저장하는 필드 
    int data; // 데이터를 저장하는 필드 
   };

 

 

 

2. 양방향 연결 리스트

 

다음 노드 + 이전 노드 2개의 포인터를 가지로 있다.

역순으로도 검색이 가능하기 때문에 단방향 연결 리스트에 비해 각 요소에 대한 접근과 이동이 비교적 쉽다

class Node {
    Node next; // 다음 노드 주소를 저장하는 필드
    Node prev; // 이전 노드 주소를 저장하는 필드
    int data; // 데이터를 저장하는 필드
};

 

 

 

3. 양방향 원형 연결 리스트

 

단순히 첫번째 노드와 마지막 노드를 각각 연결시켜, 마치 원형 리스트 처럼 만드는 것

이러한 구조는 티비 채널을 순회하거나 오디오 플레이어와 같이 데이터를 순차적 방식으로 처리하다 마지막 요소를 만나면 다시 처음 요소로 되돌아가는 애플리케이션에서 사용된다고 보면 된다.