자료구조 - 스택, 큐

강의 소개

현재 수강하고 있는 멀티캠퍼스 k-digital 지능형 웹서비스 풀 스택 과정을 수강하며 적은 내용입니다.

교재로는 자료구조와 함께 배우는 알고리즘 입문 자바 편을 사용하고 있습니다.

---

 

1.  스택(Stack)

먼저 들어온 데이터가 나중에 나가는 형식(FILO)의 자료구조이다.

입구와 출구가 동일한 형태로 볼 수 있다. 통로가 1개이기 때문에 가장 나중에 들어온 데이터가 가장 빨리 나가는 것이다.

ex. 접시 쌓기, 박스 쌓기

 

언어별 스택 구현

자바

자바의 java.util.Stack을 사용한다.

 

-메서드

push: 스택에 데이터 저장

pop: 스택에서 데이터 하나를 꺼내서 삭제한다.

isEmpty: 스택이 비어있는지 여부를 boolean타입으로 반환한다.

peek: 스택의 꼭대기 top을 조회한다.

top부터 조회할 수 있다. 아래를 조회하려면 top부터 하나씩 삭제하며 내려와서 가장 아래인 bottom에도 데이터가 없으면 스택이 비어있는 것이다. (stack empty)

 

Stack<Integer> stack = new Stack<Integer>();

// 삽입(3) - 삽입(1) - 삭제() - 삽입(2)
stack.push(3);
stack.push(1);
stack.pop();
stack.push(2);

// 스택의 최상단 원소부터 출력
while(! stack.isEmpty()) {
	System.out.print(stack.peek() + " "); // 2 3
    stack.pop();
}

 

 

파이썬

파이썬에서는 기본적으로 제공되는 객체인 리스트를 그대로 사용해서 스택을 구현할 수 있다.

리스트에서는 append로 삽입, pop으로 삭제를 할 수 있다.

stack = []

stack.append(1)  # 삽입(꼭대기)
stack.pop()  # 삭제

print(stack([::-1]))  # 최상단 원소부터 출력
print(stack)  # 최하단 원소부터 출력

 

---

 

2.  큐(Queue)

먼저 들어온 데이터가 먼저 나가는 형식(FIFO)의 자료구조이다.

 

 

언어별 큐 구현

자바

java.util.PriorityQueue

java.util.LinkedList

자바에서 큐를 구현할 때는, LinkedList(연결 리스트) 내에서 구현되어 있는 큐를 사용하는 것이 일반적이다.

삽입할 때는 offer를, 원소를 삭제할 때는 poll메서드를 사용한다. 또한, 이 poll메서드는 원소를 꺼내서 확인 후 반환하는 역할도 한다.

import java.util.*;

public class Main {
	
    public static void main(String[] args) {
    	Queue<Integer> q = new LinkedList<>();
        
        // 삽입(2) - 삽입(3) - 삭제() - 삽입(1) - 삭제() - 삽입(5)
        q.offer(2);
        q.offer(3);
        q.poll();
        q.offer(1);
        q.poll();
        q.offer(5);
        
        // 먼저 들어온 원소부터 추출
        while (!q.isEmpty()) {
        	System.out.println(q.poll() + " ");
        }
    	// 1 5
    }

}

 

 

파이썬

파이썬에서 큐를 구현할 때는, deque라이브러리를 사용한다.

(파이썬에서 기본적으로 제공하는 자료형인 list를 그대로 사용하는 것보다 deque를 사용하는 것이 시간상 이득이다.)

원소를 삽입할 때는 가장 오른쪽 위치에 원소를 추가하는 append메서드를 사용한다.

또한, 삭제할 때는 가장 왼쪽에 있는 데이터를 꺼내는 popleft메서드를 사용한다.

from collections import deque

# 큐 구현을 위해 deque라이브러리를 사용
queue = deque()

# 삽입(5) - 삽입(1) - 삽입(2) - 삭제() - 삭제() - 삽입(3)
queue.append(5)
queue.append(1)
queue.append(2)
queue.popleft()
queue.popleft()
queue.append(3)

# 먼저 들어온 순서대로 출력
print(queue) # deque([2, 3])

# 역순으로 바꾸기
queue.reverse()
print(queue) # 나중에 들어온 원소부터 출력