스택(Stack)과 큐(Queue), python

이미지 출처 : https://medium.com/omarelgabrys-blog/stacks-and-queues-d96c6f35fae3

스택(Stack)

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

- 입구와 출구가 동일한 형태이다.

스택 구현

파이썬에서의 스택 구현은 리스트를 활용하여 구현할 수 있다.

stack = []

# 삽입(5) > 삽입(2) > 삽입(3) > 삽입(7) > 삭제() > 삽입(1) > 삽입(4) > 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

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

>> [1, 3, 2, 5]
   [5, 2, 3, 1]


# pop() 연산은 괄호안에 인덱스를 추가하여, 인덱스 번호에 해당하는 원소를 빼낼 수 있다.

참고(c++, java)

c++

#include <bits/stdc++.h>

using namespace std;

stack<int> s;

int main(void) {
	s.push(5);
    s.push(2);
    s.push(3);
    s.push(7);
    s.pop();
    s.push(1);
    s.push(4);
    s.pop();
    
    // 스택의 최상단 원소부터 출력
    while (!s.empty()) {
    	cout << s.top() << ' ';
        s.pop();
    }
}

 

Java

import java.util.*;

public class Main {
	
    public static void main(String[] args) {
    	Stack<Integer> s = new Stack<>();
        
        s.push(5);
        s.push(2);
        s.push(3);
        s.push(7);
        s.pop();
        s.push(1);
        s.push(4);
        s.pop();
        
        while (!s.empty()) {
        	System.Out.print(s.peek() + " ");
            s.pop();
        }
    }
}

 

큐(Queue)

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

- 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태이다.

- 큐는 일종의 대기열로 생각할 수 있다.

큐(queue) 구현

파이썬에서의 큐 또한 리스트로 구현할 수 있지만 리스트로 구현할 시 시간복잡도 O(N) 이기 때문에, 시간복잡도가 O(1)인 deque 라이브러리를 사용하여 구현한다.

from collections import deque

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

# 삽입(5) > 삽입(2) > 삽입(3) > 삽입(7) > 삭제() > 삽입(1) > 삽입(4) > 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue)

>> deque([3, 7, 1, 4])
   deque([4, 1, 7, 3])

참고(c++, java)

c++

#include <bits/stdc++.h>

using namespace std;

queue<int> q;

int main(void) {
	q.push(5);
    q.push(2);
    q.push(3);
    q.push(7);
    q.pop();
    q.push(1);
    q.push(4);
    q.pop();
    
    while (!q.empty()) {
    	cout << q.front << ' ';
        q.pop();
    }
}


>> 3 7 1 4

 

Java

import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        
        q.offer(5);
        q.offer(2);
        q.offer(3);
        q.offer(7);
        q.poll();
        q.offer(1);
        q.offer(4);
        q.poll();
        
        while (!q.isEmpty()) {
            System.out.print(q.poll() + " ");
        }
    }
}


>> 3 7 1 4

 

본 포스팅은 나동빈님의 알고리즘 강의를 참고하였습니다.