[Data Structure] Stack / Queue

Stack

Stack은 LIFO (Last In First Out)  자료 구조이다. 나중에 넣은 자료가 먼저 나오는 방식이다.

책이나 접시를 쌓아 두면 위에서부터 쌓거나 위에서부터 빼낼 수 있는 구조를 생각하면 된다.

 

LIFO를 설명한 접시 그림 

 

1,2,3 의 순서로 쌓이면, 꺼낼때에는 3,2,1 순으로 리스트 한쪽 끝에서 작업이 이뤄지는 선형구조이다. 

자료를 삽입하는 것은 Push  ,  자료를 꺼내는 것은 Pop 이다.

 

 

push와 pop

• top : Stack의 가장 윗 데이터. 프로퍼티의 현재 위치.  삽입 및 제거
• push : Stack에 요소 삽입
• pop : Stack의 Top위치의  요소를 제거 
• size(length) : Stack의 Size 반환
• peek : Stack의 Top위치의 요소를 반환 (pop과 달리 제거하지 않는다)
• isEmpty : Stack 이 비어있다면 true ,  비어있지 않다면 false 

Linked List Stack을 참조 할 수 있는 웹사이트

http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/8-List/list-stack.html

 

그림이 옛것 같지만 그래도 이해하는데 도움이 되었다 

 

사용예시

• Function callStack
• 실행 취소 (undo, command + z)
• 웹페이지 뒤로가기(backward)

 

Pseudo Code 

 

• push(item)
  • 요소를 넣을 Storage에 요소를 삽입 
  • top 1 증가
• pop()
  • 비어있다면 미실행
  • top의 값을 반환 및 제거
  • top 1 감소
• size()
  • push나 pop시 반영된 top의 값을 이용하여 반환
• peek()
  • 비어있다면 반환할 값이 없다는 내용 반환
  • 비어있지 않다면, top의 값 반환
• isEmpty()
  • 사이즈 또는 top의 값을 확인
  • 비어있다면 True,  비어있지않다면 False 

 

 

 

Queue

Queue는 Stack과 다르게 FIFO(first in, first out) 자료구조이다. 먼저 넣은 자료가 먼저나오는 형태이다.

쇼핑몰이나 카페등의 줄서기처럼 먼저 줄은 선 사람이 먼저 나가는 구조를 생각하면 된다.

 

Queue를 설명한 Gif. Array로 psuh와 shift를 사용해서 보여주고 있다

 

 enqueue와 dequeue

 

• enqueue :  Queue의 가장뒤 (Back /rear)에 요소 삽입 
• dequeue : Queue의 가장 앞 (Front) 의 요소 제거
• size :  Queue의 Size 반환 
• peek : Queue의 가장 앞의 요소 반환 

 

사용예시

• Print 출력 처리
• 인쇄 대기열 
• CPU 프로세서 우선 순서 관리 
• 놀이동산이나 카페등 FIFO가 필요한 대기열

 

Pseudo Code

 

• enqueue(item)

  • 삽입할  Storage에 rear 위치에 값을 삽입

  • rear 1 증가

• dequeue() 

  • 비어있다면 미실행

  • front의 위치에서 값을 반환 및 제거

  • front 1 감소 

• size()

  • rear - front를 반환

• peek()

  • 비어있다면 반환할 값이 없다는 내용 반환

  • 비어있지 않다면 front의 값 반환