카테고리 없음
[Data Structure]Queue와 Stack
eigen96
2023. 4. 28. 18:34
728x90
기본원리
선형 데이터 구조로 데이터를 저장하고 접근하는 방식에 따라 구분함.
Stack
- 스택은 Last-In-First-Out (LIFO) 원칙을 따르는 데이터 구조
Queue
- 큐는 First-In-First-Out (FIFO) 원칙을 따르는 데이터 구조
시간복잡도
Stack
- 전부 O(1)
Queue
- 전부 O(1)
사용 예시
Stack
- 함수 호출 관리
- 함수가 호출되면 함수 관련 record(지역변수, 매개변수, 메타데이터 등)가 Call Stack에 push됨.
- 함수가 반환되면 record가 스택에서 pop됨
- DFS(깊이 우선 검색)
- 그래프 및 트리에 대한 DFS 순회 알고리즘을 구현
- 노드를 스택에 푸시하고 팝하면 역추적하기 전에 경로를 따라 모든 노드를 방문하여 깊이 우선 방식
- 실행 취소/다시 실행 기능
- 변경 기록을 앞뒤로 이동가능하게 해줌.
- 후위 표기법(Postfix Notation)
Queue
- 작업 스케줄링
- 큐는 운영 체제와 같은 멀티태스킹 환경에서 작업을 관리.작업이 순서대로 실행되어 공정성과 예측 가능성을 제공
- 인쇄 스풀링
- 인쇄 작업 대기열을 유지하면 작업이 제출된 순서대로 인쇄
- BFS(너비 우선 탐색)
- 노드를 Queue에 추가하고 Queue에서 빼면 다음 Level로 이동하기 전에 지정된 수준의 모든 노드를 방문하여 너비 우선 방식으로 그래프 또는 트리를 탐색
- 버퍼링
- 데이터 스트리밍, 네트워크 패킷 관리 또는 키보드 입력 처리와 같은 다양한 애플리케이션에서 버퍼를 구현할 때 사용.
- 들어오는 데이터의 대기열을 유지함으로써 데이터가 수신된 순서대로 처리되도록 하고 처리 지연으로 인한 데이터 손실을 방지
구현 방법
캐시 친화적(cache-friendly) CPU 캐시를 활용하는 알고리즘 또는 데이터 구조의 속성 ex) 자주 or 순차적으로 액세스되는 데이터가 인접한 메모리 블록에 저장될 때 캐시 친화적.
| Stack(Array 구현시) | Stack (Linked List 구현시) |
장점
|
|
|
|
Queue(Array) |
Queue(Linked List) |
|
|
|
|
Code
Stack (Array)
#include <iostream>
struct Stack {
int capacity;
int top;
int* array;
};
void initialize(Stack& stack, int capacity) {
stack.capacity = capacity;
stack.top = -1;
stack.array = new int[capacity];
}
void deinitialize(Stack& stack) {
delete[] stack.array;
}
void push(Stack& stack, int value) {
if (stack.top == stack.capacity - 1) {
std::cerr << "Stack overflow. Cannot push." << std::endl;
return;
}
stack.array[++stack.top] = value;
}
int pop(Stack& stack) {
if (stack.top == -1) {
std::cerr << "Stack underflow. Cannot pop." << std::endl;
return -1;
}
return stack.array[stack.top--];
}
int peek(Stack& stack) {
if (stack.top == -1) {
std::cerr << "Stack is empty. Cannot peek." << std::endl;
return -1;
}
return stack.array[stack.top];
}
bool isEmpty(Stack& stack) {
return stack.top == -1;
}
int main() {
Stack stack;
initialize(stack, 5);
push(stack, 10);
push(stack, 20);
push(stack, 30);
push(stack, 40);
std::cout << "Top element is: " << peek(stack) << std::endl;
std::cout << "Popped element is: " << pop(stack) << std::endl;
std::cout << "Top element is now: " << peek(stack) << std::endl;
deinitialize(stack);
return 0;
}
Stack (Linked List)
#include <iostream>
class Stack {
public:
Stack() : head(nullptr) {}
~Stack() {
while (!isEmpty()) {
pop();
}
}
void push(int value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
}
int pop() {
if (isEmpty()) {
std::cerr << "Stack underflow. Cannot pop." << std::endl;
return -1;
}
int poppedValue = head->data;
Node* temp = head;
head = head->next;
delete temp;
return poppedValue;
}
int peek() {
if (isEmpty()) {
std::cerr << "Stack is empty. Cannot peek." << std::endl;
return -1;
}
return head->data;
}
bool isEmpty() {
return head == nullptr;
}
private:
struct Node {
int data;
Node* next;
Node(int data) : data(data), next(nullptr) {}
};
Node* head;
};
int main() {
Stack stack;
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
std::cout << "Top element is: " << stack.peek() << std::endl;
std::cout << "Popped element is: " << stack.pop() << std::endl;
std::cout << "Top element is now: " << stack.peek() << std::endl;
return 0;
}
Deque란?
- deque("double-ended queue"의 줄임말)는 양쪽 끝, 즉 전면과 후면에서 요소를 추가하거나 제거할 수 있는 데이터 구조
- 스택과 대기열의 기능을 모두 포함
Stack Overflow와 Stack Underflow
- 스택 데이터 구조로 작업할 때 발생하는 이슈
Stack OverFlow
- 스택 오버플로는 이미 가득 찬 스택에 push 할 때 발생
- 데이터가 의도하지 않은 위치에 기록될 수 있으므로 메모리 손상 또는 예기치 않은 동작이 발생
Stack UnderFlow
- 스택 언더플로는 빈 스택에서 Pop하려고 할 때 발생합니다.
- 또한 프로그램이 존재하지 않거나 사용하지 않는 데이터에 액세스하려고 시도할 수 있으므로 메모리 손상이나 예기치 않은 동작이 발생
해결방법
- 팝 및 푸시 작업 전에 비어 있거나 가득 찬 조건을 확인
- 동적 데이터 구조 사용
- 스택 크기 제한 구현
참조
- 자료구조와 함께 배우는 알고리즘 입문 (이지스 퍼블리싱 2017)
728x90