[자료구조] Queue과 Stack

자료구조

• 자료구조는 자료들의 집합을 체계적이고 효율적으로 관리하기 위한 형식
• 자료구조는 자료 집합, 규칙, 조작으로 개념을 나누어 이해하는 것이 좋다.
  1. 자료 집합 : 대상이 되는 자료의 본체를 의미함. 배열, 구조체 등 자료를 저장할 수 있는 본체
  2. 규칙 : 자료 집합을 조작, 관리, 유지하기 위해 정한 규칙
  3. 조작 : 자료 집합에 직접 적용하는 처리를 의미함

• stack, queue, linked list, tree 등 다양한 종류의 자료구조가 존재하고 필요와 목적에 따라 적합한 자료구조를 선택해 사용한다.

Queue

• Queue는 C의 array나 python의 list를 자료집합으로 사용할 수 있다. python에는 collections 라이브러리에 dequeue type을 사용하면 queue를 쉽게 구현할 수 있다.
• Queue는 대기열이라고도 부르고, 자료를 삽입된 순서대로 처리하는 선입 선출(First In, First Out, FIFO) 규칙에 따라 자료를 관리한다.
• 기본적인 조작은 enqueue, dequeue, isEmpty, isFull 등이 있다.
  enqueue : queue의 끝에 자료를 추가함
  dequeue : queue의 가장 앞 요소를 반환함
  isEmpty : queue가 비어있는지 확인
  isFull : queue가 꽉 찼는지 확인

• 위의 그림은 1, 2, 3을 순서대로 enqueue하고 차례로 dequeue하는 것을 볼 수 이따.
• push된 순서대로 반환되는 것을 볼 수 있다.

C에서 queue 구현

• 데이터를 꺼내는 위치인 read point와 데이터를 쓰는 write point 두 개의 변수로 데이터를 처리한다.

python에서 queue 구현

• python의 내장 라이브러리인 collections의 deque type을 사용하면 쉽게 queue를 사용할 수 있다.

Stack

• Stack은 C의 array나 python의 list를 자료집합으로 사용할 수 있다.
• Stack은 가장 마지막에 들어간 자료를 먼저 꺼내는 후입 선출(Last In First Out, LIFO) 규칙에 따라 자료를 관리
• 기본적인 조작은 push, pop, isEmpty, isFull 등이 있다.
  push(x) : 스택의 가장 위에 요소 x를 추가한다.
  pop() : 스택의 가장 위에있는 요소를 반환함
  isEmpty() : 스택이 비어있는지 여부를 판단
  isFull() : 스택이 꽉찼는지 확인

Stack

• 위의 그림은 1, 2, 3을 순서대로 stack에 push하고 차례로 pop하는 것을 볼 수 있다.
• push된 순서의 역순인 3, 2, 1 순으로 pop되는 것을 볼 수 있다.

C에서 stack 구현

• 데이터를 읽는 point와 데이터를 쓰는 point가 동일해 하나의 변수로 데이터를 처리할 수 있다.

python에서 stack 구현

• python은 list 자료형을 stack 자체로 사용하거나 collections모듈의 deque를 사용할 수 있다. list는 append와 pop으로, deque는 append와 popright를 사용해 push와 pop 기능을 구현할 수 있다.