스택
스택은 가장 최근에 입력된 데이터가 가장 먼저 출력되는 입출력 자료구조이다. (후입선출, LIFO: Last-In-First-Out)
- 스택의 구조는 리스트가 스택 하단(bottom)부터 쌓이는 요소로 구성되며, 스택 상단(top)에 삽입되고 삭제되는 함수가 있다.
스택에서의 연산 과정으로 push()함수와 pop()함수가 사용된다.
- push(): 스택에 데이터를 추가하는 기능을 한다.
- pop(): 스텍에서 데이터를 삭제하는 기능을 한다.
스택 활용
스택을 활용하여 괄호 검사 문제 프로그램을 만들 수 있다.
- 왼쪽 괄호가 입력되면 스텍에 push하며 오른쪽 괄호가 입력되면 스택에서 pop된다.
- 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
- 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안 된다.
또한 스택을 활용하여 후위 표기 수식의 계산을 하는 프로그램을 만들 수 있다.
- 후위 표기법으로 표현된 수식을 왼쪽에서 오른쪽으로 스캔하며 토큰을 찾는다.
- 찾은 토큰이 피연산자이면 스택에 push하고 찾은 토큰이 연산자이면 필요한 수만큼의 피연산자를 스택에서 pop하여 연산을 수행하고 결과를 다시 스택에 push한다.
큐
큐는 가장 먼저 입력된 데이터가 가장 먼저 출력되는 입출력 자료구조이다. (선입선출, FIFO: First-In-First-Out)
- 큐는 배열을 선형으로 사용하여 큐를 구현한 선형 큐, 배열을 원형으로 만들어 큐를 구현한 원형 큐로 구현할 수 있다.
선형 큐
- 선형 큐는 요소 데이터를 저장할 1차원 배열과, 큐의 처음과 끝을 나타내는 front, rear 변수로 구성된다.
- 선형 큐에 요소를 삽입할 떄는 배열의 뒤쪽에 삽입하고, 큐에 요소를 삭제할 때는 배열의 앞쪽부터 삭제한다.
원형 큐
- 원형 큐는 선형 큐에서 front와 rear값이 최대치보다 커지면 다시 0의 값을 가지는 구조로 이루어져 있다.
큐 활용
큐를 활용하여 은행 대기 시간 계산 시뮬레이션 프로그램을 만들 수 있다.
- 은행에서 고객이 들어와서 서비스를 받고 나가는 과정을 시뮬레이션하여 고객들이 기다리는 평균 시간을 계산한다.
- 현재 시각을 나타내는 clock 변수 값을 1 증가하면서 [0, 10] 난수를 생성하여 3보다 작으면 새로운 고객이 은행에 들어온 것(enqueue)으로 판단한다.
- 만약 고객이 enqueue한다면 고객의 아이디, 도착시간, 서비스 시간 정보를 큐에 저장한다.
- 현재 서비스 중이라면 서비스 받는 시간을 알려주는 service_time 변수 값을 1 감소시킨다.
- service_time이 0이면 현재 서비스 받는 고객이 없으므로 큐에서 고객을 dequeue한다.
- 전체 시뮬레이션 시간인 60분(clock == 60)이 될 때 까지 루프를 반복한다.
