자료구조 - 스택

특징

한쪽 끝이 막힌 상자에 데이터를 넣고 빼내는 형식의 자료구조(선입후출, LIFO). 흔히 데이터의 삽입, 삭제가 일어나는 위치를 top, 삽입을 push, 삭제를 pop 이라고 표현.

구현

스택은 보통 배열과 연결 리스트로 구현한다

배열

일정 크기의 배열을 선언한 뒤, top 인덱스 변수 값을 변경해가며 push,pop 을 구현한 형태. 연결 리스트보다 구현이 쉽고 메모리를 적게 쓰지만 선언할 때 크기가 정해져 있어서 메모리 부족

메모리 낭비가 발생할 수 있음.

연결 리스트

연결 리스트로 요소를 구현해 링크로 자기 바로 밑에 있는 요소를 가리키게 한다. 요소가 추가될 때마다 메모리를 할당하므로 메모리의 낭비

부족이 없으나 상대적으로 구현이 복잡하고 링크를 위한 메모리가 필요해 메모리를 배열에 비해 많이 쓴다.

활용

스택은 굉장히 많이 활용되는 자료구조이다. 웹 브라우저의 뒤로가기, 프로그램에서의 재귀함수 호출, OS 의 시스템 스택 등 실제 프로그램들에서도 많이 사용되고, 괄호 짝 맞추기나 전/후위 연산자 문제, 미로 찾기 등의 알고리즘 문제 해결과 이후 더 복잡한 자료구조에서도 스택을 활용하는 경우가 있다.
파이썬 스택 모듈

파이썬 라이브러리에 있는 queue 모듈을 사용하면 바로 스택과 큐를 구현할 수 있다. 파이썬에서는 스택 모듈이 따로 없고 LifoQueue, 후입선출 큐의 형태로 제공한다.

import queue

s = queue.LifoQueue() # LifoQueue() 의 인자로 저장 데이터 수의 최대값을 줄 수 있다. 인자를 주지 않으면 메모리의 한계까지 수용한다.
s.put("data1") # put() 메소드의 인자로 주어진 값을 해당 스택에 쌓는다.
s.put("data2") # 하나 더 쌓는다.
s.qsize() # >>2 qsize() 메소드는 현재 큐에 들어있는 데이터의 개수를 리턴한다.
s.get() # >>"data2" 위에서부터 하나씩 꺼내서 리턴한다.
s.get() # >>"data1" 하나 더 리턴한다.
s.get() # 이 경우 큐 객체에서 꺼낼 데이터가 없으므로 None 이나 False를 리턴하거나 예외를 발생시킬 것으로 기대되지만 get() 메소드는 다를 쓰레드가 가지고 갈 때까지 무한 대기 상태가 된다고 한다.
s.get_nowait() # 이렇게 get_nowait()메소드를 사용하면 더이상 객체에 꺼낼 데이터가 없을 때 바로 queue.Empty 예외를 발생시킨다.
s.put_nowait("noMoreSpaceInStack") # 이 스택 객체는 생성할때 인자를 주지 않았으므로 객체가 꽉 찰 일은 거의 없겠으나, put_nowait()메소드 역시 만약 스택이 가득 찼다면 대기하지 않고 바로 queue.Full 예외를 발생시킨다.

자료구조 - Stack

Categories

자료구조 - 스택