Stack
LIFO
Stack은 쌓아 올리는 방식의 자료구조이다.
LIFO (Last In First Out, 후입선출), 또는 FILO (First In Last Out, 선입후출) 방식으로, 가장 먼저 들어온 데이터가 가장 나중에 나가며, 가장 나중에 들어온 데이터가 가장 먼저 나간다.
변수 'top'을 선언하며, 이는 가장 위에 있는, 가장 최근에 들어온 Element를 가리킨다.
최초 구현 시, 변수 'top'을 -1로 초기화하여 빈 Stack을 만든다.
Element를 추가할 경우, 현재 'top'이 가리키는 Element의 위에 쌓이며 'top' 값이 1 증가한다.
Element를 제거할 경우, 현재 'top'이 가리키는 Element를 제거하고 'top' 값이 1 감소한다.
Array와 Linked List 모두 구현이 가능하며, Array 방식을 사용하여 구현할 경우 Buffer의 구현 방식에 따라 다시 두 종류로 나눌 수 있다.
- Non-Circular buffer
- Circular buffer
주요 연산
- push (or insert) : Stack의 가장 위에 Element를 추가
- pop (or delete) : Stack의 가장 위의 Element를 제거하고 값을 반환
- peek (or top) : Stack의 가장 위의 Element를 반환 (제거는 하지 않음)
- isEmpty (or stack_empty) : Stack이 비어 있는지 확인
- isFull (or stack_full) : Stack이 가득 차 있는지 확인
주요 사용 예시
- 함수 호출 시의 스택 프레임 관리
- 수식의 괄호 검사 : 왼쪽 괄호와 오른쪽 괄호의 개수와 순서를 순차적 검사
- 깊이 우선 탐색(DFS) 알고리즘 구현 : 순차적 탐색으로 Stack의 방식과 유사
- 웹 브라우저의 뒤로 가기 기능 : 가장 마지막에 열린 페이지 복구
C++ 예시 코드
#include <iostream>
#define SIZE 5 // Stack size
using namespace std;
class Stack {
private:
int arr[SIZE]; // Array 기반
int top;
public:
Stack() { top = -1; } // 초기화
bool isEmpty() { return top == -1; }
bool isFull() { return top == SIZE - 1; }
void push(int value) {
if (isFull()) {
cout << "Stack Overflow\n";
return;
}
arr[++top] = value;
}
int pop() {
if (isEmpty()) {
cout << "Stack Underflow\n";
return -1;
}
return arr[top--];
}
int peek() {
if (isEmpty()) {
cout << "Stack is empty\n";
return -1;
}
return arr[top];
}
void display() {
if (isEmpty()) {
cout << "Stack is empty\n";
return;
}
for (int i = top; i >= 0; i--)
cout << arr[i] << " ";
cout << endl;
}
};
int main() {
Stack s;
s.push(10); // 10
s.push(20); // 10 20
s.push(30); // 10 20 30
s.display();
cout << "Popped: " << s.pop() << endl; // 10 20
s.display();
}
Queue
FIFO
Queue은 줄을 서는 방식과 유사한 자료구조이다.
FIFO (First In First Out, 선입선출) 방식으로, 가장 먼저 들어온 데이터가 가장 먼저 나간다.
한 쪽에서만 연산이 이루어지는 Stack과 다르게 Queue는 두 쪽에서 연산이 이루어진다.
변수 'front'와 'rear'를 선언하며, 각각 Queue의 가장 앞(먼저 온 쪽)과 가장 뒤(나중에 온 쪽)를 가리키게 된다.
최초 구현 시, 변수 'front'와 'rear'를 -1로 초기화하여 빈 Queue를 만든다.
Element를 추가할 경우, 'rear' 값이 1 증가하며 Element를 처음 추가하면 추가로 'front' 값을 0으로 한다.
Element를 제거할 경우, 현재 'front'가 가리키는 가장 앞의 Element를 제거하고 'front' 값이 1 증가한다.
마찬가지로 Array와 Linked List 모두 구현이 가능하며, Array 방식을 사용하여 구현할 경우 Buffer의 구현 방식에 따라 다시 두 종류로 나눌 수 있다.
- Non-Circular buffer
- Circular buffer
주요 연산
- enqueue (or insert) : Queue의 가장 뒤에 Element를 추가
- dequeue (or delete) : Queue의 가장 앞의 Element를 제거하고 값을 반환
- peek (or front) : Queue의 가장 앞의 Element를 반환 (제거는 하지 않음)
- isEmpty (or queue_empty) : Queue가 비어 있는지 확인
- isFull (or queue_full) : Queue가 가득 차 있는지 확인
주요 사용 예시
- 프린터 인쇄 작업 대기열
- 운영체제의 프로세스 스케줄링
- 네트워크 패킷 처리
C++ 예시 코드
#include <iostream>
#define SIZE 5 // Stack size
using namespace std;
class Queue {
private:
int arr[SIZE]; // Array 기반
int front, rear;
public:
Queue() {
front = -1;
rear = -1;
} // 초기화
bool isEmpty() { return front == -1; }
bool isFull() { return rear == SIZE - 1; }
void enqueue(int value) {
if (isFull()) {
cout << "Queue Overflow\n";
return;
}
if (isEmpty()) front = 0;
arr[++rear] = value;
}
int dequeue() {
if (isEmpty()) {
cout << "Queue Underflow\n";
return -1;
}
int data = arr[front];
if (front >= rear) { // 마지막 요소 제거 시 초기화
front = -1;
rear = -1;
}
else {
front++;
}
return data;
}
int peek() {
if (isEmpty()) {
cout << "Queue is empty\n";
return -1;
}
return arr[front];
}
void display() {
if (isEmpty()) {
cout << "Queue is empty\n";
return;
}
for (int i = front; i <= rear; i++)
cout << arr[i] << " ";
cout << endl;
}
};
int main() {
Queue q;
q.enqueue(10); // 10
q.enqueue(20); // 10 20
q.enqueue(30); // 10 20 30
q.display();
cout << "Dequeued: " << q.dequeue() << endl; // 20 30
q.display();
}
Circular Queue
Circular Queue는 Queue의 가장 앞과 가장 뒤가 원형으로 연결된 자료구조이다.
일반적 Queue에서 Element를 제거할 경우 기존 'front'가 가리키던 공간을 사용할 수 없게 된다.
Circular Queue는 Queue의 공간 낭비를 해결하여 고정된 크기에서 효율적인 공간 활용이 가능하다.
Circular Queue에서 Element를 추가할 경우, 단순히 'rear' 값을 1 증가시키는 대신, (rear + 1) % SIZE를 사용한다.
이를 통해 'rear' 값이 SIZE보다 같거나 커질 경우 비어있는 'front' 자리를 사용할 수 있다.
Circular Queue에서 Element를 제거할 경우에도 (front + 1) % SIZE를 사용하며,
Circular Queue가 가득 찬 상태는 (rear + 1) % SIZE == front 인 경우이다.
C++ 예시 코드
#include <iostream>
#define SIZE 5 // Stack size
using namespace std;
class CircularQueue {
private:
int arr[SIZE]; // Array 기반
int front, rear;
public:
CircularQueue() {
front = -1;
rear = -1;
} // 초기화
bool isEmpty() { return front == -1; }
bool isFull() { return (rear + 1) % SIZE == front; }
void enqueue(int value) {
if (isFull()) {
cout << "Circular Queue Overflow\n";
return;
}
if (isEmpty()) front = 0;
rear = (rear + 1) % SIZE;
arr[rear] = value;
}
int dequeue() {
if (isEmpty()) {
cout << "Circular Queue Underflow\n";
return -1;
}
int data = arr[front];
if (front == rear) { // 마지막 요소 제거 시 초기화
front = -1;
rear = -1;
}
else {
front = (front + 1) % SIZE;
}
return data;
}
int peek() {
if (isEmpty()) {
cout << "Queue is empty\n";
return -1;
}
return arr[front];
}
void display() {
if (isEmpty()) {
cout << "Circular Queue is empty\n";
return;
}
int i = front;
while (true) {
cout << arr[i] << " ";
if (i == rear) break;
i = (i + 1) % SIZE;
}
cout << endl;
}
};
int main() {
CircularQueue cq;
cq.enqueue(10); // 10
cq.enqueue(20); // 10 20
cq.enqueue(30); // 10 20 30
cq.enqueue(40); // 10 20 30 40
cq.enqueue(50); // 10 20 30 40 50
cq.display();
cout << "Dequeued: " << cq.dequeue() << endl; // 20 30 40 50
cq.enqueue(60); // 20 30 40 50 60 (front = 1, rear = 0)
cq.display();
}
