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

1. 스택(Stack)

▶ 스택이란, 한쪽에서만 자료를 넣고 뺄 수 있는 후입선출 LIFO(Last In First Out)형식의 선형 자료구조이다.

스택의 기본 개념은 영어 단어의 뜻과 같이 '쌓는다'는 뜻이다. 스택은 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고, top으로 정한 곳을 통해서만 접근할 수 있다.

예를 들어, 박스 쌓기에 비유할 수 있다. 박스를 아래에서 위로 차곡차곡 쌓으면 아래에 있는 박스를 치우기 위해서는 맨 위의 박스부터 치워야 한다.

아래부터 1->2->3 순서로 쌓여있는 상자를 오른쪽으로 옮긴다고 가정해보자.
먼저 가장 위에 있는 3번 상자를 오른쪽으로 옮기고, 그 후에는 2번 상자를 옮기고, 다음에는 1번 상자를 옮길 것이다. 즉, 마지막에 입력된 상자가 첫 번째로 출력된다.

1->2->3의 순서로 입력되었다면, 3->2->1의 순서로 출력되는 것이다.
우리는 이것을 LIFO(Last In First Out) 형식이라고 하며 스택은 이러한 구조적 특징을 가진다.

1.1 스택의 연산

• push(삽입): 데이터를 삽입한다.
• pop(삭제): 데이터를 삭제한다.

1.2 스택 예제

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

print(stack)

#결과
[1]

위에서 알아본 스택은 LIFO구조이므로 가장 나중에 append된 3부터 pop된다.
[1]->[1,2]->[1,2,3]->[1,2]->[1]

Array Implementation

배열에 top을 나타내는 index를 활용해서 구현할 수 있다.

class ArrayStack {
	private int top;
	private int size;
	private int[] arr;

	public ArrayStack(int n) {
		size = n;
		top = -1;
		arr = new int[n];
	}

	public void push(int n) {
		if (isFull()) return;
		arr[++top] = n;
	}

	public int pop() {
		if (isEmpty()) return -1;
		return (arr[top--]);
	}

	public boolean isFull() {
		return (top == size-1);
	}

	public boolean isEmpty() {
		return (top == -1);
	}
}

Linked List Implementation

class LLStack<T> {
	private LinkedList<T> l;
	
	public LLStack() {
		l = new LinkedList<T>();
	}

	public void push(T x) {
		l.insertAtFront(x);
	}

	public T pop() {
		if (isEmpty()) return null;
		return (l.deleteAtFront());
	}

	public T peek() {
		return (l.getIter().getValue());
	}

	public boolean isEmpty() {
		return (l.isEmpty());
	}
}

2. 큐(Queue)

▶ 큐란, 한 쪽에서 삽입 작업이 이루어지고, 다른 한 쪽에서는 삭제 작업이 이루어지는 선입선출 FIFO(First In First Out)형식의 선형 자료구조이다.

큐의 기본 개념은 영어 단어의 뜻인 '줄서는 것'과 같다.
흔히, 대기 줄에 비유할 수 있다. 먼저 온 사람이 먼저 들어가는 것이다.

top으로 정한 곳을 통해서만 삽입, 삭제가 이루어지는 스택과는 달리 큐는 한쪽에서 삽입 작업이 이루어지고, 다른 쪽에서 삭제 작업이 이루어진다.

이때, 삭제 연산만 수행되는 곳을 프론트(front), 삽입 연산만 이루어지는 곳을 리어(rear), 리어에서 이루어지는 삽입 연산을 인큐(enQueue), 프론트에서 이루어지는 삭제 연산을 디큐(dnQueue)라고 부른다.

자동차들이 터널을 줄지어 지나간다고 생각해보자.
먼저 들어온 1번 차가 첫 번째로 나가고, 다음에 들어온 2번 차가 두 번째로 나간다.

1->2-3의 순서로 입력되었다면, 1->2->3의 순서로 출력되는 것이다.
우리는 이것을 FIFO(First In First Out)형식이라 하며 큐는 이러한 구조적 특징을 가진다.

2.1 큐의 연산

큐의 연산은 collections 모듈에서 제공하는 deque 자료구조를 활용하는 것이 좋다. deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue라이브러리를 이용하는 것보다 더 간단하다.

• append(): 오른쪽에서 데이터를 삽입
• appendleft(): 왼쪽에서 데이터를 삽입
• pop(): 오른쪽에서 데이터 삭제
• popleft(): 왼쪽에서 데이터 삭제

2.2 큐 예제1

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
queue.popleft()
queue.popleft()

print(queue)

# 결과
deque([3])

위에서 알아본 큐는 FIFO구조이므로 가장 먼저 append된 1부터 pop된다.
append는 오른쪽에서 데이터를 삽입하고, popleft는 왼쪽에서 데이터를 삭제한다.
[1]->[1,2]->[1,2,3]->[2,3]->[3]

 

append는 오른쪽에서 데이터를 삽입하고, pop은 오른쪽에서 데이터를 삭제한다.
[1]->[1,2]->[1,2,3]->[1,2]->[1]

 

3. 덱(Dequeue)

▶ 덱이란, 양쪽에서 삽입과 삭제가 가능한 구조이며 스택과 큐의 연산을 모두 지원한다.

Scroll: 입력 제한 덱 (입력이 한쪽에서만 발생하고, 출력은 양쪽에서 일어날 수 있음)
Shelf: 출력 제한 덱 (입력은 양쪽에서 일어나고, 출력은 한쪽에서 일어나도록 제한)

덱의 연산은 collections 모듈에서 제공하는 deque 클래스로 구현 가능하다.

• append(): 오른쪽에서 데이터를 삽입
• appendleft(): 왼쪽에서 데이터를 삽입
• pop(): 오른쪽에서 데이터 삭제
• popleft(): 왼쪽에서 데이터 삭제

3.1 덱 예제

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
queue.pop()
queue.pop()

print(queue)

# 결과
deque([1])

위에서 알아본 덱은 양쪽에서 삽입과 삭제가 가능하다.
append는 오른쪽에서 데이터를 삽입하고, pop은 오른쪽에서 데이터를 삭제한다.
[1]->[1,2]->[1,2,3]->[1,2]->[1]

---

• 오버플로: 특정한 자료구조가 수용할 수 있는 데이터의 크기를 넘어가는 삽입 연산을 수행할 때 발생한다.
• 언더플로: 비어있는 자료구조에서 삭제 연산을 수행할 때 발생한다.

 

---

연관된 글 :

[자료구조] 자료구조

참고 :

[ 자료구조 ] Stack

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