Data Structure - stack, queue

컴퓨터는 0과 1만 인식한다.

사람은 0과 1로 사고하지 않으니까 사람과 컴퓨터 사이에 전달할 무언가가 필요한데 그렇게 나온 것이 compiler 이다.

 

0과 1로 이루어진 데이터에 타입을 지정한다.

2진수 데이터를  특정한 길이 1byte 단위 (bit 8개를 조합한 것)로 나눈다. 

 

이로 특정한 값을 얻어낼 수 있고 이를 문자로 나타낼 수 있다. (ASCII Tabla 에 정의되어 있음)

 

Data Type 데이터 타입

 : 하나의 데이터를 어떻게 해석할지 정의한 것

 

• Primitive Type
  • 정수, 실수
  • 문자
  • 논리(참, 거짓)
• Custom Type : 사용자 정의 타입의
  • 구조체, 클래스 등..

 

 

Data Structure 자료 구조

: 여러 데이터들의 묶음을 어떻게 저장하고 사용할지 정의한 것

 

배열, 트리, 스택 등 다양한 자료 구조가 있다.

 

Stack 

나중에 넣은 값이 먼저 나오는(한 쪽 끝에서만 자료를 넣거나 뺄 수 있어서)  LIFO (Last In First Out) 구조로 되어 있다.

쌓여 있는 접시를 가져가거나 새로운 접시를 쌓을 때 항상 맨 위에 접시만 움직일 수 있는 것을 연상하면 된다.

속성

top  : 스택의 가장 위에 있는 데이터를 리턴한다.

메서드

push( ) : 스택 가장 위에 새로운 데이터를 추가한다. 꽉 찼을 경우 Overflow condition

pop( ) : 스택에서 가장 마지막에 추가된 데이터를 삭제한다. 스택이 비어 있는 경우 Underflow condition

peek( ) : 스택 가장 위에 있는 데이터를 리턴한다.

isEmpty( ) : 스택이 비었을 경우 true, 그렇지 않으면 false를 리턴한다.

isFull( ) : 스택이  꽉 찼을 경우 true, 그렇지 않으면 false를 리턴한다.

size( ) : 

 

사용 예

• 실행 취소
• 브라우저의 히스토리
• 괄호 검사

pseudocode 작성해보기 (codestates 과제 기준)

push(element) :  값이 저장되는 객체에 top 에 해당하는 키에 element를 할당해준 후 top++한다.

pop() : 

size() : 값들이 저장되는 공간의 길이를 구한다.

 

stack 구현해보기 (codestates 과제 기준)

과제 내용 정리해야지...

 

Queue

먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 형식이다.

먼저 줄을 선 사람이 티켓을 먼저 사서 갈 수 있는 상황을 연상하면 쉽다.

속성

front (head) 와 rear (tail)은 데이터의 위치를 가리킨다.

 

• front : 데이터를 꺼낼 수 있는 위치
• rear : 데이터를 넣을 수 있는 위치

 

메서드

• enqueue( ) : 큐에 새로운 데이터를 추가한다.
• dequeue( ) : 큐의 가장 앞에 있는 값을 삭제한다.
• peek( )  : 큐의 가장 앞에 있는 값을 리턴한다. (삭제 x)
• isEmpty( ) : 큐가 비었을 경우 true, 그렇지 않으면 false를 리턴한다.
• isFull( ) : 큐가 꽉 찼을 경우 true, 그렇지 않으면 false를 리턴한다.

size( ) : 이것도 정의된 메서드가 맞나?

 

 

사용 예

• 프린터의 출력 처리
• 윈도 시스템의 메시지 처리기
• 프로세스 관리
  
  등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.

 

용어

• Overflow : 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우
• Underflow : 큐가 비어 있어서 자료를 꺼낼 수 없는 경우

종류

선형 큐, 환형 큐

 

위키백과 참조

 

 

pseudocode 작성해보기 (codestates 과제 기준)

enqueue()

dequeue()

size()

 

stack 구현해보기 (codestates 과제 기준)

과제 내용 정리해야지...