(191114) 자료구조 - Stack, Queue

오늘 배운 것

- 자료구조란 무엇인가

- 자료구조 중 stack 과 queue는 무엇인가

  아래에 정리!!

 

- 스택과 큐에 대한 기본 개념에 대해서 알 수 있었다.

 

 

Stack 자료구조

Stack 자료구조.jpg

stack 자료구조는 후입선출(LIFO, Last In First Out)의 구조로 위 모습에서 알 수 있듯이 쉽게 상자를 생각하면 된다.

빈 상자에 물건을 쌓는 경우 상자에 가장 먼저 들어온 물건이 제일 밑에 쌓이고 제일 마지막에 들어온 물건이 맨 위에 쌓이기 때문에 만약 물건을 뺀다고 하면 제일 마지막에 들어온 물건부터 상자에서 빠지게되고 제일 먼저 들어온 물건은 그 다음에 들어온 물건들이 모두 빠져야 뺄 수 있다. 

(stack의 대표적인 예 : 브라우저의 뒤로가기)

Property / Method

stack 자료구조는 Top이라는 상자의 제일 위, 즉 현재 위치를 가리키는 property가 있다. 후입선출이라는 구조이기 때문에 stack의 Top에 위치하여 있지 않은 요소에는 접근할 수 없고, 위에 설명한 것처럼 밑에 있는 요소에 접근하려면 그 위에 있는 요소들을 모두 제거해야 한다.

 

stack 자료구조가 가지고 있는 Method에는 일단 기본적으로 stack에 요소를 추가하는 Push, stack의 Top에 위치한 요소를 꺼내서 제거하는 Pop이 있고, 현재 Top에 위치한 요소를 꺼내지않고 무엇인지 확인하여주는 Peek라는 것이 있다. 이외에도 stack이 비어있는지 혹은 가득차있는지 확인하는 Empty 또는 Full 이나, stack의 level이나 혹은 크기 등을 보여주는 Size가 있다.

 

Property

- top

 

Method

- push()

- pop()

- peek()

- empty() / full()

- size()

 

Stack 자료구조와 method를 pseudo code로 만들어보기(이것이 맞나??)

먼저 stack 생성 시 (배열???) empty 상태이기 때문에 top을 처음에는 -1로 설정

(empty 상태에서 처음 element가 push 된다면 top은 0이 되고 배열의 index 처럼 기능)

 

- push(element)

1. full() 함수를 호출한다

1-1. full() 함수 호출 결과로 true이면 stack이 가득 찼기 때문에 더 이상 push 할 수 없다는 에러 발생 후 종료

1-2. full() 함수 호출 결과로 false이면 stack이 가득 차지 않았기 때문에 다음으로 진행됨

2. stack에 element를 현재 top 다음 (혹은 위에) 추가

3. top 값에 +1을 해준다

 

- pop()

1. empty() 함수를 호출한다

1-1. empty() 함수 호출 결과로 true이면 stack이 완전히 빈 상태이기 때문에 더 이상 pop할 수 없다는 에러 발생 후 종료

1-2. empty() 함수 호출 결과로 false이면 stack이 완전히 빈 상태가 아니기 때문에 다음으로 진행

2. stack에서 현재 top에 해당하는 element를 제거

3. top 값에 -1를 해준다.

  

- peek()

1. 현재 top 값과 그 값에 해당하는 element를 리턴

 

- empty()

1. 현재 top 값을 리턴

1-1. top 값이 -1일 경우 true 리턴

1-2. top 값이 -1이 아닐경우 fasle 리턴

 

- full()

1. 현재 top 값을 리턴

1-1. top 값이 처음 stack 생성 시 지정한 크기와 같을 경우 true 리턴

1-2. top 값이 처음 stack 생성 시 지정한 크기와 다를 경우 false 리턴

 

- size()

1. 현재의 top 값이 그 stack(배열)의 크기를 나타내기 때문에 top 값을 리턴

 

 

Queue 자료구조

Queue 자료구조.jpg

Queue 자료구조는 stack과는 다르게 선입선출(FIFO,First In First Out)로 한쪽이 뚫려있는 관 모양을 생각하면 된다. 일상생활에서 자주 접하는 은행에서 대기열을 기다리거나 어디서든 줄서서 기다리는 예를 생각하면 된다. 먼저 온 요소가 먼저 처리되고 나중에 온 요소는 나중에 처리되는 구조이다.

 

Property / Method

Queue에서는 요소가 들어오는 곳, 나가는 곳 두군데가 있기 때문에 먼저 queue에서 맨 앞에 위치한 요소를 나타내는 front, queue의 맨 뒤에 위치한 요소를 나타내는 rear가 있다.

 

Queue 자료구조가 가지고 있는 method로는 front에 해당하는 요소를 queue에서 삭제하는 Dequeue, queue의 맨 뒤에 요소를 추가하는 Enqueue가 있고 stack과 비슷하게 현재 해당하는 front가 무엇인지 확인하는 getFront, queue가 비어있는지 혹은 가득 찼는지 확인하는 empty / full, 그리고 queue의 level 혹은 크기를 확인하는 size가 있다.

 

property

- front

- rear

 

method

- enqueue()

- dequeue()

- getFront()

- empty() / full()

- size()

 

Queue 자료구조와 method를 pseudo code로 만들어보기