스택

• 한쪽으로만 데이터를 넣고 뺄 수 있는 구조

구조

• FILO(Fisrt In Last Out)구조를 가짐
• 주요 메소드
  • push() : 데이터를 스택에 넣기
  • pop() : 데이터를 스택에서 빼기

장단점

• 장점

  • 구현이 쉽다
  • 데이터 삽입/삭제 속도가 빠름

• 단점

  • 전체 크기가 유동적이지 않음

큐

• 한쪽은 입력만 반대쪽은 출력만 되는 구조

구조

• FIFO(First In First Out)구조를 가진다.
• 주요 메소드
  • Enqueue() : 큐에 데이터 삽입
  • Dequeue() : 큐에서 데이터 꺼내기

장단점

• 장점
  • 구현이 쉽고 저장 삭제가 빠르다.
• 단점
  • 전체 크기가 유동적이지 않음

Stack으로 Queue 구현

• 스택a와 스택b 두개의 스택이 존재

• Enqueue

  • 스택 a에 push

• Dequeue

  • 스택 b가 비어있지 않으면 b에 있는 값을 pop
  • 스택 b가 비어있으면 스택a의 모든 값들은 pop해서 스택 b에 push, 스택 a의 마지막 값만 push하지 않음

Queue로 Stack 구현

• 큐a와 큐b 두개의 큐가 존재

• push

  • 큐a가 비었으면 Enqueue
  • 큐a가 비어있지 않으면 큐a의 값을 큐b로 옮기고 큐a에 Enqueue 후 큐b에 값을 큐a로 옮김

• pop

  • 큐a에서 Dequeue