Data Structure and Algorithms (2)

Stacks and Queues

 

Stack

Stack은 LIFO(Last-In First-Out) 구조를 가진 자료구조입니다.
Stack 구조는 컴퓨터 가상메모리의 Stack 영역에서 사용되는데, 함수가 호출되면서 다시 복귀할 주소를 저장하거나, 지역변수, 매개변수 등을 임시로 저장하는데에 쓰입니다.
Stack의 구현은 Array나 List 모두 가능합니다. (파이썬에서는 List를 통해 구현)
Stack에 대한 기본적인 기능(Basic operations)에는 push, pop, top, isFull(배열로 구현된 경우), isEmpty 가 있습니다.

• push: stack의 가장 뒤에 새로운 요소를 삽입.
• pop: stack의 가장 뒤 요소(top)를 제거 후 return.
• top: stack의 가장 뒤 요소를 지칭하며 삭제 없이 접근하기 위해서 사용. 파이썬에서는 리스트 인덱스를 통해 접근

 

 

Queue

Queue는 FIFO(First-In, First-Out) 구조를 가진 자료구조입니다.
queue에서는 front와 rear로 가장 먼저 들어온 요소와 제일 마지막에 들어온 요소에 접근합니다.
Basic operations (enqueue, dequeue, is_full, is_empty)

• Enqueue: queue에 원소를 삽입
• Dequeue: queue에서 원소를 삭제