🍿 자료구조 개념 정리 (2) 스택, 큐, 덱, 해시테이블, 셋

[leemember]

🧑🏻‍🏫 자료구조

📍스택

• 먼저 들어간 데이터가 나중에 나오는 것이 규칙이다.

일상 생활에서 예를 들어보자면, 엘레베이터나 지하철 버스를 타고 내릴 때 늦게 들어간 사람이 먼저 나오게 되는 경우를 이 스택이라는 개념에 비유해볼 수 있다.

추상 자료형

먼저, 추상자료형은 기능의 구현 부분을 나타내지 않고 순수한 기능이 무엇인지 나열한 것을 추상 자료형이라고 한다.

스택의 추상 자료형

• push 데이터 삽입
• pop 데이터 제거
• peek 데이터 참조
• isEmpty 비었는지 체크

push로 하여금 스택에 데이터들이 쌓인다. 그리고 pop 함수로 인해 늦게 들어온 데이터가 먼저 나간다.

📍큐

• 먼저 들어간 데이터가 먼저 나오는 것이 규칙이다.
  스택과의 반대되는 개념이라고 보면된다.

일상 생활로 예를 들어보면, 마트에서 줄을 서서 계산할 때 먼저 온 손님을 먼저 계산하는 경우라고 보면 된다. 큐는 운영체제로의 예시로도 볼 수 있다. 운영체제에 먼저 들어온 프로세스를 먼저 처리해주는 것이다.

큐의 추상 자료형

• enqueue 데이터 삽입
• dequeue 데이터 제거
• front 데이터 참조
• isEmpty 비었는지 확인

데이터가 삽입, 삭제될 때 이전 노드를 새로 삽입한 노드로 설정한다. 그리고 head에 삽입하는 경우와 tail에 삽입하는 경우 그 외 위치에 삽입하는 경우의 코드로 구분하여 짠다.

📍덱

• 스택과 큐를 짬뽕 시킨 자유로운 자료구조이다.

덱의 추상 자료형

• printAll : 모든 데이터를 출력한다.
• addFirst : head에 데이터를 삽입한다.
• removeFirst : head에서 데이터를 제거한다.
• addLast : tail에 데이터를 삽입한다.
• removeLast : tail에서 데이터를 제거한다.
• isEmpty : 비었는지 확인

📍해시테이블

• 해시 테이블은 **해시와 테이블이 합쳐진 자료구조 (key와 value 값이라고 보면 됨)**이다. 만일 충돌이 발생한다면 인덱스들을 연결리스트로 중복된 값들 둘 다 저장을한다.

해시테이블의 추상 자료형

• set : key와 value에 데이터를 삽입한다.
• get : key와 value의 데이터를 읽어준다.
• remove : key와 value의 데이터를 제거한다.

해시테이블의 장점

• 빠른 데이터 읽기, 삽입, 삭제

단점

• 메모리를 많이 차지한다.
• 해시 함수에 따라 공간의 낭비가 극대화될 수도 있고 조금 덜할 수도 있다.
• 좋은 해시 함수의 구현은 필수다.

📍셋

• 데이터의 중복을 허용하지 않는 자료구조이다.
• 프로그래밍을 하다가 중복되지 않는 값을 저장하고 싶다면 셋을 이용하면 된다. 셋은 해시 테이블을 이용하기 때문에 쉽게 구현할 수 있다.
• key값만 사용하여 구현할 수 있다.

셋의 추상 자료형

• add(data) : key와 value에 데이터를 삽입한다.
• isContain(data) : 데이터 체크
• remove(data) : key와 value의 데이터를 제거한다.

위 괄호안에 data는 매개변수를 뜻한다.

• clear() : 셋을 비우기
• isEmpty() : 셋이 비었는지 체크
• printAll() : 모든 데이터 출력