본문 바로가기

플밍 is 뭔들/자료구조

04-4 큐의 응용 컴퓨터의 여러 분야에서 발생한 순서대로 문제를 해결해야 하는 경우 큐를 사용한다. 운영체제에서 실행을 요청한 작업들을 순서대로 처리하기 위해서 버퍼 큐와 프로세스 스케줄링 큐를 사용하고, 산업공학 등의 분야에서는 최적의 시스템을 설계ㅖ하기 위한 시물레이션에서 대기 행렬 큐를 사용한다. ※ 운영체제의 작업 큐 - 각기 다른 속도로 실행되는 작업 처리 기간을 조화시키기 위해 사용. ex) 인쇄작업에 버퍼 큐를 이용해 CPU에 비해 느린 인쇄 작업이 진행중일 때 기다리지않고 다음 데이터를 버퍼 큐에 삽 입하여 버퍼큐에 있는 데이터를 순서대로 출력하게 한다. - CUP를 사용하고자 하는 프로세스들에 대한 CPU 사용 스케줄을 관리하기 위해 스케줄링 큐를 사용 준비 큐와 대기 큐로 구성되어 있음 사용하고자 하는 .. 더보기
04-3 큐의 구현(연결 자료구조 방식을 이용한 큐) ※ 순차 자료구조 방식의 단점 사용 크기가 제한되어 있다.(큐의 크기를 마음대로 변경할 수 없다) 원소가 없어도 항상 처음 크기를 유지해야 된다(메모리 낭비가 생긴다) 이러한 문제를 해결하기 위해 연결 자료구조 방식을 이용하여 크기에 제한없는 연결 큐를 구현해 보자. ※ 연결 큐 연결 큐의 초기 상태(공백 큐)에서 front와 rear는 null이다. front는 첫번째 노드를 가르키고(Linked List에서의 head) rear는 마지막 노드를 가르킨다(Linked List에서의 tail) ※ 연결 큐 구현 소스 Interface public interface Queue { boolean isEmpty(); void enQueue(String item); String deQueue(); void de.. 더보기
04-2 큐의 구현(순차 자료구조를 이용한 큐) ※ 큐의 구현 배열을 사용하는 순차 자료구조 방식과 참조변수를 사용하는 연결 자료구조 방식이 있다. 초기 큐를 생성하면 rear와 front는 모두 -1이다. rear와 front 가 같으면 큐에는 값이 없는상태이다. 생성, 공백 큐 검사, 삽입, 삭제, 검색기능이 있다. ※ 선형 큐 구현 소스(순차 자료구조를 이용해 구현) Interface public interface Queue { boolean isEmpty(); boolean isFull(); void enQueue(char item); char deQueue(); void delete(); char peek(); } ArrayQueue public class ArrayQueue implements Queue { private int rear; .. 더보기
04-1 큐(Queue) ※ 큐란? 스택과 다르게 한쪽에선 삽입연산이 일어나고 한쪽에서는 삭제연산이 일어나는 선입선출(FIFO, First In First Out)의 자료구조. 한쪽은 프론트(front)로 정하여 삭제연산만 수행하고 한쪽은 리어(rear)로 정하여 삽입 연산만 수행하도록 제한한다. 큐에서 이루어 지는 삽입연산을 enQueue라 하고 삭제연산을 deQueue라 한다. ※ 선형큐와 원형 큐 선형 큐는 우리가 생각하는 일반적인 큐(바로 위의 그림)이며 원형 큐는 선형큐를 말아논것과 같은 개념이다. 물리적인 형태는 같지만 코딩을 통해 원형의 형태의 개념으로 구현할 수 있다. 원형큐의 장점과 각각의 차이점은 04-2에 있으니 기억이 나지 않으면 가서 확인하자. ※ 연결 큐와 덱 연결 큐와 덱 모두 연결 자료구조를 사용해 .. 더보기
03-4 스택의 응용 ※ 역순 문자열 만들기스택에 한 문자 단위로 잘라서 push했다가 pop을하면 문자열을 역으로 만들 수 있다. ※ 시스템 스택 프로그램 간의 호출과 복귀에 따른 수행 순서를 보면, 호출한 순서와 복귀하는 순서는 반대가 되어 가장 나중에 호출된 함수가 가정 먼저 실행을 완료하고 복귀한다. 따라서 함수의 호출과 복귀 순서는 스택의 LIFO 구조를 응용하여 관리하는데, 이때 사용하는 스택을 시스템 스택(System Stack)이라 한다. 함수나 서브프로그램이 호출되면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프래임에 저장하여 시스템 스택에 삽입(push)한다. 시스템 스택의 top은 현재 실행중인 함수의 스택 프레임이 된다. 그리고 함수가 종료되면 top의 스택.. 더보기
03-3 스택의 구현(연결 자료구조 방식) ※ 순차 자료구조를 이용해 구현한 스택과 차이점 배열을 사용하여 구현하기는 쉽지만 물리적 크기가 고정되어 있는 배열을 사용하기 때문에 스택의 크기를 변경하기 어렵고 물리적인 공간 낭비가 생길 수 있다. 이러한 문제를 연결 자료구조를 이용함으로써 해결할 수 있다. ※ 연결 자료구조를 통한 구현 스택 초기 상태(공백 스택)는 참조변수 top을 null로 설정. 스택이 push되면 새로 push된 노드는 이전 노드를 가르키고 top은 새로 들어온 노드를 가르킨다. ※ 연결 자료구조를 통한 구현 소스 Interface Stack interface Stack{ boolean isEmpty(); //스택이 공백스택인지 확인하는 함수 void push(char item); //문자를 push하는 함수 char pop.. 더보기
03-2 스택의 구현(순차 자료구조) ※ 스택의 구현 순차 자료구조를 이용한 방식 연결 자료구조를 이용한 방식 ※ 순차 자료구조를 통한 구현 차원 배열 stack[n]을 사용할 때 n이 스택의 크기가 되며 top이 n보다 클 수 없다. 스택에 원소가 쌓이는 순서를 배열의 인덱스로 표현한다. 가장큰 인덱스가 top이된다. top은 0부터 n-1의 인덱스를 저장하므로, 스텍이 초기상태(공백스택, 스택에 값이 없을 때) top에는 -1을 저장한다. ※ 순차 자료구조를 통한 구현 소스 interface Stack interface Stack{ boolean isEmpty(); //스택이 공백스택인지 확인하는 함수 void push(char item); //문자를 push하는 함수 char pop(); //pop 하는 함수(top에 있는 원소를 삭제.. 더보기
03-1 스택 ※ 스택이란? 스택이란 자료구조는 top을 통해 자료가 순차적으로 쌓인다. 또한 top을 통해 순차적으로 출력된다. 그래서 가장 오래된 자료가 가장아래 쌓이고 가장 최신 자료가 제일 위에 쌓인다. 시간에 따라 자료가 쌓이고 삭제할 때는 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO, Last-In-First-Out) 구조를 갖는다. top을 통한 삽입연산을 push라 하며 top을통한 삭제연산을 pop이라 한다. 더보기
02-4 이중 연결 리스트 ※ 이중 연결 리스트 단순 연결 리스트는 선행 노드에 접근하기가 어렵다. 그래서 이를 개선하기 위해 원형 연결 리스트를 구성했다. 하지만 원형 연결 리스트에서도 현재 노드의 선행 노드에 접근하기 위해서는 전체 리스트를 한바퀴 순회해야 하는 문제가 생긴다. 이러한 문제점들을 보완하기 위해 이중 연결 리스트(Doubly Linked List)가 있다. 앞에서 배운 연결 리스트들은 link가 하나였고 다음 노드값들을 저장해 두었다. 하지만 이중연결 리스트는 노드에 link부분을 앞뒤로 두어 선행노드와 후행노드를 각각 연결해둔다. 그래서 선행노드의 접근이 다른 연결 리스트에 비해 쉽다. ※ 구현(아래 이중 연결 리스트로 구현한다) 메인 public class Main { public static void mai.. 더보기
02-3 원형 연결 리스트 ※ 원형 연결 리스트(Circular Linked List)란? 연결 리스트의 구조를 원형으로 만든것 -> 마지막 노드의 링크를 첫번째 노드에 걸어준다. 단순 연결 리스트는 이전 노드에 접근하려면 노드를 다시 처음부터 순회해야 되지만 원형 연결 리스트는 계속 순회하면 이전 노드에 접근할 수 있다. 1.원형 연결 리스트의 삽입연산 운형 연결 리스트에서의 삽입연산은 마지막 노드부분을 처음 노드와 연결하는 부분 빼고 단순 연결 리스트와 똑같다. 또한 원형 연결 리스트의 마지막 노드를 삽입하는 것이 곧 리스트의 첫 번째 노드를 삽입하는 것과 같은 의미이다. 그래서 원형 연결 리스트에서의 삽입연산은 첫 번째 노드 삽입과 중간 노드 삽입의 경우로 나눌 수 있다. ※ 구현 메인 public class Main { p.. 더보기
02-2 단순 연결 리스트 ※ 전장에서 공부했든 연결리스트에 대한 기본 구조는 알고 있을 것이다. 노드를 만들 때 C에서는 link 부분을 포인터를 이용했지만 자바에서는 포인터대신 객체를 이용한다. ex) Node.link.link.link.link 의 방식으로 연결 리스트의 노드를 탐색한다고 생각하자. ※ 자바에서의 포인터개념?? 자바에서 포인터 개념을 알기 위해선 메모리 구조에 대해 알아야 한다. 정적 메모리 스텍(Stack) 영역 스택 영역은 변수값을 저장하게 되는데 기본타입인 정수형(int/short/char/byte)변수와 실수형(float/double)변수와 논리형(boolean)변수를 실제값으로 저장한다 크기가 정해져 있는 타입이다. 메모리 할당시 컴파일할때 이미 계산이 이루어진다. 메소드 작업이 종료되면 할당되어던 .. 더보기
02-1 연결 자료구조 방식 ※ 연결 자료구조 방식 순차 자료구조 방식에서의 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 자료 표현 방식 순차 자료구조 방식에서의 문제점이란? 1. 순차 자료구조에서 배열이 갖고 있는 메모리 사용의 비효율성 문제 2. 삽입,삭제 연산 시 발생하는 원소들의 이동 작업으로인한 오버헤드 증가로 인한 성능문제 연결 자료구조 방식에서는 순차 자료구조 방식에서처럼 물리적순서와 논리적 순서가 같을 필요가 없다. 각 원소(노드)에 저장되어 있는 다음 원소의 주소에 대한 참조에 의해서 연결되는 방식 여러개의 작은 공간을 연결하여 전체를 표현하므로 크기 변경이 유연하고 좀더 효율적인 메모리 사용 가능 물리적 순서를 맞추기 위한 오버헤드가 발생하지 않는다. 연결 자료구조(Linked Data Structur.. 더보기

티스토리툴바