[알고리즘] Stack과 Queue

Stack

LIFO(Last In First Out, 후입선출) 의 자료구조

Stack 을 생각할 때에는 위 GIF 처럼 쌓인 책을 생각하시면 됩니다.

쌓을 때
아래에서 위로 하나씩 쌓임

가져갈 때
위에 있는 것부터 가져감
** 가장 처음 들어온 책이 가장 나중에 가져가게 됨

이 방식을 LIFO(후입선출)의 방식이라고 합니다.

stacked 자체도 쌓인 이라는 의미를 가지고 있습니다.

Stack 용어 정리

용어	설명
top	스택의 가장 윗부분 (꼭대기)
bottom	스택의 가장 아랫부분 (바닥)
push(item)	데이터를 넣는 작업
pop()	데이터를 꺼내는 작업
peek()	스택의 가장 위에 있는 항목 조회
empty()	비어있는지 확인

구현 (1) - STL

#include <iostream>
#include <stack>

using namespace std;

int main(){

	// 스택 생성
	stack<int> s;


	// 데이터 추가 
	s.push(3); // 3
	s.push(2); // 3, 2
	s.push(1); // 3, 2, 1


	// 가장 마지막으로 들어온 값이 1이기 때문에 1 출력 
	cout << "top element: " << s.top() << '\n';


	// pop
	s.pop(); // 1 삭제 3 2
	s.pop(); // 2 삭제 3


	// size, 현재 stack 에 3만 있기 때문에 1
	cout << "stack size: " << s.size() << '\n';


	// empty, stack 에 3이 있기 때문에 empty 아님 
	cout << "Is it empty?: " << (s.empty() ? "Yes" : "No") << '\n';

	return 0;
}

구현 (2) - 배열

#include <iostream>
#define stack_size 100
using namespace std;
 
// stack 구조체 생성
struct stack {
    int top = -1;
    int arr[stack_size];
    
    void push(int data) {
        // 데이터 추가
        if (top == stack_size-1) {
            cout << "stack is full" << endl;
            return;
        }
        arr[++top] = data;
    }
    
    int pop() {
        // 데이터 꺼내기
        if (empty()) {
            cout << "stack is empty" << endl;
            return -1;
        }
        return arr[top--];
    }
    
    int peek() {
        // 가장 위에 있는 데이터 출력
        if (empty()) {
            cout << "stack is empty" << endl;
            return -1;
        }
        return arr[top];
    }
    
    bool empty() {
        // stack empty 여부 확인
        return top <= -1;
    }
};

int main() {
    stack st;
    
    //현재 스택은 비워져있는 상태
    cout << "is stack empty? "<< st.empty() << endl;
    cout << st.pop() << endl;
    cout << st.peek() << endl;
 
    //for 루프가 돌면 스택은 1개만 저장 가능한 상태
    // 1 ~ 99 까지 저장 되어 있음
    for (int i = 0; i < stack_size-1; i++) st.push(i + 1);

    cout << endl;
    cout << "after for loop"<<endl;
    st.push(15);  // 1 ~ 99, 15
    st.push(120); // 스택이 전부 채워져 있어서 값을 넣을 수 없음
    st.pop();     //스택에서 한 개(15)가 비워짐, 1개 채울 수 있는 상태
 
    st.push(120); // 1 ~ 99, 120
 
    cout<<endl;
    
    //스택이 비워지면 while루프 종료
    while(!st.empty()) cout << st.pop() << endl;
}

구현 (3) - 연결리스트

#include <iostream>
 
using namespace std;
 
// Node 구조체 선언
struct Node {
    int data;
    Node* next;
};
 
Node* top = NULL;
 
// top 에 데이터 추가
void push(int data) {
    // 1. Node struct 를 만들고
    // 2. 현재 top 에 있는 데이터를 next 로 설정
    // 3. top 에 현재 데이터로 설정
    
    // EX ) top -> [1] -> [2] -> [3] 으로 연결리스트가 설정되어 있을 때 0 값을 push 하게 되면
    // top -> [0] -> [1] -> [2] -> [3] 의 형식으로 연결리스트가 설정됨
    Node* node = new Node();
    node->data = data;
    node->next = top;
    top = node;
}
 
// 가장 top 에 있는 데이터 출력
void Top() {
    if (top != NULL) {
        cout << "top : " << top->data;
    }
    else {
        cout << "top is NULL";
    }
    cout << endl;
}
 
// 가장 top 에 있는 데이터를 꺼냄
void pop() {
    if (top == NULL) {
        cout << "stack underflow" << endl;
    }
    else {
        cout << "pop : " << top->data << endl;
        top = top->next;
    }
}
 
// 현재 연결리스트 데이터 출력
void display() {
    Node* ptr;
    if (top == NULL) {
        cout << "stack is empty";
    }
    else {
        ptr = top;
        cout << "stack element : ";
        while (ptr != NULL) {
            cout << ptr->data << " ";
            ptr = ptr->next;
        }
    }
    cout << endl;
}
 
int main() {
 
    // 현재 stack 연결리스트에 저장되어 있는 값이 없음
    display();
    Top();
 
    push(1); // 1 추가 top -> [1]
    push(2); // 2 추가 top -> [2] -> [1]
    push(3); // 3 추가 top -> [3] -> [2] -> [1]
    
    display(); // 3 2 1 출력
    Top(); // top 에 연결되어 있는 값인 3 출력
 
    pop(); // 3 꺼냄 top -> [2] -> [1]
    pop(); // 2 꺼냄 top -> [1]
 
    display(); // 1 출력
    Top(); // top 에 연결되어 있는 값인 1 출력
 
    push(5); // 5 추가 top -> [5] -> [1]
 
    display(); // 5 1 출력
    Top(); // top 에 연결되어 있는 값인 5 출력
 
    return 0;
}

스택의 사용 사례

1. 재귀 알고리즘
   재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
   재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때 스택에 넣어 두었던 임시 데이터를 꺼낸다.
2. 메소드 호출 스택
3. 웹 브라우저 방문기록 (뒤로가기)
4. 실행 취소(undo)
5. 역순 문자열 만들기
6. 후위 표기법 계산
7. 수식의 괄호 검사

Queue

FIFO (First In First Out, 선입선출) 의 자료구조

Queue 를 생각할 때에는 극장 혹은 뭔가를 하기 위한 대기 줄을 생각하시면 됩니다. 대기 줄 같은 경우에는 먼저 온 순서대로 일이 진행되는데요. 이 방식을 FIFO(선입선출) 이라고 합니다.

Queue 를 번역해봤을 때에도 대기 줄이라는 뜻을 가지고 있습니다.

Queue 용어 정리

용어	설명
front	데이터를 꺼내는 쪽(맨 앞)
rear	데이터를 넣는 쪽(맨 뒤)
enqueue(item)	데이터를 넣는 작업
dequeue()	데이터를 꺼내는 작업
peek()	큐의 가장 앞에 있는 항목 조회

구현 (1) - STL

#include <iostream>
#include <queue>

using namespace std;

int main(){

    // 큐 생성
    queue<int> q;

    // push
    q.push(1); // 1
    q.push(2); // 1 2
    q.push(3); // 1 2 3
    q.push(4); // 1 2 3 4
    q.push(5); // 1 2 3 4 5
    q.push(6); // 1 2 3 4 5 6

    // pop
    q.pop(); // 1
    q.pop(); // 2
    q.pop(); // 3

    // 현재 스택 4 5 6
    cout << "front element: " << q.front() << endl; // 가장 앞에 있는 값 -> 4
    cout << "back element: " << q.back() << endl; // 가장 뒤에 있는 값 -> 6
    cout << "queue size: " << q.size() << endl; // 큐 사이즈 -> 3
    cout << "Is it empty?: " << (q.empty() ? "Yes" : "No") << endl;

    return 0;
}

구현 (2) - 배열

#include <iostream>
 
using namespace std;
int queue[100];
int n = 100;
int front = -1; // 데이터를 꺼내는 위치를 저장하고 있는 변수
int rear = -1; // 데이터를 넣는 위치를 저장하고 있는 변수
 
void insert(int data) { // queue 에 데이터 추가
    if (rear == n - 1) {
        // 더이상 데이터를 넣을 수 없는 경우
        cout << "queue overflow" << endl;
    } else {
        if (front == -1) {
            // front 를 처음 초기화 할 때 0 으로 초기화 하는 경우 empty 인지 확인이 어렵기 떄문에
            // insert 를 했을 때 front 값을 0으로 바꿔준다.
            front = 0;
        }
 
        cout << "insert : " << data << endl;
        queue[++rear] = data; // 배열의 마지막에 추가
    }
}
 
void del() { // queue 에서 데이터 꺼내기
    if (front == -1 || front > rear) {
        cout << "queue underflow" << endl;;
    } else {
        // 배열의 맨 처음에 있던 값을 꺼냄
        cout << "delete : " << queue[front++] << endl;;
    }
}
 
void display() {
    // 현재 queue 에 있는 값들 출력
    if (front == -1) {
        cout << "queue is empty" << endl;
    } else {
        cout << "queue element : ";
        for (int i = front; i <= rear; i++) {
            cout << queue[i] << " ";
        }
        cout << endl;
    }
}
 
int main() {
    display();
 
    insert(1); // [1]
    insert(2); // [1,2]
    insert(3); // [1,2,3]
 
    display();
 
    del(); // [2,3]
    del(); // [3]
 
    display();
 
    insert(5); // [3,5]
 
    display();
 
    return 0;
}

구현 (3) - 연결리스트

#include <iostream>
 
using namespace std;
 
// node 구조체 선언
struct node {
    int data;
    node* next;
};
 
node* front = NULL; // 꺼내야 하는 노드
node* rear = NULL; // 데이터를 추가해야 하는 노드
node* temp;
 
void insert(int data) {
    // queue 에 데이터 추가
    cout << "insert : ";
    if (rear == NULL) {
        // 아무 데이터가 없는 경우
        // node 를 만들고 rear 및 front 로 추가
        rear = new node();
        rear->next = NULL;
        rear->data = data;
        front = rear;
    } else {
        // queue 에 데이터가 있는 경우
        // 현재 있는 rear 뒤에 추가해준다.
        temp = new node();
        rear->next = temp; //끝에 추가하는 거니까
        temp->data = data;
        temp->next = NULL;
        rear = temp;
    }
    cout << data << endl;
}
 
void del() {
    // queue 에서 데이터 꺼내기
    if (front == NULL) {
        cout << "queue underflow";
    } else {
        temp = front;
        if (temp->next != NULL) {
            // queue 에 데이터가 두개 이상인 경우
            // front 에 연결되어 있는 다음 값을 front 로 할당해줌.
            temp = temp->next;
            cout << "delete : " << front->data;
            free(front);
            front = temp;
        } else {
            // front에만 원소가 있는 경우
            // front node 를 할당 취소
            cout << "delete : " << front->data;
            free(front);
            front = NULL;
            rear = NULL;
        }
    }
    cout << endl;
}
 
void display() {
    // queue 에 있는 값들 모두 출력
    if ((front == NULL) && (rear == NULL)) {
        cout << "queue is empty";
    } else {
        temp = front;
        cout << "queue element : ";
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
    }
    cout << endl;
}
 
int main() {
    display();
 
    insert(1); // [1]
    insert(2); // [1] -> [2]
    insert(3); // [1] -> [2] -> [3]
 
    display(); // 1 2 3
 
    del(); // 1 node 삭제
    del(); // 2 node 삭제
 
    display(); 3
 
    insert(5); // [3] -> [5]
 
    display(); 3 5
 
    return 0;
}

사용 예

1. 너비 우선 탐색(BFS, Breadth-First-Search) 구현
2. 처리해야할 노드의 리스트를 저장하는 용도로 큐를 사용
3. 캐시 구현
4. 우선순위가 같은 작업 예약 (인쇄 대기열)
5. 선입선출이 필요한 대기열 (티켓 카운터)
6. 콜센터 고객 대기시간
7. 프린터의 출력 처리
8. 은행 업무
9. 프로세스 스케쥴링
10. 네트워크 패킷 처리

백준 문제

10828번 스택
1874번 스택 수열
10845번 큐

🙇🏻‍♀️ 레퍼런스

[자료구조/알고리즘] - 스택, 큐