📖스택
스택(Stack)은 후입선출(LIFO - Last In First Out)의 특성을 가지는 자료구조이다. 즉, 제일 마지막에 넣은 데이터가 제일 먼저 빠져나올 수 있다. 한 방향으로만 데이터를 넣고 뺄 수 있는 선형 구조이다. 프링글스 통을 생각하면 쉽다.
데이터를 스택에 넣는 것을 push, 스택에서 빼는 것을 pop이라고 한다.
📁스택의 기본 함수
C++의 STL은 스택에 대한 여러 함수를 제공한다. 먼저, 스택에 대한 헤더파일을 가져오고, stack이라는 이름으로 int형 데이터를 저장하는 스택을 생성하면 다음과 같다.
#include <stack> stack<int> stack;
위의 코드처럼 'stack<데이터 타입> 스택이름'으로 스택을 생성할 수 있다. STL에서 제공하는 기본 함수는 다음과 같은 것들이 있다.
stack.push(element) //데이터 삽입 stack.pop() //데이터 삭제 stack.top() //스택에서 제일 위에 있는(최근에 저장된) 데이터 반환 stack.empty() //스택이 비어있는지 확인 stack.size() //스택의 현재 크기 반환
📁스택 구현(C++)
배열을 이용하여 직접 스택을 구현해보면 다음과 같다.
template<class T> class Stack
{
private:
int top; //가장 마지막에 저장된 데이터의 위치
int size; //스택의 크기
T *stack; //데이터를 저장할 동적 배열
public:
Stack() //스택 생성
{
size = MAXVALUE;
stack = new T[size];
top = -1;
}
~Stack() // 스택 삭제
{
delete[] stack;
}
void push(T value)
{
if(!isFull()) {
stack[++top] = value;
}
else {
cout << "Stack is Full" << endl;
}
}
void pop()
{
if(!empty()) {
top--;
}
else {
cout << "Stack is Empty" << endl;
}
}
T Top()
{
if(!empty()) {
return stack[top];
}
else {
return "Stack is Empty" << endl;
}
}
int size()
{
return top + 1;
}
bool empty()
{
return top == -1;
}
bool isFull()
{
return top + 1 == size;
}
};📖큐
큐(Queue)는 선입선출(FIFO - First In First Out)의 특성을 가지는 자료구조이다. 즉, 제일 처음에 넣은 데이터가 제일 먼저 빠져나올 수 있다. 먼저 줄에 선 사람이 먼저 나갈 수 있는 것을 생각하면 쉽다.
큐는 한쪽에서 데이터를 삽입하고, 반대쪽에서 데이터를 삭제한다. 새로운 데이터를 삽입하는 쪽을 rear 또는 tail이라고 하고, 저장되어있던 데이터를 삭제하는 쪽을 front 또는 head라고 한다.
📁큐의 기본 함수
C++의 STL은 큐에 대한 함수도 제공한다. 큐에 대한 헤더파일을 가져오고, q라는 이름으로 int형 데이터를 저장하는 큐를 생성하면 다음과 같다.
#include <queue> queue<int> q;
위의 코드처럼 'queue<데이터 타입> 큐이름'으로 큐를 생성할 수 있다. STL에서 제공하는 기본 함수는 다음과 같은 것들이 있다.
q.push(element) //데이터 삽입 q.pop() //데이터 삭제 q.front() //큐에서 제일 앞에 저장한 데이터 반환 q.back() //큐에서 제일 끝에 저장한(최근에 저장한) 데이터 반환 q.size() //큐의 현재 크기 반환 q.empty() //큐가 비어있는지 확인
📁큐 구현(C++)
배열을 이용하여 직접 큐를 구현해보면 다음과 같다.
template<class T> class Queue
{
private:
int front; //첫번째 데이터의 위치
int rear; //마지막 데이터의 위치
int size; //큐의 크기
T *queue; //큐를 저장할 동적 배열
public:
Queue() //큐 생성
{
size = MAXVALUE;
queue = new T[size];
front = 0;
rear = 0;
}
~Queue() //큐 삭제
{
delete[] queue;
}
void push(T value)
{
if(!isFull()) {
rear = (rear + 1) % size;
queue[rear] = value;
}
else {
cout << "Queue is Full" << endl;
}
}
void pop()
{
if(!empty()) {
front = (front + 1) % size;
}
else {
cout << "Queue is Empty" << endl;
}
}
bool empty()
{
return front == rear;
}
bool isFull()
{
return (rear + 1) % size == front;
}
};