자료구조 및 알고리즘 5 - Queue and Stack

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다.

 

 

 

 

0. Queue and Stack

 

0.1 Queue

 

Insert 와 Delete 만을 제공하는 자료구조 입니다. Queue 의 매우 주요한 특징으로는 FIFO(* First In First Out) 입니다. 앞서 봤던 Sorted Packed Array 같은 자료구조들과 달리 LinkedList 를 기반으로 합니다. LinkedList 의 특징을 통해 Queue 의 각 수행들은 매우 빠른 성능을 보입니다. 실제로 빨라야 하는 수행이기도 합니다.

Queue 는 생각보다 많은 곳에 쓰이지는 않지만 알고있으면 유용한 순간들이 있습니다.

 

0.1.1 성능

 

• Insert : O(1)
• Delete: O(1)

 

0.2 Stack

 

Queue 와 마찬가지로 Insert 와 Delete 만을 제공하는 자료구조 입니다. Stack 의 매우 중요한 특징으로는 FILO(* First In Last Out) 입니다. LinkedList 와 비슷하게 포인터 개념을 사용하는 자료구조입니다. Queue 와 마찬가지로 각 수행들은 매우 빠른 성능을 보이고 이 수행들은 실제로 빨라야 하는 수행들이기도 합니다.

Stack 은 Queue 보다 매우 많은 곳이 사용됩니다. 처음 들어간 것이 마지막에 나온다는 특이한 성질 덕분에 순서를 바꾼다던지 웹 페이지의 뒤로가기 기능들에 사용됩니다.

 

0.2.1 성능

 

• Insert: O(1)
• Delete: O(1)

 

 

 

1. 구현

 

1.1 Queue 의 구현

 

Head ->
	3
Tail ->	2

 

Head 와 Tail 포인터를 이용하여 구성되는 자료구조입니다. Tail 은 가장 마지막 값이자, 가장 처음 들어왔던 값으로 만약 Queue 에서 poll() 을 한다면 가장 먼저 나가는 요소입니다. Head 는 가장 처음 값이자 Queue 에서 add() 를 했을 때 요소가 들어가는 자리를 가르킵니다. 

 

이때 생각해야 할 점이 있습니다.

 

Queue 가 꽉 찼다는 것은 어떻게 표현할 수 있을까?

Queue 가 비었다는 것은 어떻게 표현할 수 있을까?

 

Queue 가 비었다면 Tail 이 가르키는 곳과 Head 가 가르키는 곳이 같은 것입니다.

(* Head == Tail -> empty)

 

Queue 가 꽉 찼다면 Head 는 한 바퀴 돌아 Tail 을 가르키고 있을겁니다.

(* Head == Tail -> full)

 

그렇다면 꽉찬 경우와 비어있는 경우가 Head 와 Tail 의 상태가 같은데 이를 어떻게 구분할까

 

정답은 "한 칸 사용을 안하는 것" 입니다.

즉 Head 가 Tail 보다 한 칸 아래에 있다면 이는 full 로 간주합니다.

Head 와 Tail 이 같은 곳을 가르킨다면 이는 empty 로 간주합니다.

 

class Queue {
private:
	int tail;
    int head;
    int* array;
    int capa;
    
public:
	Queue(int initCapacity)
    : array{new int[initCapacity]}, tail{0}, head{0}, capa{initCapacity} {}
    
    ~Queue()
    {
    	delete[] array;
    }
    
    int add(int x)
    {
    	if(isFull())
        	return -1;
            
    	array[head] = x;
        head = (head + 1) % capa;
        return 0;
    }
    
    int poll()
    {
    	if(isEmpty)
        	return -1;
            
        int result = array[tail];
        tail = (tail + 1) % capa;
        return result;
    }
    
    bool isFull()
    {
    	if(head < tail)
        {
        	if(((head + 1) % capa) == tail)
            	return true;
        }
        else
        {
        	if(((tail + 1) % capa) == head)
            	return true;
        }
        
        return false;
    }
    
    bool isEmpty()
    {
    	if(head == tail)
        	return true;
            
        return false;
    }
}

 

 

 

 

1.2 Stack 의 구현

 

Top ->
	3
	2
	1

 

Top 포인터를 이용하여 구현하는 자료구조 입니다. 이는 Queue 보다 생각할 것들은 적습니다. Top 이 index 를 넘어가면 full, Top 이 처음을 가르키면 empty 이고, 값을 추가할 때는 Top 에 요소를 추가, 값을 빼낼 때는 Top 아래에 있는 값을 빼냅니다.

 

class Stack {
private:
	int top;
    int capa;
    int* array;
    
public:
	Stack(int initCapacity)
    : array{new int[initCapacity]}, top{0}, capa{initCapacity} {}
    
    ~Stack()
    {
    	delete[] array;
    }
    
    int add(int x)
    {
    	if(isFull)
        	return -1;
        
        array[top] = x;
        top++;
    }
    
    int pop()
    {
    	if(isEmpty)
        	return -1;
        
        int result = array[top];
        top--;
        return result;
    }
    
    bool isFull()
    {
    	if(top == capa)
        	return true;
            
        return false;
    }
    
    bool isEmpty()
    {
    	if(top == 0)
        	return true;
            
        return false;
    }
}

 

 

 

 

2. Application of Stack and Queue

 

Stack 과 Queue 의 대표적인 활용은 미로찾기 입니다.

백준 문제풀이 중 Queue 를 활용하여 최소 거리 탐색을 했으니 이번에는 Stack 을 활용하여 미로의 깊이 우선 탐색을 구현해 보겠습니다.

 

 

2.1 Queue 활용

2024.04.01 - [자바[JAVA]] - BOJ(백준 온라인 저지) 2178번 with 자바[JAVA]

 

 

2.2 Stack 활용

 

미로가 다음과 같은 형식으로 주어진다 가정했을 때 굳이 최단거리로 갈 필요 없이 해결하라 한다면 DFS , Stack 을 사용할 수 있습니다.

 

5 10

0 1 0 0 1 0 1 1 0 0

0 0 0 0 0 0 0 0 0 1

1 0 0 0 1 1 1 0 1 1

1 1 1 1 1 1 1 0 0 1

0 0 0 0 0 0 0 0 0 0

 

(* 0 은 지나갈 수 있는 길, 1 은 벽)

(* visited 행렬을 이용할 수 있지만 그냥 사용하지 않는 방식으로 하겠습니다.)

 

우선 행렬의 크기를 입력받고 미로 행렬을 만들어줍니다.

 

그리고 시작위치 (0,0) 에서 시작해서 (4,9) 까지 가면 성공입니다.

 

시작위치에서 갈 수 있는 동 서 남 북 방향을 찾고 갈 수 있으면 바로 이동합니다.

만약 이동하다가 결국 막힌다면 다시 뒤로 돌아와 동 서 남 북 방향을 찾고 갈 수 있으면 바로 이동합니다.

 

다시 뒤로 돌아오는 기능은 Stack 을 통해 구현할 수 있습니다.

 

비교적 간단하니 바로 코드를 보겠습니다.

 

#include <iostream>
#include <stack>

int main()
{
	int dr[] = {0, 0, 1, -1};
    int dc[] = {1, -1, 0, 0};

	int N, M;
    
    std::cin >> N;
    std::cin >> M;
    
    int** maze;
    maze = new int*[N];
    for(int i=0; i<N; i++)
    	maze[i] = new int[M];
        
    for(int i=0; i<N; i++)
    	for(int j=0; j<M; j++)
        	std::cin >> maze[i][j];
            
    std::stack<int*> stack;
    
    int* nowPos = new int[2];
    int nowRow = 0;
    int nowCol = 0;

    nowPos[0] = nowRow;
    nowPos[1] = nowCol;
    maze[nowRow][nowCol] = 9;
    
    stack.push(nowPos);
    
    while(nowRow != N-1 || nowCol != M-1)
    {
        if(stack.empty())
            return -1;
        
        bool flag = false;
        
        for(int i=0; i<4; i++)
        {
        	int nextRow = nowRow + dr[i];
            int nextCol = nowCol + dc[i];
            
            if(nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= M)
            	continue;
                
            if(maze[nextRow][nextCol] != 0)
            	continue;
                
            flag = true;
            
            int* nextPos = new int[2];
            nextPos[0] = nextRow;
            nextPos[1] = nextCol;
            stack.push(nextPos);
            
            nowRow = nextRow;
            nowCol = nextCol;
            
            maze[nowRow][nowCol] = 9;
            break;
        }
        
        if(!flag)
        {
            if(stack.empty())
                return -1;
            
        	maze[nowRow][nowCol] = 8;
        
        	int* nextPos= stack.top();
            nowRow = nextPos[0];
            nowCol = nextPos[1];
            stack.pop();
        }
    }
    
    for(int i=0; i<N; i++)
    {
    	for(int j=0; j<M; j++)
        	std::cout << maze[i][j] << " ";
        std::cout << std::endl;
    }
    
    for(int i=0; i<N; i++)
    	delete[] maze[i];
    delete[] maze;
}