데이터구조 - (5) 스택, 큐

스택

LIFO 구조로 마지막에 넣은 것이 처음으로 나가는 구조이다.

예시로 쌓여있는 식판이 있다.

출처 : 쉽게 배우는 자료구조 with 파이썬

기본적으로 push는 append의 동작을 수행하고,

pop은 top 값을 제거한다. 원하는 값을 삭제하기 위해서는 따로 지정이 필요하다.

​

출처 : 쉽게 배우는 자료구조 with 파이썬

정적 영역은 컴파일 직후 상대적인 위치를 정할 수 있는 정보가 있고,

동적 영역은 수행을 시작한 후에야 알 수 있다.

즉 정적은 프로그램 수행 코드와 프로그램이 끝날 때까지 존재하는 데이터가 있고,

동적은 프로그램 수행 중 할당받는 메모리(힙)와 다른 함수 호출할 때 정보를 저장하는 스택이 있다.

 

리스트를 이용한 스택

리스트를 이용하여 스택을 구현하면 삽입은 append(값)으로,

삭제는 pop()으로 구현된다. top의 경우 stack[끝 인덱스],

popAll()은 self.__stack.clear()와 같이 구현된다.

출처 : 쉽게 배우는 자료구조 with 파이썬

​

 

연결 리스트를 이용한 스택

연결 리스트로 구현할 경우 맨 앞을 스택의 탑으로 삼는다.

그렇기에 맨 앞에 원소를 더하거나 삭제하는 형태로 진해된다.

이것이 더욱 효율적이기 때문이다.

출처 : 쉽게 배우는 자료구조 with 파이썬

그렇기에 insert와 pop, top에 0이라는 위치가 기본값이다.

 

stack 응용

출처 : 쉽게 배우는 자료구조 with 파이썬

문자열 뒤집기를 구현한 것이다.

LIFO 구조를 이용하여 empty가 될 때까지 pop을 진행하고

그 값을 다른 stack에 push해서 문자열을 뒤집는 것이다.

 

출처 : 쉽게 배우는 자료구조 with 파이썬

Postfix 계산을 하는 코드로, 즉 후위 표현식에 관한 input을 입력하면

그 결과를 도출하는 함수를 구현한 것이다.

​

 

큐

FIFO 방식으로 줄 서기와 같은 기본적인 선입선출 방식이다.

스택과 큐의 방식의 차이를 정확히 이해하는 것이 중요하다.

​

리스트로 구현한 큐

출처 : 쉽게 배우는 자료구조 with 파이썬

추가할 때는 append로 제거할 때는 pop(0)로

맨 뒤에 추가하고, 맨 앞을 제거하는 형태로 구현한다.

 

 

연결 리스트로 구현한 큐

맨 앞을 front로, 맨 뒤를 tail로 삼는다.

출처 : 쉽게 배우는 자료구조 with 파이썬

마찬가지로 append로 추가하고, 제거는 pop(0)을 사용한다.

즉 연결 리스트와 리스트라는 점이 가장 큰 차이점이다.

 

 

큐 활용

출처 : 쉽게 배우는 자료구조 with 파이썬

팰린드롬인지 체크하는 함수이다.

즉 좌우가 대칭인 문자열인지 확인하는 것이다.

백준에서 팰린드롬과 관련된 여러 문제들이 존재한다.

그에 위와 같은 알고리즘 방식을 활용하여 풀면 된다.

​

간단히 설명하면 stack과 queue를 사용해

입력받은 문자열을 저장한다. 이는 LIFO와 FIFO 방식을 이용한 것이다.

while문의 조건에 맞게 반복을 하면 중간에 같이 같지 않은 경우

q의 값이 남은 상태로 멈추게 되는데, 이런 경우 else문을 만나 False를 반환한다.

즉 while문을 돌았을 때 q의 값이 비어있는 경우에는 팰린드롬 문자열이다.

​

이를 실제로 하나씩 stack과 queue에 적용해보면 더욱 쉽게 이해할 수 있다.