스택(Stack)

스택은 후입선출(LIFO, Last-In-First-Out) 구조를 가진 자료구조입니다. 이는 마지막에 들어간 요소가 가장 먼저 나오는 구조를 의미합니다.

주요 연산:

• push: 스택에 요소를 삽입합니다.
  -> python에서 append()메소드 사용

• pop: 스택에서 가장 위에 있는 요소를 제거하고 그 값을 반환합니다.
  -> 파이썬에서 pop() 메소드 사용

ex) 쟁반을 쌓아놓으면 제일 나중에 놓았던 것을 필요할 때 제일 먼저 가져가게 됨

ex) gmail 메일함, 가장 최근에 받은 이메일은 가장 위에 있다. 그러나 몇시간 전에 받은 이메일은 밑에 있게 된다.

예제)

stack = []
stack.append(1)
stack.append(2)
top_element = stack.pop()
top_element

예제-결과)
2

큐(Queue)

: 큐는 선입선출(FIFO, First-In-First-Out) 구조를 가진 자료구조이다. 이는 처음에 들어간 요소가 가장 먼저 나오는 구조를 의미한다.

ex) 식당 줄에 먼저 선 사람이 제일 처음 음식을 받게되고 그다음 사람이 음식을 받음

주요 연산:

• enqueue : 큐의 뒤쪽에 요소를 추가합니다. (insert연산)
  -> 파이썬에서 put() 메소드

• dequeue : 큐의 앞쪽에서 요소를 제거하고 그 값을 반환합니다. (read&delete연산)
  -> 파이썬에서 get() 메소드

ex) 큐는 프린터의 인쇄 대기열, 운영체제의 작업 스케줄링 등에 사용된다.

선형 큐

: 막대모양으로 된 큐이다. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한칸씩 옮겨야 한다는 단점이 있다.

환형 큐

: 선형 큐의 문제점(배열로 큐를 선언할 시 큐의 삭제와 생성이 계속 일어났을 때, 마지막 배열에 도달한 후 실제로는 데이터공간이 남아있지만 오버플로우가 발생)을 보완한 것이 환형큐이다. front가 큐의 끝에 닿으면 큐의 맨 앞자리로 자료를 보내어 원형으로 연결하는 방식이다.

덱(Deque, Double-Ended Queue)

덱은 양쪽 끝(front, rear)에서 요소의 추가와 제거가 가능한 자료구조이다. 스택과 큐의 특성을 모두 가지고 있다. 중간에 데이터를 삽입하거나 삭제하는 것은 불가능하다.

메소드

• append(x) : 데크의 오른쪽에 x를 추가
• appendleft(x) : 데크의 왼쪽에 x를 추가
• clear(x) : 데크에서 모든 요소를 제거하고 길이가 0인 상태로 만든다.
• copy(x) : 데크에서 얕은 복사본을 만든다.
• count(x) : 데크의 요소 수를 센다.
• extend(iterable) : iterable 인자에서 온 요소를 추가하여 데크의 오른쪽을 확장한다.

예제)

from collections import deque
d = deque('ghi')     
d.extend('jkl')               
d

예제-결과)

deque(['g', 'h', 'i', 'j', 'k', 'l'])

• extendleft(iterable) : iterable 인자에서 온 요소를 추가하여 데크의 왼쪽을 확장한다. 일련의 왼쪽 추가는 iterable인자에 있는 요소의 순서를 뒤집는 결과를 준다.

예제)

d.extendleft('abc')       
d

예제-결과)

deque(['c', 'b', 'a', 'g', 'h', 'i', 'j', 'k', 'l'])

• insert(i,x) : x를 데크의 i위치에 삽입한다. 삽입으로 인해 제한된 기리의 데크가 maxlen이상으로 커지면 indexerror 발생
• pop() : 데크의 오른쪽에서 요소를 제거하고 반환한다.
• popleft() : 데크의 왼쪽에서 요소를 제거하고 반환한다.
• remove(value) : value의 첫번째 항목을 제거한다.
• reverse() : 데크의 요소들을 제자리에서 순서를 뒤집고 None을 반환한다.
• rotate(n=1) : 데크를 n단계 오른쪽으로 회전한다. n이 음수이면 왼쪽으로 회전한다. 데크가 비어있지 않으면, 오른쪽으로 한단계 회전하는 것은 d.append(d.pop())과 동등하고, 왼쪽으로 한단계 회전하는 것은 d.append(d.popleft())와 동등하다.

예제)

d.rotate(1)                     
d

예제-결과)

deque(['l', 'c', 'b', 'a', 'g', 'h', 'i', 'j', 'k'])