이제 본격적으로 자료구조를 하나씩 알아보자!
스택
여기 약간 내가 하고싶은 말이 다 들어있다. 스택은 일종의 자료를 저장하는 구조인데 저장하는 공간이 바구니처럼 생겼다. 데이터를 넣으면 아래쪽부터 쌓이는데 꺼낼때는 위에서부터 꺼낼 수 있는 그런 구조 후입선출(LIFO) 구조이다. push는 데이터를 넣는 작업 pop은 데이터를 꺼내오는 작업이다.
사진 속에서는
push(1) -> push(2) -> push(3) -> pop()
이런 작업을 거친다. 굳이 pop을 할때는 pop(3)이라 할 필요가 없는게 무조건 맨 위에것만 꺼내올 수 있기 때문이다.
top은 데이터가 있는 가장 위에 위치를 나타내는데 pop작업을 거친 뒤 top은 2가 있는 위치겠다.
배열로 스택을 구현하면 저렇게 구현이 되는데,,! top의 위에 데이터를 쌓는 작업이 push이다.
top이라는 변수를 -1로 설정해두고 데이터는 arr[top+1]에 넣는 그런 느낌! 데이터를 넣고 top도 하나씩 더해주어야 한다. 이 top변수가 왜 필요하냐고 생각할 수도 있는데 스택의 공백과 포화를 나타내기에 좋기 때문이다.
만약 이 스택에서 top의 값이 5라면 지금 스택이 포화되어있는 상태로 더 데이터를 넣을 수가 없다.
만약 이 스택에서 top의 값이 -1이라면 스택이 비어있는 상태로 데이터를 pop할 수가 없다.
그리고 스택에서 사용하는 함수 중 하나가 peek이다.
peek은 우리말로 힐끗 훔쳐보다라는 뜻으로 맨 위에 있는 데이터 값만 보고 실제로 pop하지는 않는다는 특징이 있다.
스택으로 할 수 있는 작업들은 여러가지가 있는데, 실제 작업은 백준 문제를 풀면서 해볼 예정이다.
지금은 어떤식으로 스택이 응용될 수 있다 정도로만 얘기하고 넘어갈 것이다.
1. 괄호검사
수식에서는 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 하며,
같은 괄호 짝에 대해서는 왼쪽 괄호는 오른쪽 괄호보다 선행되어야 한다.
왼쪽 괄호가 나오면 스택에 하나씩 추가하고 오른쪽 괄호가 나오면 스택에서 왼쪽괄호를 pop해서 같은 쌍인지 확인한다.
만약 이때 괄호 짝이 맞지 않거나, 스택이 비어있으면 오류가 날 것이다.
수식이 다 끝났는데 스택이 비어있지 않다면 왼쪽 괄호가 더 많다는 뜻이므로 오류를 출력한다.
2. 회문검사
회문은 EYE LEVEL 12321 처럼 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 말한다.
스택을 이용해서 앞쪽 절반은 push를 하고 뒷쪽 절반은 pop을 하면서 같은지 하나하나 확인한다.
3. 수식계산
일단 우리가 수식을 쓰는 방식은 중위표기법이다. (1+2)*3처럼 생겼다.
하지만 컴퓨터가 수식을 인식하는 방식은 후위표기법이다. 12+3* 이렇게 생겼다.
전위표기법도 있지만 스택공부에서는 중요하지 않으니꽈 패쓰
이 수식계산을 할때 스택을 이용해서 후위표기법으로 계산할 수 있다.
후위표기법으로 쓰여져있는 식을 하나씩 스캔하면서 피연산자 그니까 숫자이면 스택에 저장, 연산자이면 피연산자를 스택에서 꺼내서 연산하고 다시 스택에 저장.
이런 방식으로 진행하면 된다.
12+3*
이 후위표기법으로 시뮬레이션을 해보면
1 들어왔다? 스택에 저장
2 들어왔다? 스택에 저장
+ 들어왔다? 연산자네 앞에 있던 피연산자 두개 pop 더해 3이야 다시 스택에 저장
3 들어왔다? 스택에 저장 (이때는 3 3이 스택에 들어있겠지)
* 들어왔다? 연산자네 앞에 있던 피연산자 두개 pop 곱해 9야
끝났다? 스택에 뭐들어있지? 9 답 9!
이런식으로 진행된다.
사람이 중위표기법으로 바꾸면 컴퓨터가 처리하기 편하도록 후위표기법으로 바꾸는 알고리즘이 필요하다.
이것도 역시 스택으로 할 수가 있다.
피연산자 만나면 그대로 출력, 연산자가 나오면 스택에 저장해뒀다가 스택의 top보다 순위가 낮은 연산자가 나오면 출력, 왼쪽 괄호는 우선순위가 가장 낮은 연산자이고 오른쪽 괄호가 나오면 스택에서 왼쪽 괄호 위에 쌓여있던 모든 연산자 출력
(1+2)*3-4 이걸 후위표기법으로 바꿔보자면
( -> 스택에 넣어
1 -> 그대로 출력
+ -> 스택에 넣어( '+' 는 '(' 보다 순위가 높기 때문에 그냥 들어가)
2 -> 그대로 출력
) -> 오른쪽 괄호 나오면 왼쪽 괄호 위에 쌓여있던 모든 연산자 출력하니까 + 출력됨
-----------------
여기까지 12+ 까지 출력될 것임
-----------------
* -> 스택에 넣어
3 -> 그대로 출력
- -> *출력하고 -는 스택에 넣어('-'는 '*'보다 순위가 높기 때문에 * 출력해야됨)
4 -> 그대로 출력
-----------------
여기까지 12+3*4
-----------------
스택에 남아있는거 다 출력 -만 남아있으니까 이거 출력하면 끝임
그니까 12+3*4-가 출력되겠죠?
4. 미로탐색
큐
큐는 관의 형태로 이루어진 자료구조이다. 아까 스택은 들어가는 곳과 나가는 곳이 같았는데, 큐는 다르다. 먼저 들어간게 먼저 나오는 선입선출 형태이다.
큐에 데이터를 넣는 함수는 add이고 데이터를 빼는 함수는 delete이다. 이 사진의 큐는 단순한 형태의 선형큐인데 데이터를 삽입하려면 하나의 데이터를 넣을 때마다 한칸씩 front로 이동시켜야 하기 때문에 복잡하다.
그래서 있는 큐 종류가 원형큐이다. 배열을 원형으로 사용해서 큐를 구현한다.
이런식으로 생겼는데 front와 rear라는 변수를 도입해서 front와 rear값으로 데이터를 넣을때는 rear값을 추가하고 데이터를 뺄때는 front값을 하나씩 더한다.
'CODING > Data Structure' 카테고리의 다른 글
| 자료구조의 기본 개념 (0) | 2022.01.12 |
|---|
