[TIL][Fri] 스택 / 큐

스택

학습 사이트

leetcode

스택(Stack) 자료구조 개념 | 배열 Vs 연결 리스트 | LIFO(Last In First Out) | push | pop | top | Overflow | Underflow

스택의 개념 :: LIFO 원칙

스택은 "Last-In, First-Out" 원칙을 따르며, 마지막으로 추가된 항목은 가장 먼저 제거되는 형식의 자료구조이다.

스택의 연산

Push(item): 스택 상단에 요소를 추가

Pop(): 스택에서 상단 요소를 제거

Peek()/Top(): 요소를 제거하지 않고 스택 상단에 있는 요소를 봄

IsEmpty(): 스택이 비어 있는지 확인

push pop

삽입	삭제(인출)
스택의 끝	가장 끝 요소

스택과 데이터 구조

배열

배열은 같은 타입의 요소들의 고정된 사이즈의 집합이다. index에 기반해서 직접 접근이 가능하며, 스택을 구현하기 위해서 이 배열을 사용할 수 있고, index 변수를 사용해 스택 상단을 추적할 수 있다.

장점

빠른 접근 가능(index기반)

고려해야 할 점

크기가 고정되어있으나, 스택이 초기 용량을 뛰넘는다면 배열 크기를 다시 설정해야 할 수 있다.

동적 크기 조정(사이즈 변동시)은 시간복잡도 측면에서 비용이 많이 드는 작업이 될 수 있다.

언제 배열을 스택에 사용할까?

• stack의 최대 크기를 사전에 알고 있거나 추론 가능할 때.
• 요소에 랜덤 엑세스(index기반접근)가 필요할 때
• 더 단순하고 간단한 구현을 원할

연결리스트(linked list)

각각의 노드(요소)를 스택에 표현할 때 단일 연결 리스트를 사용할 수 있고, 그 head를 스택의 top에 둘 수 있다.

장점

동적 크기 조정이 자유롭다.

스택의 실제 크기에 맞게 조정할 수 있기에 메모리 효율성이 좋다: 연결리스트는 오직 필요할 때에만 노드를 위해 메모리를 할당하는데, 이는 사이즈가 자주 변할 수 있는 스택 같은 데이터 구조를 다룰 때 유용하다.

고려해야 할 점

더 느린 접근: 리스트를 한번 쭉 돌아봐야 하므로 배열에 비해 접근이 느려진다.

언제 연결리스트를 스택에 사용할까?

• stack의 사이즈가 자주 바뀔 때
• 동적 크기 조정/ 메모리 효율성이 중요할 때
• 랜덤 엑세스보다 삽입과 삭제가 더 자주 고려될 때

복잡도

Time and Space Complexity analysis of Stack operations

push 와 pop은 일반적으로 O(1)의 시간복잡도를 가진다.

사용사례

• 웹브라우저 방문기록(뒤로가기)
• 역순 문자열 생성
• 역추적 알고리즘
• 기능 실행 취소 (undo)
• 함수 호출 재귀 관리
• 후위 표기법 계산
• 수식의 괄호 검사(연산자 우선순위 표현을 위한 괄호 검사)

에러 헨들링

• 빈 stack에서 요소를 하나 pop하려고 할 때 등…
• Four Models of Error Handling for Stacks

스택과 DFS

 

---

큐

원형큐(Circular Queue) 자료구조 - front와 rear값 변경 / FIFO(선입선출)

코딩테스트, 초급, 원형큐, circular Queue

What is the difference between linkedlist and queue?

Time and Space Complexity Analysis of Queue operations

큐의 개념

"선입, 선출" 원칙을 따르며, 추가된 첫 번째 항목 가장 먼저 제거되는 자료 구조이다.

큐의 연산

• Enqueue: 큐 뒤에 요소를 추가한다.
• Dequeue: 큐의 맨 앞에서 요소를 하나 제거한다.
• Peek/Front: 삭제하지 않고 큐의 맨 앞 요소를 살펴본다.
• IsEmpty: 큐가 비었는지 아닌지 체크한다.
• IsFull (if applicable): 큐가 최대 용량에 도달했는지 확인한다.

큐와 데이터 구조

배열

Circular queue는 배열의 끝에 도달했을 때 다음 요소는 배열의 시작에 위치하게 된다.

장점

동적 크기 조정 없이 고정된 사이즈의 배열을 다루기 때문에 매모리 사용에 효율적이다.

연결리스트에 비해 요소에 빠른 접근이 가능하다.

사례

네트워킹에서의 버퍼링- 들어오는 데이터의 buffer 관리에 사용될 수 있다. 버퍼가 가득 차면 새로운 packet이 기존의 오래된 것을 덮어씌운다.

연결리스트

단일 연결 리스트에 이전 노드를 가리키는 포인터를 추가한 이중 연결 리스트를 사용할 수 있다. 마찬가지로 리스트의 head를 큐의 맨 처음으로 간주 가능하다.

장점

동적 사이즈: 재조정 연상을 고려하지 않고 자유롭게 늘였다 줄였다 할 수 있음.

리스트의 삽입과 삭제 모두 효율적이다.

사례

실시간 처리(Real-Time processing) 작업의 처리 시간이 다양한 실시간 처리 시스템에서는 큐 기반의 단일리스트가 실시간으로 바뀌고 있는 load에 동적으로 조정 가능하다. (미확인)

큐와 복잡도

Time and Space Complexity Analysis of Queue operations

Time Complexity Auxiliary Space

enqueue() using Array	O(1)	O(1)
enqueue() using Linked List	O(1)	O(1)
dequeue() using Array	O(1)	O(1)
dequeue using Linked List	O(1)	O(1)
peek() using Array	O(1)	O(1)
peek() using Linked List	O(1)	O(1)
initialize() using array	O(n)	O(n)
initialize() using LinkedList	O(n)	O(n)
isfull() using array	O(1)	O(1)
isfull() using Linked List	O(1)	O(1)
isempty() operation using array	O(1)	O(1)
isempty() operation using LinkedList	O(1)	O(1)

사용 사례

• 컴퓨터 시스템의 작업 관리
• 프로세스 스케줄링
• 네트워킹의 작업 처리 등 큐 특히 유용한 시나리오

에러 헨들링

• 빈 queue에서 dequeue하려할 때
• 꽉 찬 queue에(만약 최대 용량을 가지고 있는 큐일 때) enqueue할 때

---

[한걸음 더] 큐: circular queue

어떻게 하면 de/enqueue할 때, 데이터가 이동하지 않을까?

queue의 문제점

실제 데이터를 삭제/꺼내려다 보니 (그 뒤의 데이터들이 이동해야 해서) 오버헤드가 발생함.

해결방안

저장하는 위치와 꺼내는 위치를 지정하고, 꺼내는 위치부터 저장하는 위치 전까지가 데이터가 있는 곳이라고 간주한다.

즉, 데이터를 실제로 옮기는 것이 아니라, 단지 front(데이터를 꺼내는 위치)와 rear(데이터를 저장하는 위치)위치만 바꾸면 오버해드를 줄일 수 있게 된다. 실제 데이터가 삭제되냐 않느냐는 큰 문제가 아니다.

 

구현 시 포인트

변수 설정

데이터를 꺼내는 위치를 지정하는 변수 : front
데이터가 들어갈 위치를 지정하는 변수: rear
현재 데이터가 몇개 저장되었는지를 저장하는 변수: count

index 계산

인덱스가 update될때마다 나머지를 계산해야 front index와 rear index를 정확히 알 수 있다.(ex: idx%6)

max size와 rear의 값이 같다면?

다시 rear의 값을 0으로 바꿔줘야 한다. 이때 rear과 front가 같다면 두가지 경우가 있다.

1. 모든 메모리가 꽉 차있다. (한바퀴 돌아서 같아진 경우 발생)
2. 데이터가 한개도 없는 상태 (초기에)

→ 1과 2를 구별하기 위해 다른 변수가 필요하다. (count로 설정)

count 설정

1. rear를 증가하면서 count를 증가
2. front를 이동하면서 count를 감소시켜 1과 2를 구별한다.

queue vs circular queue

 

상황	queue	circular queue
데이터 입력 시	maximum size가 있어서 overflow가 일어날 수 있다.	일반적인 큐는 새로운 데이터를 아무런 문제 없이 받을 수 있음.

[한걸음 더] 큐와 BFS

23.10.20 러프하게 작성

 

stack / queue implementation by hand

 

c언어의 연결리스트로 구현할 때 메모리 관리와 연결 조직 간 헷갈리는 걸 조심하자