스택이란?
- 다른 통로들은 모두 막고 한쪽만을 열어둔 구조
- 열린 곳이자 데이터를 푸시하고 팝하는 윗부분을 top, 꼭대기라 하며 아랫 부분을 bottom,바닥이라 칭함
- 스택에 저장되는 것을 항목 또는 요소라 칭함
- 요소의 삽입과 삭제가 상단에서만 이루어지는 자료구조
- 스택에 저장된 원소는 top으로 정한 곳에서만 접근 가능, top 위치에서만 원소가 삽입 되며 먼저 삽입한 원소는 밑에 쌓이고 나중에 삽입한 원소는 위에 쌓이는 후입선출 구조
- 가장 먼저 삽입한 원소는 stk[0], 가장 마지막에 푸시한 데이터는 stk[ptr-1]에 위치한다.
- 스택 크기는 배열 stk의 원소 수인 len(stk)와 일치
파이썬으로 구현한 stack함수
- 순차구조 구현 스택은 순차자료구조인 1차원 배열을 사용하여 쉽게 구현이 가능하지만 물리적으로 크키가 고정된 배열(튜플)을 사용할 때 스택의 크기 변경이 어려우며, 순차자료구조의 단점을 가진다.
스택의 활용 : 올바른 괄호
- 문자열에 있는 괄호를 차례대로 조사하면서 왼쪽 괄호를 만나면 스택에 삽입하고, 오른쪽 괄호를 만나면 스택에서 top 괄호를 삭제한 후 오른쪽 괄호와 짝이 맞는지 검사한다.
- 스택이 비어 있으면 스택에 조건에 위배하게 되고 괄호의 짝이 맞지 않아도 위배된다.
- 수식에 대한 검사가 모두 끝났을 때 스택은 공백 스택이 되어야 하며 마지막 괄호까지를 조사한 후에도 스택에 괄호가 남아있다면 괄호의 개수가 틀린 수식임.
스택의 활용-2
시스템 스택이란?
- 프로그램에서의 호출과 복귀에 따른 수행순서를 관리
- 가장 마지막에 호출된 함수가 가장 먼저 실행 완료하고 복귀하는 후입선출 구조이기에 후입선출구조의 스택을 이용하여 수행순서를 관리
- 함수 호출이 발생하면 호출한 함수 수행에 필요한 지역변수, 매개변수, 함수 복귀 주소들의 정보를 스택프레임에 저장하여 시스템 스택에 삽입
- 함수의 실행이 끝나면 시스템 스택의 top 원소를 삭제하면서 프레임에 저장되어있던 복귀주소를 확인하고 복귀
- 함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램의 수행이 종료되면 시스템 스택은 공백 스택이 된다.
순환이란?
- 어떤 함수가 자기 자신을 다시 호출하여 문제를 해결하는 프로그래밍
- 순환을 멈추는 부분과 자신을 순환적으로 호출하는 부분이 존재
- 멈추는 부분이 존재하지 않으면 시스템 스택을 다 사용할 때까지 순환하다 오류를 발생시키면서 작동이 멈춤
- 함수 호출의 오버헤드, 문제를 나누어 해결하는 분할 정복 방법 사용
- 분할 정복은 어떤 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법
반복이란?
- for/while문을 사용하며 수행속도가 빠르다
- 순환적인 문제에서는 프로그램 작성이 어려울 수 있으며 순환호출이 끝에서 이루어지는 경우는 반복 알고리즘으로 간단히 변경이 가능하다
- 대부분의 순환은 반복으로 바꾸어 작성이 가능하다
큐란?
- 스택과 비슷한 삽입과 삭제의 위치가 제한되어 있는 유한 순서 리스트
- 뒤에서 삽입만 가능하며 앞에서는 삭제만 할 수 있는 구조
- 가장 먼저 삽입한 원소는 가장 먼저 삭제하는 선입선출 구조
- 전단 부분을 front, 후단 부분을 rear라 칭하며 큐에 데이터를 추가하는 작업을 enqueue, 데이터를 꺼내는 작업을 dequeue라 칭함
- 스택과 큐의 차이
큐의 활용과 큐의 응용
- 빠른 cpu와 속도가 상대적으로 느린 주변장치(ex) 프린터)들 사이의 시간이나 속도 차이를 극복하기 위한 버퍼
- 여기서 버퍼란 갑자기 데이터가 몰려드는 경우 이들을 잠시 보관하는 장소
- 컴퓨터로 현실 세계를 시뮬레이션 하는 분야에서 응용
- 다양한 알고리즘에서 활용(레벨순회, 너비우선탐색, 기수정렬 등)
- cpu 스케쥴링에서 활용
- 프린터 버퍼 큐 : CPU에서 프린터로 보낸 데이터 순서대로 프린터에서 출력하기 위해 선입선출 주고 큐 사용
- 스케줄링 큐 : CPU 사용을 요청한 프로세서들의 순서를 스케줄링 하기 위해서 큐를 사용
선형 큐의 문제점
- 큐에서 삽입과 삭제를 반복하면서 앞부분에 빈자리가 존재하여도 rear = n-1 상태가 지속되어 포화상태로 인식하고 더이상의 삽입을 실행하지 않는다.
- 해결방법 첫번째로는 저장된 원소들을 배열의 앞부분으로 이동시키는 것인데 순차자료에서 이동작업은 연산이 매우 복잡하기에 첫번째 방법은 효율성이 떨어짐
- 두번째 방법으로는 1차원 배열의 사용하면서 논리적으로 배열의 처음과 끝이 연결되어 있다고 가정하고 사용 => 원형 큐
- 시간복잡도 O(n)
우선순위 큐
- 인큐할 때는 데이터에 우선순위를 부여하여 추가하고, 디큐할 때는 우선순위가 가장 높은 데이터를 꺼내는 방식
- 파이썬에서는 우선순위를 부여하는 큐는 heapq 모듈에서 제공
- heap에서 data의 인큐는 heapq.heappush(heap, data)로 수행되고 디큐는 heapq.heappop(heap)으로 수행
원형큐(링버퍼 큐) 구현
- 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조
- 시간 복잡도 O(1)
덱이란?
- 전단과 후단에서 모두 삽입과 삭제가 가능한 큐
- 큐 2개중 하나를 좌우로 뒤집어서 붙인 구조, 큐의 양쪽 끝에서 삽입연산과 삭제연산을 수행할 수 있도록 확장한 자료구조이다.
- 스택을 위아래로 붙인 구조
- 파이썬에서는 덱의 연산을 collections 모듈에서 제공하는 deque 클래스로 구현이 가능하다.
덱 관련 파이썬 메서드 함수
- append(item): item을 덱의 rear에 삽입
- appendleft(item): Item을 덱의 front에 삽입
- pop(): 덱의 rear 끝 요소를 반환하는 동시에 덱에서 제거
- popleft(): 덱의 front 끝 요소를 반환하는 동시에 덱에서 제거
- extend(list): 배열(list)을 순환하면서 덱의 rear에 삽입
- extendleft(list): 배열(list)을 순환하면서 덱의 front에 추가
- remove(item): item을 덱에서 찾아 제거
- rotate(n): 덱의 n만큼 회전(양수일 경우 오른쪽, 음수일 경우 왼쪽)
덱의 응용
- 깊이 우선 탐색(DFS, Depth First Search) : 가장 최근에 저장한 경로를 선택하여 다시 시도(스택을 이용한 구현)
- 너비 우선 탐색(BFS, Breadth First Search) : 가장 먼저 저장된 경로를 선택하여 다시 시도(큐를 이용한 구현)
사진 출처:
쉽게 배우는 C 자료구조 | 생능출판사
코딩을 조금이라도 해 보았다면 프로그래밍이 자료(data)를 주로 다루는 것임을 알 수 있을 것이다. 우리가 프로그램을 개발할 때 가장 먼저 해야 할 일은 처리할 자료를 컴퓨터가 잘 다룰 수 있
www.booksr.co.kr
'자료구조' 카테고리의 다른 글
| 트리 (0) | 2024.07.26 |
|---|---|
| 자료구조 - 연결리스트 (0) | 2024.07.19 |
| 배열 (2) | 2024.07.03 |
| 알고리즘 기초 (0) | 2024.07.02 |
| 자료구조와 알고리즘 (2) | 2024.06.26 |
