[자료구조][C++][TIL]Stack&Queue

컴퓨터공학과 전공과목 자료구조 3, 4주차에 Stack과 Queue를 공부하였습니다. 

Stack과 Queue에 대한 개념과 구현방법을 공부하고, 관련된 백준 문제를 풀어보았습니다.

 

Stack

1. 스택이란?

-접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조

-스택에 저장된 원소는 top으로 정한 곳에서만 접근 가능하다

 ->top의 위치에서만 원소를 삽입하므로 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓인다

 ->마지막에 삽입(Last-In)한 원소는 맨 위에 쌓여 있다가 가장 먼저 삭제(First-Out)된다 : 후입선출(LIFO, Last-In-First-Out)

 

2. 스택의 연산 알고리즘(with 백준 10828)

https://www.acmicpc.net/problem/10828

10828번: 스택

 

1) push

(*) 증감연산자(전위, 후위) 비교하기

전위(++t) : 증가 후 대입

후위(t++) : 대입 후 증가

push연산은 배열의 index값을 올린 후 값을 대입하기 때문에 전위 연산자가 사용됨

 

2) pop

(*) pop연산은 배열의 값을 return한 후 index값을 줄이기 때문에 후위 연산자가 사용됨

 

3) size, empty, top

-메인함수

 

 Queue

1. 큐란?

-First-In-First-Out : FIFO 구조

-먼저 삽입된 객체가 먼저 삭제될 수 있는 자료 구조

-원소가 rear을 통해서 삽입, front를 통해 삭제

 

2. 추상 데이터 타입

-size() : 큐 안의 객체의 개수를 반환

-isEmpty() : 큐가 비었으면 참을, 그렇지 않으면 거짓을 반환

-front() : 큐의 맨 앞의 값을 제거하지 않고 참조를 반환

-rear() : 큐의 맨 뒤의 값을 제거하지 않고 참조를 반환

-enqueue(e) : 큐의 rear에 객체 e를 삽입

-dequeue() : 큐의 front에서 객체를 삭제. 빈 큐일경우 에러 발생

 

(*)queue를 구현할 때 front와 rear의 정의는 구현하는 사람마다 다를 수 있습니다. 일관된 규칙을 적용하기만 한다면 모두 맞다고 볼 수 있습니다

(**)저는 rear를 마지막 원소의 위치로, front를 첫번째 원소의 한칸 앞으로 정의하고 풀었습니다

 

3. 배열기반 선형 큐의 문제점

-배열로 이루어진 선형 큐에서는 삽입과 삭제를 반복하면서 front, rear에 해당하는 위치가 배열의 크기를 넘어갈 수 없어 front이전의 공간이 남아있어도 더 이상 사용할 수 없게 된다

 

4. 배열기반 원형 큐의 사용

-원형 큐는 남아있는 front의 앞의 공간을 사용하여 선형 큐보다 메모리를 효율적으로 사용할 수 있는 구조이다

 

5. 큐의 알고리즘 구현(with 18258)

https://www.acmicpc.net/problem/18258

18258번: 큐 2

1. 멤버변수와 생성자 선언

2. 소멸자와 pop 

3. size/empty/front/back

4. main함수 구현

 

(*)배운점

-멤버변수와 함수의 이름이 똑같으면 에러가 생긴다는 사실을 알게되었다. 

-endl을 시행할 때 시간이 오래 걸린다. 18258문제를 풀 때 왜 계속 시간초과가 뜨는지 몰랐는데, endl 대신 "\n"을 사용하니 시간초과 문제를 해결할 수 있었다!

-ps를 할 때는 class에서 모든 멤버변수를 public 안에서 선언하지만, 원칙적으로는 캡슐화를 지키기 위해 private 선언안에서 사용해야 한다는 것을 알게되었다. 앞으로는 private 선언을 해서 코드를 구현하는 연습도 해봐야겠다

 

(**)느낀점

자료구조 과목을 배우면서 느낀 점은 선수 과목 객체1, 2의 개념의 빈 구멍들이 조금씩 채워져가는 듯 했다.

객체1, 2를 들을 때 실습 연습을 거의 못해서 처음 자료구조 실습을 할 때는 어려운 점들이 있었는데 연습을 하다보니 점차 익숙해져서 뿌듯했다.