[3.스택/큐] stack, queue

1. Stack

: 단어의 의미처럼 데이터를 쌓아 올린다는 의미

: 배열 대신에 사용되는 경우가 있음

: LIFO(Last In First Out) > 마치 접시를 쌓아두었다가 맨 위부터 사용하는 것처럼,

 가장 최근에 추가한 항목이 가장 먼저 제거될 항목이라는 것.

: 미로 찾기, 괄호 유효성 체크, 재귀 알고리즘 등에 활용

: 직접 new연산자로 객체를 생성하여 사용가능

 

2. Stack의 연산

stack.pop()	가장 최근 원소 반환 후 제거
stack.peek()	가장 최근 원소 호출 (제거X)
stack.push(e)	요소 삽입
stack.isEmpty()	스택이 비어있는 경우 true반환, 요소가 있는 경우 false반환
stack.search()	객체가 존재하는 인덱스 반환(마지막 요소로부터 1~반환) = pop개수를 알 수 있음

 

3. Stack 특징

: 배열과 다르게 상수시간에 i번째 요소에 접근 불가

: 그러나 데이터 추가 혹은 삭제는 상수시간에 가능 > 배열처럼 원소를 옆으로 밀어주는 작업 불필요

: 스택은 같은 방향에서 아이템을 추가하고 삭제한다는 조건하에 연결리스트로도 구현 가능

 

4. stack 예제코드

public static class StackNode {
	private int data; // 자료형은 T
	private StackNode next;
	public StackNode(int d) {
		this.data=d;
	}
}
private StackNode top;
public int pop() {
	if(top==null) throw new EmptyStackException();
	int item=top.data;
	top=top.next;
	return item;
}
public void push(int item) {
	StackNode t=new StackNode(item);
	t.next=top;
	top=t;
}
public int peek() {
	if(top==null) throw new EmptyStackException();
	return top.data;
}
public boolean isEmpty() {
	return top==null;
}

 

 

5. Queue 

: FIFO(First In First Out) - 매표소 앞에 줄을 서서 표를 구매하듯, 큐에 저장된 항목들은 큐에 추가되는 순서대로 제거

: BFS, 캐시구현, 작업 우선 순위, Heap구현 등에 활용

: LinkedList 형태로 구현가능

 

6. Queue 연산

queue.remove()	첫번째 요소 반환 후 제거
queue.poll()
queue.peek()	첫번째 요소 반환 (제거X)
queue.element()
queue.add(e)	요소 삽입 > 큐의 가장 마지막에 주가
queue.offer(e)
queue.isEmpty()	큐가 비어있다면 true반환, 요소가 존재한다면 false반환

 

7. Queue 특징

: 큐 역시 연결리스트로 구현 가능 - 연결리스트 반대방향에서 항목을 추가하고 제거한다는 조건하에 구현 가능

: 큐는 처음과 마지막 노드 갱신을 유의해서 구현해함

: 너비우선탐색(BFS)구현시 처리해야할 노드 리스트를 저장하는 용도로 사용

  => 노드하나를 처리할때마다 해당 노드와 인접한 노드를 큐에 다시 저장 : 노드를 접근한 순서대로 처리 가능

 

 

8. Queue 예제코드

private static class QueueNode {
	private int data;
	private QueueNode next;
	public QueueNode(int d) {
		this.data=d;
	}
}

private QueueNode first;
private QueueNode last;

public void add(int item) {
	QueueNode t=new QueueNode(item);
	if(last!=null) {
		last.next=t;
	}
	last=t;
	if(first==null) {
		first=last;
	}
}

public int remove() {
	if(first==null) throw new NoSuchElementException();
	int data=first.data;
	first=first.next;
	if(first==null) {
		last=null;
	}
	return data;
}

public int peek() {
	if(first==null) throw new NoSuchElementException();
	return first.data;
}

public boolean isEmpty() {
	return first==null;
}