기본 콘텐츠로 건너뛰기

[DATA STRUCTURE] 큐 QUEUE


큐[QUEUE]의개념

Queue is an abstract data structure, somewhat similar to Stacks. 
Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). 
Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.

  • First In First Out

Basic Operation

Queue operations may involve initializing or defining the queue, utilizing it, and then completely erasing it from the memory. Here we shall try to understand the basic operations associated with queues −

  • enqueue() − add (store) an item to the queue.
  • dequeue() − remove (access) an item from the queue.

Few more functions are required to make the above-mentioned queue operation efficient. These are −

  • peek() − Gets the element at the front of the queue without removing it.
  • isfull() − Checks if the queue is full.[Boolean]
  • isempty() − Checks if the queue is empty.[Boolean]

큐의사용 예

  • 너비 우선 탐색(BFS, Breadth-First Search) 구현
    처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다.
    노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
    노드를 접근한 순서대로 처리할 수 있다.
  • 캐시(Cache) 구현
  • 우선순위가 같은 작업 예약 (인쇄 대기열)
  • 선입선출이 필요한 대기열 (티켓 카운터)
  • 콜센터 고객 대기시간
  • 프린터의 출력 처리
  • 윈도 시스템의 메시지 처리기
  • 프로세스 관리

Reference

댓글

이 블로그의 인기 게시물

기본적인 MongoDB 사용/자바연동

mongoDB 명령어 db: 현재 사용 중인 데이터베이스 확인 -test :Default로 들어가 있는 test 테이블 show dbs : DB의 리스트 확인 show collections : collection 리스트 확인, collection = table in mongoDB show tables : 위 명령어와 같음 db.stats() : 데이터베이스 상태 확인 db.(db명).drop(): 안에 있는 데이터 삭제 mongod --version => mongodb 확인 mongo -version => shell 확인 use 테이블 명: 테이블 생성 db.dropDatabase() : 접속된 테이블 삭제 -테이블 확인 필요!! db.createCollection(“테이블 명”): 테이블 생성 db.테이블 명.drop(): 테이블 지움 db.blog[테이블 명].insert({“name ” : “ nodejs”}) : 내용(Document)을 추가 db.테이블 명.insert([ {“ ” : “ ”},{“ ” : “ ”}]); -여러 Documents를 하나의 테이블에 넣는 방법 db.blog[테이블 명].find() : 내용 확인 db.테이블 명.find().pretty() : 보기 좋게 검색 id : primary key를 자동으로 부여해줌 db.테이블 명.remove({“name” : “book01”}) : 특정한 Documents를 지우는 법 insert 문 count 문 연산자 몽고디비 비교 연산자 $eq 2. $gt 3. $gte 4. $lt 5. $lte ne : 주어진 값과 일치 하지 않는 값 in: 주어진 배열 안에 속하는 값 nin: 주어진 배열 안에 속하지 않는 값 몽고디비 논리연산자 1.$or: 주어진 조건 중 하나라도 tr...

자바FX 설치하기(펌)

필요한것 최신 Java JDK 8 (JavaFX 8 포함) Eclipse 4.6 또는 e(fx)clipse 플러그인을 포함한 그 이상 버전. 가장 쉬운 방법은 e(fx)clipse website 에서 미리 포함되어 있는 버전을 받습니다. 다른 대안으로는 Eclipse에서 update site 를 이용할 수 있습니다. Gluon이 제공하는 Scene Builder 8.0 (왜냐하면 Oracle은 오직 소스 코드 형태로만 제공 하기 때문입니다.) Eclipse 설정 Eclipse가 JDK 8과 Scene Builder를 사용할 수 있게 해야 합니다: Eclipse Preferences를 열어 *Java | Installed JREs*를 찾습니다. *Add..*를 클릭한 후 *Standard VM*를 선택, JDK 8이 설치되어 있는 *디렉토리*를 고릅니다. 다른 JRE나 JDK를 삭제합니다. 그러면 JDK 8 하나만 남습니다. *Java | Compiler*를 찾아 Compiler compliance level을 1.8로 설정합니다. JavaFX  부분을 찾아 Scene Builder 실행 파일이 있는 경로를 지정합니다. JavaFX 프로젝트 만들기 e(fx)clipse를 설치하고 나서 Eclipse에서  File | New | Other… , *JavaFX Project*를 고릅니다. 프로젝트 이름(예:  AddressApp )을 작성한 다음, *Finish*를 클릭합니다. 자동으로 생성되는  application  패키지가 있다면 삭제하세요. 패키지 만들기 시작부터 우리는 좋은 소프트웨어 디자인 원칙을 따를 겁니다. 가장 중요한 원칙이  모델-뷰-컨트롤러 입니다. 이에 따라 우리의 코드를 세 단위로 나누고 각 패키지를 만듭니다 (src 디렉토리에서 마우스 오른쪽 클릭 후  New… | Package  선택): ...

[DATA STRUCTURE] Stack 스택

What is Stack A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of plates, etc. Basic Operations push()  − Pushing (storing) an element on the stack. pop()  − Removing (accessing) an element from the stack. peek()  − get the top data element of the stack, without removing it. isFull()  − check if stack is full. isEmpty()  − check if stack is empty. 스택(Stack)의 사용 사례 재귀 알고리즘을 사용하는 경우 스택이 유용하다. 재귀 알고리즘 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다. 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다. 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다. 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다. 웹 브라우저 방문기록 (뒤로가기) 실행 취소 (undo) 역순 문자열 만들기 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사) Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기 후위 표기법 계산 public   class   StackTest1  {      public   static   void   main...