[자료구조] 스택(Stack) & 큐(Queue)

스택(Stack)

• 후입선출(Last In First Out; LIFO) 자료구조 : 마지막에 들어온 데이터가 먼저 나가는 구조

스택 구현

• 일반적으로 배열 또는 연결 리스트로 구현
• 배열 기반 스택 : 고정된 크기를 가짐
• 연결 리스트 기반 스택 : 동적으로 크기가 조정됨

스택 기본 연산

• push: 스택의 맨 위에 요소 추가
• pop : 스택의 맨 위에 있는 요소를 제거하고 반환
• peek 또는 top : 스택의 맨 위에 있는 요소를 반환하지만 제거하지는 않음

스택 사용

데이터의 순서와 관련된 정보를 유지하면서 데이터를 저장하고 검색하는 경우 유용하게 사용된다.

1. 함수 호출과 재귀 알고리즘
   • 함수가 호출되면 해당 함수의 호출 정보(매개 변수, 반환 주소 등)가 스택의 맨 위에 저장된다.
   • 함수의 실행이 완료되면 스택에서 해당 호출 정보가 제거된다.
     이렇게 스택을 사용하면 함수 호출의 순서와 관련된 정보를 유지하면서 재귀적인 호출을 구현할 수 있다.
     
     
2. 브라우저의 뒤로/앞으로 버튼 
   • 방문한 웹 페이지의 탐색 기록이 스택에 저장되며, 각 페이지 방문시 스택에 해당 정보가 추가된다.
   • 뒤로/앞으로 버튼을 클릭하면 스택에서 페이지의 탐색 기록이 제거된다.
     이를 통해 사용자는 이전에 방문한 페이지로 돌아갈 수 있다.
     
     
3. 실행 취소/다시 실행 기능
   • 각 실행 단계마다 수행한 작업에 대한 정보(ex. 편집한 텍스트, 수행한 명령)는 스택에 저장된다.
   • 실행 취소를 선택하면 스택에서 가장 최근에 수행한 작접이 제거되고, 다시 실행을 선택하면 스택에서 제거한 작업이 다시 수행된다.
4. 인터럽트 처리
   • 인터럽트 : 컴퓨터 시스템에서 발생하는 이벤트로, 현재 실행 중인 프로그램을 일시적으로 중단하고 특정한 작업을 수행하는 것
   • 인터럽트가 발생하면 현재 실행 중인 명령어의 주소와 프로그램 상태 등을 백업하여 인터럽트 처리가 끝난 후 원래 진행중이던 프로그램을 이어서 진행할 수 있게 된다.
     이때 현재 실행 중인 명령어의 주소와 프로그램 상태 등을 스택저장한다.
     
     
5. 다른 자료구조 구현
   • 큐(Queue) 
   • 데크(Deque) 

큐(Queue)

• 선입선출(First In First Out; FIFO) 자료구조 : 먼저 들어온 데이터가 먼저 나가는 구조

큐 구현

큐는 배열과 연결 리스트를 사용하여 구현할 수 있다.

• 배열을 사용한 큐
  • 배열의 인덱스를 활용하여 요소를 저장하고, 큐의 front와 rear 포인터를 사용하여 삽입과 삭제 연산을 관리한다.
  • 큐의 크기를 제한하는 경우에 유용하며, 메모리 관리가 비교적 간단하다.
  • 하지만 배열의 크기를 변경하기 어렵고, 요소의 삽입과 삭제 시 재배치 작업이 필요할 수 있다.
    
    
• 연결 리스트를 사용한 큐
  • 큐의 front와 rear 포인터는 연결리스트의 시작과 끝을 가리키며, 삽입과 삭제 연산은 노드를 추가하거나 제거하여 처리된다.
  • 큐의 크기가 동적으로 확장될 수 있지만, 각 노드가 포인터를 저장해야 하므로 메모리 사용량이 배열을 이용하여 구현한 것 보다 더 많을 수 있다.
    
    
• 기타 구현 방법
  • 연결 리스트와 배열을 결합한 형태인 Linked Array 나 동적 배열을 사용할 수도 있다.
  • 스택 두 개를 이용하여 큐를 구현하는 데크(Deque)와 같은 방법도 있다.
    데크 : 양방향에서 삽입과 삭제가 가능한 자료구조 (Double-ended Queue)

큐 기본 연산

• 삽입(Enqueue) : 큐에 데이터를 추가하는 연산으로 큐의 뒤쪽에 요소를 삽입
• 삭제(Dequeue) : 큐에서 데이터를 제거하는 연산으로 큐의 앞쪽에서 요소를 제거하고 반환
• peek 또는 front : 큐의 가장 앞쪽에 위치한 요소를 반환하는 연산으로 제거는 하지 않음

큐 사용

데이터를 순서대로 처리해야 할 때 유용하게 사용된다.

1. 네트워크 패킷 처리
   • 네트워크에서 데이터 전송 시 패킷(Packet)  단위로 분할되어 전송된다. 
   • 패킷이 도착하면 큐에 Enqueue 되고, 패킷 처리 시스템은 큐에서 패킷을 Dequeue 하여 처리한다.
   • 큐를 사용하여 패킷을 처리하면 동시에 여러 패킷을 처리하고 순서를 유지할 수 있도록 도와준다.
     
     
2. 프로세스 관리
3. 버퍼 관리
   • 버퍼 : 데이터를 임시로 저장하는 메모리 공간
   • 버퍼를 관리할 때 큐를 사용하여 데이터의 일시적인 저장과 순차적인 처리를 보장할 수 있다.
     
     
4. 멀티스레드 환경에서의 동기화
   • 멀티스레드 환경에서 여러 스레드가 동시에 공유 자원에 접근 하는 경우 동기화가 필요하다.
   • 이때 큐를 사용하여 스레드는 큐에 데이터를 Enqueue하고 다른 스레드는 큐에서 Dequeue하여 작업을 수행하면서 동기화 문제를 해결하고, 스레드의 안정성과 일관성을 보장할 수 있다.

우선순위 큐(Priority Queue)

• 모든 데이터에 우선순위가 있으며 우선순위가 높은 데이터가 먼저 나온다.
• 우선순위가 같은 경우는 FIFO 규칙을 따른다.