[자료구조] 06. 스택 (Stack)

사담 공간

드디어 고오급 자료구조에 입문하게 된다..!! 그래도 스택이랑 큐까지는 할만했던 것 같은데 트리부터가...허허

알고리즘 전까지는 최대한 개강 전에 끝내보자 ㅠㅠ

키워드

#스택 #후입선출 #LIFO

1. 스택 개념

스택(Stack)은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형구조(LIFO) 로 되어있다.

스택의 핵심이자 큐 같은 자료구조와 구별되는 가장 큰 차이점은 바로 이 "LIFO"라는 개념이다.

LIFO (Last In First Out), 후입선출

영어와 한자 해석 그대로, "제일 마지막에 들어온 데이터가 제일 먼저 나간다" 라는 뜻이다.

사실 글로 읽기보다는 그림으로 보면 이해가 빠르다.

그림과 함께 보면 당연하게 느껴진다.

한쪽이 막혀있으니, 한쪽으로만 자료를 꺼낼 수 있고, 꺼낼 수 있는 자료는 맨 위에 쌓여있던 (가장 최근에 입력된) 데이터일 것이다!

따라서 스택의 삽입과 삭제는 스택의 맨 윗 지점에서만 일어나며, 이를 top 이라고 지칭한다.

위 내용은 후에 나올 큐(queue) 자료구조와 스택을 구분짓는 가장 큰 차이점이므로 꼭 기억해두자!

2. 스택 ADT & 구현

스택 메서드 ADT

일반 메서드

void initialize() : 초기 스택 생성

주요 스택 메서드

void push(e) : 스택에 원소를 삽입
element pop() : 스택에서 원소 삭제 후 반환

보조 스택 메서드

element top() : 가장 최근에 삽입된 원소 반환
integer size() : 저장된 원소의 개수를 반환
boolean isEmpty() : 아무 원소도 저장되어 있지 않고 비어있는지 여부를 반환

예외

emptyStackException() : 비어 있는 스택에서 삭제나 top 시도할 경우
fullStackException() : 꽉 차 있는 스택에서 삽입 시도할 경우 발령

스택 구현

배열을 이용한 구현

크기 N의 배열을 사용해 원소들을 배열의 왼쪽 -> 오른쪽으로 추가
변수 t = top 원소의 인덱스

일반 메서드

void initialize() : 초기 스택 생성

Alg initialize()
    // input : size N, top t
    // output : empty stack S
    
    S = array()
    t = -1
    return S

주요 스택 메서드

void push(e) : 스택에 원소를 삽입

Alg push(e)
    // input : stack S, size N, top t, element e
    // output : none

    if (t = N - 1)
        fullStackException()
    
    t = t + 1
    S[t] = e
    return

element pop() : 스택에서 원소 삭제 후 반환

Alg pop()
    // input : stack S, size N, top t
    // output : element

    if (isEmpty())
        emptyStackException()
    
    t = t - 1
    return S[t+1]

보조 스택 메서드

element top() : 가장 최근에 삽입된 원소 반환

Alg top()
    if (isEmpty())
        emptyStackException()
    return S[t]

integer size() : 저장된 원소의 개수를 반환

Alg size()
    return t + 1

boolean isEmpty() : 아무 원소도 저장되어 있지 않고 비어있는지 여부를 반환

Alg isEmpty()
    if (t = -1)
        return true

    else
        return false

<파이썬 구현>

# stack_array.py

class stack_array:
    def __init__(self, N):
        self.arr = ['NULL'] * N
        print(len(self.arr))
        self.n = N
        self.t = -1
    
    def push(self, e):
        if self.t == self.n - 1:
            print("fullStackException")
        
        self.t += 1
        self.arr[self.t] = e
        return
    
    def pop(self):
        if self.isEmpty():
            print("emptyStackException")
        self.t -= 1
        return self.arr[self.t+1]
    
    def isEmpty(self):
        if self.t == -1:
            return True
        else:
            return False
    
    def size(self):
        return self.n
    
    def top(self):
        if self.isEmpty():
            print("emptyStackException")
        return self.arr[self.t]

# stack.py

from stack_array import stack_array

stack = stack_array(10)

stack.push('a')
stack.push('b')
stack.push('d')
stack.push('e')
print('top :', stack.top(), 'size :', stack.size())
print('remove', stack.pop())
print('top :', stack.top(), 'size :', stack.size())
stack.push('g')
print('top :', stack.top(), 'size :', stack.size())
stack.pop()
stack.pop()
stack.pop()
stack.pop()
stack.pop()

<실행 결과>

성능

스택의 원소 개수가 n일 때,

기억장소 사용 : O(n)
각 작업의 실행 시간 : O(1)

제약

스택의 최대 크기를 예측해야 하며 크기를 실행 중에 변경할 수 없다
만원인 스택에 새로운 원소를 push 시도할 경우 구현상의 오류를 일으킨다

연결리스트를 이용한 구현

단일연결리스트를 사용해서 스택을 구현할 수 있다

-> 삽입 / 삭제 기능이 top에서만 수행되므로 헤더노드는 불필요

top 원소를 연결리스트의 첫 노드에 저장하고, 그곳을 t로 가리키게 한다

일반 메서드

void initialize() : 초기 스택 생성

Alg initialize()
    // input top t
    // output an empty stack with top t

    // 초기에는 아무 노드도 없다
    t = NULL
    return

주요 스택 메서드

void push(e) : 스택에 원소를 삽입

Alg push(e)
    // input top t, element e
    // output none
    p <- getnode()
    p.elem <- e
    p.next <- t
    t <- p
    return

element pop() : 스택에서 원소 삭제 후 반환

Alg pop()
    // input top t
    // output element
    if (isEmpty())
        emptyStackException()
    e <- t.elem
    p <- t
    t <- t.next
    putnode(p)
    return e

보조 스택 메서드

element top() : 가장 최근에 삽입된 원소 반환

Alg top()
    // input top t
    // output element
    return t.elem

integer size() : 저장된 원소의 개수를 반환

Alg size()
    // input None
    // output None
    p = t
    n = 0
    while (p != NULL)
        n += 1
    return n

boolean isEmpty() : 아무 원소도 저장되어 있지 않고 비어있는지 여부를 반환

Alg isEmpty()
    // input top t
    // output boolean

    if t = NULL
        return true
    else
        return false

<파이썬 구현>

# singly_linked_list.py

from asyncio.windows_events import NULL


class node():
    def __init__(self, data, next=NULL):
        self.data = data
        self.next = next

class singly_linked_list():
    
    # 동적 할당 받으면 되니까 처음부터 공간 얼마 필요한지 필요 X
    def __init__(self):
        self.head = node(NULL)
        self.n = 0
    
    # 일반 메서드
    def isEmpty(self):
        if self.n == 0:
            return True
        else:
            return False
    
    def size(self):
        return self.n
    
    def traverse(self):
        p = self.head
        while p != NULL:
            print(p.data, end=' ')
            p = p.next
        print()
        return
    
    # 접근 메서드
    def get(self, r):
        if r<1 or r>self.n:
            print("invalidRankException")
            return NULL
        else:
            p = self.head
            for i in range(1, r+1):
                p = p.next
            return p.data
    
    # 갱신 메서드
    def set(self, r, e):
        if r<1 or r>self.n:
            print("invalidRankException")
            return NULL
        else:
            p = self.head
            for i in range(1, r+1):
                p = p.next
            p.data = e
            return e
        
    def addFirst(self, e):
        p = self.head

        q = node(e, p.next)
        p.next = q
        self.n += 1
        return
    
    
    def removeFirst(self):
        if self.n == 0:
            print("emptyListException")
            return NULL
        else:
            p = self.head

            e = p.data
            p.next = (p.next).next

            self.n -= 1
            return e

# stack_linked_list.py
from asyncio.windows_events import NULL
from single_linked_list import singly_linked_list, node

class stack_linked_list:
    def __init__(self):
        self.linked_list = singly_linked_list()
        self.t = self.linked_list.head
    
    def push(self, e):
        p = node(e, self.t.next)
        self.t.next = p
        return

    def pop(self):
        if self.isEmpty():
            print("emptyStackException")
            return NULL
        e = self.t.next.data
        self.t.next = (self.t.next).next

        return e


    def isEmpty(self):
        if self.t.next == NULL:
            return True
        else:
            return False

    def size(self):
        p = self.t.next
        n = 0

        while p != NULL:
            n += 1
            p = p.next

        return n
    
    def top(self):
        return self.t.next.data

# stack.py

from stack_linked_list import stack_linked_list

stack = stack_linked_list()

stack.push('a')
stack.push('b')
stack.push('d')
stack.push('e')
print('top :', stack.top(), 'size :', stack.size())
print('remove', stack.pop())
print('top :', stack.top(), 'size :', stack.size())
stack.push('g')
print('top :', stack.top(), 'size :', stack.size())
stack.pop()
stack.pop()
stack.pop()
stack.pop()
stack.pop()

<실행 결과>

성능

스택의 원소 개수가 n일 때,

기억장소 사용 : O(n)
각 작업의 실행 시간 : O(1)

3. 스택 응용

추후 포스팅에서 다루도록 하겠다.

'알고리즘 > 자료구조_알고리즘' 카테고리의 다른 글

[자료구조] 08. 트리 (0)	2022.08.29
[자료구조] 07. 큐 (Queue) & 덱 (Dequeue) (0)	2022.08.29
[자료구조] 05. 집합 (0)	2022.08.25
[자료구조] 04(2). 연결리스트 확장 및 응용 (0)	2022.08.20
[자료구조] 04(1). 연결리스트 구현 (0)	2022.08.11

그냥이것저것

[자료구조] 06. 스택 (Stack)

1. 스택 개념

LIFO (Last In First Out), 후입선출

2. 스택 ADT & 구현

스택 메서드 ADT

일반 메서드

주요 스택 메서드

보조 스택 메서드

예외

스택 구현

배열을 이용한 구현

연결리스트를 이용한 구현

3. 스택 응용

'알고리즘 > 자료구조_알고리즘' 카테고리의 다른 글

티스토리툴바

[자료구조] 06. 스택 (Stack)

1. 스택 개념

LIFO (Last In First Out), 후입선출

2. 스택 ADT & 구현

스택 메서드 ADT

일반 메서드

주요 스택 메서드

보조 스택 메서드

예외

스택 구현

배열을 이용한 구현

연결리스트를 이용한 구현

3. 스택 응용

'알고리즘 > 자료구조_알고리즘' 카테고리의 다른 글

관련글

티스토리툴바