4.5. 스택(stack)
김보문
(올린 날 : 2001-05-28)
스택은 푸시다운 리스트(pushdown list) 또는 후입 선출(LIFO; last-in first-out) 리스트라고도 불리우는데 이유는 데이타의
삽입과 삭제가 한쪽 끝에서만 일어나므로 가장 나중에 삽입한 데이타가 제일 먼저 삭제되기 때문입니다.
그럼 이렇게 간단한 스택을 파이썬에선 어떻게
사용하는지 잠시 보겠습니다.
일반 C
언어에서와는 달리 파이썬에선 앞에 글에서 리스트라는 자료형을 보셨을 것입니다.
(안 보셨다면 잠시
앞으로 이동하셔서 함 보십쇼~ ^^;) 리스트라는 자료형에선 append(끼워 넣기)와 pop(빼기)가 있습니다.
## C에선
push, pop 이라고 합니다. 거의 비슷하져?
## 지금부턴
Python 2.0 (#1, May 11 2001, 19:51:31)
[GCC
egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)] on linux2
Type
"copyright", "credits" or "license" for more
information.
이 넘을 가지고 실습해 보겠습니다 ##
ex)
>>>
list = []
>>>
>>>
dir(list)
['append',
'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort']
여기에 'append'라는
넘과 'pop'라는 넘이 있습니다. 그외에 많은 것들이 있는데 자세한 사항은 레퍼런스를 보십쇼...(저도 아직 초보라서....ㅡㅡ;;)
일단 자료를 넣습니다. 한 100개 정도 넣어 볼까여~?
>>>
list=[]
>>>
for i in range(100):
... list.append(i)
...
>>>
list
[0, 1, 2, 3, 4,
5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45,
46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65,
66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85,
86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
>>>
우와 단숨에 100개가 들어갔습니다. (저도 신기할 따름입니다. ^^*)
일단 위에서 정의 했듯이 첫번째 들어가는 '0'이 스택에서는 가장 나중에 나오게 됩니다. 왜냐구여...
LIFO 가장 나중에
들어간 넘이 젤 빨리 나온다는 위에 정의를 따라서져...
간단하게 스택은 테니스공 담는 통 아시져? 둥그렇게 생긴거 10개가 들어간다고 생각하시면...
제일 처음에 넣은 공은 가장 나중에 나오겠져? 왜냐면 밑이 안 뚫려 있기 때문이져...
밑을 뚫는 다면 가장 처음에 들어간 넘이
가장 빨리 나오겠져... 그건 뒤에 말할 큐 입니다!!
그럼
100개에서 한개만 빼보죠...
>>>
list.pop()
99
>>>
list
[0, 1, 2, 3, 4,
5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45,
46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65,
66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85,
86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98]
>>>
보시면
list.pop() 했더니 99라는 값이 찍히면서 다시 list 를 때리니 99가 없어졌습니다.
%*% 주의!! 만일
list.pop(0) 이라고 하면은 제일 앞에 값인 0이 날아갑니다.
왜냐면 리스트는 번지값을 가지고 있습니다. 그러니까...현재...0 부터
99까지는 0 부터 99까지에 번지 값을 가지고 있는 거나 다름이 없죠...
그래서 큐에 구현도 정말 쉽게 가능 합니다.
그외에 데크나 다른 자료구조형도 있지만...일단 스택과 큐를 아시면 다른건...쉽게 쉽게 :-)
이제 좀 감이 잡히시는지요...
하지만 만약에 스택에선 가운데 값을 뺄려면
그건 말이 안되져...우리가 정의한 것에 어긋나고 또! 그렇게 할 수가 없습니다.
하지만 이런 스택은 컴퓨터에서 많이 사용되는
데이타 타입입니다.
그런데!!
파이썬 리스트에선 그게 또 됩니다.. ㅠㅜ 혼동하지 마시길...이건 어디까지나 정의 입니다.
(조금 읽는 글이 많더라도
그냥 한번 정도 읽어 주시길...ㅠ__ㅠ)
$ Key
Point!!
파이썬에선 스택을 간단하게 이용해서 원하는 프로그램을 작성할 수 있습니다. 리스트라는 것만 알면여~ ^^;