[Data Structure] Stack, Queue

Data Structure 란?

Stack 과 Queue 에 관해 이야기 Data Structure가 무엇인지 짚고 넘어가야 합니다.

Data Structure, 즉 자료구조, 는 자료(데이터)를 효율적으로 관리할 수 있도록 하는 조직 혹은 구조 라는 의미를 가지고 있습니다.

이 자료구조를 크게는 선형구조(Linear Structure) 와 비선형구조(Non-linear Structure) 로 구분할 수 있는데 오늘 다룰 Stack 과 Queue 는 선형구조의 대표적 예 입니다. 이유는 아래에서 얘기하도록 하겠습니다. 비선형구조는 자료들의 연결구조가 선형적이지 않고 분산적인 구조를 띕니다. 대표적인 예시로 Tree 구조가 있습니다.

1. Stack

Stack 은 코딩을 공부하던 분들은 한 번씩 들어보셨을 수도 있는 이름입니다. 바로 유명한 프로그래밍 커뮤니티 사이트 “stackoverflow.com” 를 아시는 분들이 계실 겁니다. 이 때 “stack overflow” 는 오류의 일종으로 function 의 호출될 때 Stack 에 쌓이게 되는데 이것이 여러 이유들(재귀함수, 무한루프 등)로 인해 한계를 넘어 섰을 때 발생하게 됩니다. 그렇다면 이 Stack은 어떤 구조를 가지고 있는 것일까요?

일단 Stack 은 FILO(First-In, Last-Out)의 형식을 가지고 있습니다. 가장 먼저 들어온 값이 Stack 의 가장 밑에 들어가 값이 추가 될 수록 쌓이게 됩니다. 값을 제거하려면 반대로 위에서부터 꺼내기 시작해야 합니다.

위의 그림으로 다시 설명하자면, input 순서는 1–2–3–4–5 이고,
output 순서는 5–4–3–2–1 이 됩니다.

1-1. Stack 의 Property

Stack 의 구조상 가장 위의 값을 확인할 수 있기에 “top”이라는 property 를 가진다.

1-2. Stack 의 Method

1-3. Stack 의 Method 를 pseudocode 로 구현하기

• push()

1. Stack 의 길이를 확인한다.
2. 만약 꽉 차 있다면: Stack overflow error 를 실행.
3. 그렇지 않다면 다음을 실행.
   3–1.주어진 값을 Stack에 추가한다.
   3–2. Stack 의 top 을 새로 추가한 값으로 지정한다.

• pop()

1. Stack의 길이를 확인한다.
   2. 만약 Stack이 비어 있다면: undefined를 리턴한다.
   3. 그렇지 않다면 다음을 실행.
      3–1. 로컬 변수를 생성한 후 top의 값을 할당한다.
      3–2. 현재 top 에 위치한 값을 제거한다.
      3–3. 현재 가장 마지막에 위치한 값을 top에 할당한다.
      3–4. 로컬 변수를 리턴한다.

• peek()

1. Stack의 길이를 확인한다.
2. 만약 Stack이 비어 있다면: undefined를 리턴한다.
3. 그렇지 않다면 다음을 실행.
   3–1. top의 값을 리턴한다.

• size()

Stack 이 배열의 형태라면 단순히 마지막 값의 인덱스를 리턴하면 된다.->O(1)
하지만 노드로 연결된 리스트의 형태라면 순차적으로 값들을 확인해야만 알 수 있다.->O(n)
1. 먼저 구한 길이의 값을 할당받고 리턴할 로컬 변수(값 = 0)를 선언한다.
2. 만약 top의 값이 null 이라면 0을 리턴한다.
3. 그렇지 않다면 다음을 실행
3-1. While-loop을 이용하여 top부터 안쪽 끝까지 그 다음 값을 확인한다.
3-1-1. loop에서 다음 값으로 넘어 갈 때 돌 때 로컬 변수에 +1 을 한다.
3-2. loop이 종료되고 로컬 변수 값을 리턴한다.

• isEmpty()

1. 만약 top의 값이 null 이라면 true 를 리턴한다.
2. 그렇지 않다면 false 를 리턴한다.

2. Queue

Queue 는 또 다른 자료 구조로서 Stack 과 비슷하지만 조금 다른 구조를 가지고 있습니다. 앞의 Stack이 FILO(First-In, Last-Out) 방식이라면, Queue는 FIFO(First-In, First-Out) 의 방식입니다.

실생활에서 가장 찾기 쉬운 예시라면 마트의 계산대가 있습니다. 먼저 계산을 한 사람이 나가면, 다음 사람이 와서 계산을 하고 나가게 됩니다.

간단한 그림으로 표현하자면 이런 식이 됩니다.

이 때, Queue 에서의 input 은 1–2–3–4–5 순이며, output 또한 1–2–3–4–5 가 됩니다. Stack 과 input 과정은 같지만 output 과정은 반대가 됩니다.

2-1.Queue 의 Property

Queue는 일방적인 흐름입니다. 위 그림의 1이 출구에 가장 가까우므로 ‘front’ 라는 속성이 되고, 가장 마지막에 들어온 5가 ‘rear’가 됩니다.

2-2. Queue 의 Method

2-3. Queue 의 Method 를 pseudocode 로 구현하기

• enqueue()

1. 먼저 queue의 길이를 확인한다.
2. 만약 안의 값이 가득 차 있다면 Overflow error를 리턴한다.
3. 그렇지 않다면 다음을 실행.
   1-1. 새로운 값을 queue에 추가한다.
   1-2. rear의 값을 방금 추가한 값으로 변경한다.

• dequeue()

1. 먼저 queue의 길이를 확인한다.
2. 만약 queue 안의 값이 존재하지 않는다면 undefined을 리턴한다.
3. 그렇지 않다면 다음을 실행.
   2-1. 로컬 변수를 생성해 첫번째 요소의 값을 할당한다.
   2-2. queue의 첫번째 요소의 값을 제거한다.
   2-3. 첫번째 요소가 된 값을 front에 할당한다.
   2-4. 제거된 값을 할당받은 로컬 변수를 리턴한다.

• peek()

1. 먼저 queue의 길이를 확인한다.
2. 만약 queue 안의 값이 존재하지 않는다면 undefined을 리턴한다.
3. 그렇지 않다면 다음을 실행.
   2-1. front의 값을 리턴한다.

• size()

위의 Stack처럼 배열일 때와 리스트일때의 경우가 다르다.
1. 먼저 구한 길이의 값을 할당받고 리턴할 로컬 변수(값 = 0)를 선언한다.
1. 만약 rear의 값이 null 이라면 0을 리턴한다.
2. 그렇지 않다면 다음을 실행
2-1. While-loop을 이용하여 rear부터 front까지 그 다음 값을 확인한다.
2-1-1. loop에서 다음 값으로 넘어 갈 때 돌 때 로컬 변수에 +1 을 한다.
2-2. loop이 종료되고 로컬 변수 값을 리턴한다.

• isEmpty()

1. 만약 front의 값이 null 이라면 true 를 리턴한다.
2. 그렇지 않다면 false 를 리턴한다.

참고

http://tcpschool.com/java/java_collectionFramework_stackQueue
https://www.javascripttutorial.net/javascript-queue/