[자료구조] Stack, Queue, List

자료구조의 선형/비선형

• 선형구조 : 자료 간의 관계가 1대 1의 관계 / 스택, 큐
• 비선형 구조 : 자료 간의 관계가 1대 N의 관계 / 트리, 그래프

1. Stack

가. 특성

• 물건을 쌓아 올리듯 자료를 쌓아올린 형태의 자료구조이다.
• 선형 구조이다. (자료 간의 관계가 1대 1의 관계를 갖는다)
• 자료를 삽입하거나 자료를 꺼낼 수 있다.

나. 구조

• 후입 선출 구조
• 연산은 top에서 일어난다.

다. 주요 연산

push : 저장소에 자료를 저장한다.
pop : 저장소에서 자료를 꺼낸다.
peek : 스택 top에 있는 원소를 반환한다. (제거는 하지 않는다.)

라. Function call

프로그램에서의 함수 호출과 복귀에 따른 수행순서를 관리한다.
가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후임선출구조이다
그래서 스택을 이용해서 관리 할수 있는 것이다.

---

2. 큐

스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조이다.
선입선출구조이다.

가. 구조

• 선입 선출 구조
• 머리와 꼬리가 있다. Front / Rear
• 머리에서 삭제가 일어난다.
• 꼬리에서 삽입이 일어난다.

나. java.util.Queue

• java에서 큐에 필요한 연산을 선언해 놓은 인터페이스이다.
• LinkedList 클래스를 Queue 인터페이스의 구현체로 많이 사용한다.

    참조변수-그릇 queue = new LinkedList();
    // Queue -> Deque -> LinkedList 

다. 주요메소드

• offer() : 삽입
• poll() : 삭제
• isEmpty() : 비었는지 확인
• size() : 크기

라. Deque

양쪽에서 연산을 모두 할 수 있다.

---

3. List

가. 개요

• 순서를 가진 데이터의 집합을 가리키는 추상 자료형이다.
• 동일한 데이터를 가지고 있어도 상관없다.
• 순서는, 원소를 관리하기 위함이다.

나. 리스트의 두 가지 종류

구현 방법에 따라 크게 두 가지로 나뉜다.

• 순차리스트 : 배열을 기반으로 구현된 리스트
• 연결리스트 : 메모리 동적할당을 기반으로 구현된 리스트

다. 순차리스트

• 삽입 시, 삽입 위치 다음의 항목들을 뒤로 이동해야한다.
• 삭제 시, 삭제위치 다음의 항목들을 앞으로 이동해야한다.
• 즉 입력과 제거가 어렵다.

라. 연결리스트

• 자료의 논리적인 순서와 메모리 상의 순서가 일치하지 않고, 개별적으로 위치하고 있는 각 원소를 연결하여 하나의 전체적인 자료구조를 이룬다.
• 링크를 통해 원소에 접근하므로, 순차리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않다.
• 자료구조의 크기를 동적으로 조정할 수 있어서 메모리의 효율적인 사용이 가능하다.

• 노드
  연결리스트에서 하나의 원소를 표현하는 building block이다.

  • 구성 : 데이터필드 + 링크필드
    원소의 값을 저장하는 것 다음 노드의 참조값을 저장하는 곳

• 종류

  • 단순 연결리스트 : 링크를 1개만 유지하는 리스트
  • 이중 연결리스트 : 링크를 2개 유지하는 리스트
  • 원형 연결리스트 : 리스트의 끝과 처음을 연결하는 리스트

마. 단순 연결리스트

• 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조
• 헤드가 가장 앞의 노드를 가리키고, 링크필드가 연속적으로 다음 노드를 가리킨다.
  

바. 이중 연결리스트

• 양쪽방향으로 순회할 수 있도록 노드를 연결하는 리스트
• 두개의 링크필드와 한개의 데이터 필드로 구성한다.