StackQueue.md

Stack/Queue

Stack

스택

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조

특징

• 스택에 저장된 자료는 선형 구조를 갖는다
  • 선형 구조 : 자료 간의 관계가 1대1의 관계를 갖는다
  • 비선형 구조 : 자료 간의 관계가 1대N의 관계를 갖는다
• 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다

후입선출, LIFO(Last-in-First-out)

• 마지막에 삽인한 자료를 가장 먼저 꺼낸다.

주요 메소드 with Java

java.util.Stack

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

• push()
  • 스택에 자료를 저장한다.
• pop()
  • 스택에서 자료를 꺼낸다.
  • 저장된 자료의 역순으로 꺼낸다.
• isEmpty()
  • 스택이 비어있는지 확인
• size()
  • 현재 스택의 길이를 반환

스택 응용

괄호 검사

• 왼쪽 괄호를 만나면 스택에 삽입, 오른쪽 괄호를 만나면 스택에서 top 원소를 빼서 괄호의 짝이 맞는지 검사, 검사 결과가 틀리면 잘못된 괄호열, 또한 마지막 괄호까지 조사했는데 스택이 비어있지 않으면 잘못된 괄호열

Function call

• 프로그램에서 함수 호출과 복귀에 따른 수행 순서를 관리
• 함수 실행 역시도 가장 마지막에 호출된 함수를 가장 먼저 실행하기 때문에 스택 구조와 동일

Queue

큐

• 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 구조

특징

• 큐에 저장된 자료는 선형 구조를 갖는다

선입선출, FIFO(First-in-First-out)

• 큐에 삽인한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소가 가장 먼저 삭제된다.

주요 메소드 with Java

LinkedList 클래스를 Queue 인터페이스의 구현체로 많이 사용

java.util.Stack

Queue<Type> queue = new LinkedList<>();

• offer()
  • 큐에 자료를 저장한다.
• poll()
  • 큐에서 자료를 꺼낸다.
• isEmpty()
  • 큐가 비어있는지 확인
• size()
  • 현재 큐의 길이를 반환