[자료구조] 스택(Stack) / 큐(Queue)

1. 스택(Stack)

• 선입후출(FILO) 자료구조
  • 먼저 들어온 데이터가 나중에 나가는 형식
    

    

• 구현 방법
  • Python: append(), pop() 메소드 사용
    

    stack = []
    
    stack.append(1) # 삽입
    stack.append(2) # 삽입
    stack.append(3) # 삽입
    stack.append(4) # 삽입
    stack.pop() # 삭제
    
    print(stack[::-1]) # 최상단 원소부터 출력, [3, 2, 1]
    print(stack) # 최하단 원소부터 출력, [1, 2, 3]​

  • C++: stack 라이브러리 사용 (push() / pop() / top())
    

    #include <bits/stdc++.h>
    using namespace std;
    
    stack<int> stack;
    
    int main(void) {
        stack.push(1); // 삽입
        stack.push(2); // 삽입
        stack.push(3); // 삽입
        stack.push(4); // 삽입
        stack.pop(); // 삭제
        
        while(!stack.empty()){
        	cout << stack.top() << " "; // 최상단 원소 출력, 3 2 1
            stack.pop(); // 삭제
        }
    }​

  • Java: Stack 라이브러리 사용 (push() / pop() / peek())
    

    import java.util.*;
    
    public class Main {
    	public static void main(String[] args) {
        	Stack<Integer> stack = new Stack<>();
            
            stack.push(1); // 삽입
            stack.push(2); // 삽입
            stack.push(3); // 삽입
            stack.push(4); // 삽입
            stack.pop(); // 삭제
            
            while(!stack.empty()) {
                System.out.println(stack.peek() + " "); // 최상단 원소부터 출력, 3 2 1
                stack.pop(); // 삭제
            }
        }
    }

2. 큐(Queue)

• 선입선출(FIFO) 자료구조
  • 먼저 들어온 데이터가 먼저 나가는 형식
    

    

  • 구현 방법
    • Python: deque 라이브러리 사용 (append(), popleft())
      • 리스트 사용해도 되지만 시간 복잡도를 고려하면 deque 추천
      • 리스트 사용해서 특정 원소 꺼내는 pop()을 호출하면 원소를 꺼낸 뒤 원소의 위치를 조정하는 과정까지 필요하여 O(N) 만큼의 시간 복잡도 발생
        

        from collections import deque
        
        queue = deque()
        
        queue.append(1) # 삽입
        queue.append(2) # 삽입
        queue.append(3) # 삽입
        queue.append(4) # 삽입
        queue.popleft() # 삭제
        
        print(queue) # 먼저 들어온 원소부터 출력, [2, 3, 4]
        queue.reverse() # 역순
        print(queue) # 나중에 들어온 원소부터 출력, [4, 3, 2]

    • C++: stack 라이브러리 사용 (push() / pop() / front())
      

      #include <bits/stdc++.h>
      using namespace std;
      
      queue<int> queue;
      
      int main(void) {
          queue.push(1); // 삽입
          queue.push(2); // 삽입
          queue.push(3); // 삽입
          queue.push(4); // 삽입
          queue.pop(); // 삭제
          
          while(!queue.empty()){
          	cout << queue.front() << " "; // 먼저 들어온 원소부터 출력, 4 3 2
              queue.pop(); // 삭제
          }
      }

    • Java: Stack 라이브러리 사용 (offer() / poll())
      • poll()
        • 대기열에 있는 원소를 하나씩 꺼내는 메소드
        • 꺼낸 원소를 바로 반환하여 출력할 때도 바로 사용 가능
          

          import java.util.*;
          
          public class Main {
          	public static void main(String[] args) {
              	Queue<Integer> queue = new LinkedList<>();
                  
                  queue.offer(1); // 삽입
                  queue.offer(2); // 삽입
                  queue.offer(3); // 삽입
                  queue.offer(4); // 삽입
                  queue.poll(); // 삭제
                  
                  while(!queue.empty()) {
                      System.out.println(queue.poll() + " "); // 먼저 들어온 원소부터 출력, 4 3 2
                  }
              }
          }​