Linear Structure(Stack, Queue)

Linear Structure 선형구조

선형구조란 데이터들이 일렬로 저장되어 있는 형태를 말한다.
일렬로 저장하는 방식은 리스트와 각 데이터가 다음 데이터의 위치를 가지는 연결과 리스트 두 가지 방식이 있다. 일렬로 쭉 저장되어 있는 데이터를 사용하는 방법은 리스트와 연결 리스트 외에 사용 방법에 따라 스택(Stack), 큐(Queue)가 있다.

Stack

LIFO(Last In First Out) 후입선출 구조. input순서와 output순서가 반대이다.

예를 들어, 읽고 싶은 책을 쌓아 놓고 한권씩 읽는다고 생각하자.
책은 아래에서부터 위로 한권씩 쌓이게 된다.
책을 읽으려고 할때 편하게 위에 있는 책부터 읽기 시작한다.

***간단하게 보는 Stack

let arr = []
arr.push(0) //arr = [0]
arr.push(1) //arr = [0, 1]
arr.push(2) //arr = [0, 1, 2]
arr.push(3) //arr = [0, 1, 2, 3]
arr.push(4) //arr = [0, 1, 2, 3, 4]
  /*여기까지는 Queue와 동일*/

arr = [0, 1, 2, 3, 4]
arr.pop() //arr = [0, 1, 2, 3]
arr.pop() //arr = [0, 1, 2]
arr.pop() //arr = [0, 1]
arr.pop() //arr = [0]
arr.pop() //arr = []
  /*뒤에서부터 지운다*/

Queue

FIFO(First In First Out) 선입선출 구조. input순서와 output순서가 동일하다. ex) 선착순, 번호표.

예를 들어, 가게에서 사람들이 계산을 하려고 줄을 서있다고 생각을 해보자.
사람들을 빨리 온 순서대로 계산대 앞에 줄을 서있다.
계산원은 그 순서대로 손님을 응대하지 임의로 뒷사람 먼저 할 수 없다.

***간단하게 보는 Queue

let arr = []
arr.push(0) //arr = [0]
arr.push(1) //arr = [0, 1]
arr.push(2) //arr = [0, 1, 2]
arr.push(3) //arr = [0, 1, 2, 3]
arr.push(4) //arr = [0, 1, 2, 3, 4]
  /*여기까지는 Stack과 동일*/

arr = [0, 1, 2, 3, 4]
arr.shift() //arr = [1, 2, 3, 4]
arr.shift() //arr = [2, 3, 4]
arr.shift() //arr = [3, 4]
arr.shift() //arr = [4]
arr.shift() //arr = []
  /*앞에서부터 지워진다*/