Queue & Stack

2023. 6. 24. 13:21·CS 공부/자료구조

Queue란?

 

특징

- Queue의 사전적 의미는 줄, 혹은 줄을 서서 기다리는 것을 의미한다.

- 선입선출(FIFO - First In First Out) 의 자료구조이다. → 먼저 넣은 데이터가 먼저 나온다.

- 그러므로, 순서대로 처리해야할 때 사용한다. 

- 데이터를 추가하는 Enqueue / 데이터를 추출하는 Dequeue 연산이 있다. 

  • Enqueue - 맨 뒤에 데이터를 추가하면 되기 때문에 O(1)이다. (rear포인터 이용)
  • Dequeue - 맨 앞의 데이터를 삭제하면 되기 때문에 O(1)이다. (front포인터 이용)
    • 큐의 가장 첫번째 데이터를 front / 가장 마지막 데이터를 rear로 가리킨다.
    • 접근방법은 front/rear로만 가능하다.

- 활용 예시로는 하나의 자원을 공유하는 프린터나,은행 업무,콜센터 고객 대기시간,프로세스 관리, Cache구현, 너비우선탐색(BFS) 등이 있다.

 

 

 

구현방식

- Array Based : 고정된 크기의 배열로 남는 메모리가 생긴다.  

※ 이러한 단점을 보안하기 위해서? → 원형큐(circular queue)로 구현하는 것이 일반적이다. 

- List Based : 재할당이나 메모리 낭비의 걱정을 할 필요가 없어진다. 

 

 

 

원형큐(Circular Queue)란?

탄생계기 rear이 가르키는 포인터가 배열의 마지막 인덱스를 가르키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용할 수 없다는 선형 큐의 문제점을 보완하기 위한 자료구조 기본 동

hyolls100.tistory.com

 

 

※ 우선순위 큐(priority queue)

- 일반적인 큐와 다르게 우선순위큐(priority queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옴

- 우선순위 큐는 일반적으로 Heap으로 구현

  • Push - O(logn)
  • Pop - O(logn)

 

 

힙(Heap)이란?

특징 - 완전이진트리의 일종임 - 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조임 - 중복된 값을 허용함 - Max Heap은 가장 큰 값을 빠르게 찾기 위한 것이고, Min Heap은 가장 작

hyolls100.tistory.com

 

 

 

Stack이란?

 

특징

- 스택(stack)이란 쌓아 올린다는 것을 의미한다. 따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 

- 후입선출(LIFO - Last In First Out) 의 자료구조이다. → 가장 나중에 추가한 데이터가 가장 먼저 나온다. 

- 재귀적이인 특징이 있다. 

- 데이터를 추가하는 Push / 데이터를 추출하는 Pop 연산이 있다. 

  • Push - 맨 뒤에 데이터를 추가하면 되기 때문에 O(1)이다.
  • Pop - 맨 뒤의 데이터를 삭제하면 되기 때문에 O(1)이다.

- 새로운 데이터는 top이 가리키는 데이터의 위에 쌓이게 된다. 데이터를 삭제할 때도 top을 통해서만 가능하다. 

- 활용 예시로는 call stack, 후위 표기법 연산, 괄호 유효성 검사,역순 문자열 만들기, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS) 등이 있다. 

 

 


 

 

 

스택(Stack) 두 개로 큐(Queue) 구현하기

구현방법 큐를 입력할 때에는 하나의 스택의 push()를 통하여 데이터를 넣고, 큐를 추출할 때에는 다른 스택의 pop()를 통하여 선입선출을 만족시키는 방법 Enqueue - 첫번째 스택 stack1에 push를 하여

hyolls100.tistory.com

 

큐(Queue) 두 개로 스택(Stack) 구현하기

Push - queue1의 enqueue()를 통하여 데이터를 저장 Pop a. queue1의 데이터 갯수가 1개 이하로 남을 때까지 dequeue를 한 후, 해당 데이터를 queue2에 enqueue()하여 옮김. 이 결과로 가장 나중에 들어온 데이터를

hyolls100.tistory.com

 

'CS 공부 > 자료구조' 카테고리의 다른 글

여러 종류의 트리(Tree) 정리 (이진 트리, 전 이진 트리, 완전 이진 트리, 포화 이진 트리, 이진 탐색 트리)  (0) 2023.08.09
힙(Heap)이란?  (0) 2023.08.09
원형큐(Circular Queue)란?  (0) 2023.08.07
Dynamic Array란?  (0) 2023.06.24
Array vs Linked List  (0) 2023.06.24
'CS 공부/자료구조' 카테고리의 다른 글
  • 힙(Heap)이란?
  • 원형큐(Circular Queue)란?
  • Dynamic Array란?
  • Array vs Linked List
횰쓰
횰쓰
개발 성장 블로그입니다
  • 횰쓰
    횰쓰토리
    횰쓰
  • 전체
    오늘
    어제
    • 분류 전체보기
      • CS 공부
        • 운영체제
        • 네트워크
        • 컴퓨터구조
        • 데이터베이스
        • 알고리즘
        • 소프트웨어공학
        • 자료구조
        • 웹
      • 프로그래밍
        • Python
        • NodeJS
      • 개발도구
        • Git
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    3 Way Handshake
    이진탐색트리
    카드뭉치
    프로세스 주소공간
    Max힙
    둘만의 암호
    SQL/NOSQL
    RB Tree
    최태성인강
    4 way handshake
    AVL트리
    멀티 프로세스
    자가균형 이진탐색트리
    tcp
    Push-force
    경쟁상태(Race Condition)
    Git
    chrome
    리스트정렬여부
    Min힙
    페이지 교체
    운영체제
    한국사능력검정시험 심화
    Sync/Async
    큐
    포화이진트리
    멀티 스레드
    전이진트리
    RB트리
    스택
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
횰쓰
Queue & Stack
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.