관리 메뉴

don't stop believing

Stack - 스택 본문

Golang/Basic

Stack - 스택

Tongchun 2019. 5. 15. 18:43

자료구조 중 스택입니다.
Stack과 Queue는 항상 같이 설명됩니다.

 

https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

 

Stack (abstract data type) - Wikipedia

From Wikipedia, the free encyclopedia Jump to navigation Jump to search Simple representation of a stack runtime with push and pop operations. In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal

en.wikipedia.org

Stack에서 중요한 개념은 LIFO (Last-In, First-Out) 입니다. 가장 마지막에 들어간 데이터가 가장 처음 나오게 됩니다.

Stack에서는 Push, Pop, Peek이 있으며 아래 코드에서 개념을 확인할 수 있습니다.

Go로 구현된 코드입니다.

package main

import "fmt"

// StackItem 구조체입니다. 값과 다음 StackItem을 가지고 있습니다.
type StackItem struct {
	item interface{}
	next *StackItem
}

// Stack 구조체는 StackItem과 Stack의 깊이를 가지고 있습니다.
type Stack struct {
	sp    *StackItem // Stack에서 가장 위에 있는 아이템을 저정합니다.
	depth uint64     // Stack에 아이템이 몇개 있는지를 저장합니다.
}

// Stack을 생성합니다.
func New() *Stack {
	var stack *Stack = new(Stack)

	stack.depth = 0
	return stack
}

// Stack에 아이템을 집어 넣습니다.
func (stack *Stack) Push(item interface{}) {
	stack.sp = &StackItem{item: item, next: stack.sp}
	stack.depth++
}

// Stack에서 가장 위에 있는 아이템을 제거합니다.
// 가장 위에있는 아이템을 제거하고 그 다음 아이템을 위로 올립니다.
func (stack *Stack) Pop() interface{} {
	if stack.depth > 0 {
		item := stack.sp.item
		stack.sp = stack.sp.next
		stack.depth--
		return item
	}

	return nil
}

// Stack의 가장 위에 있는 아이템을 확인합니다.
// 아이템을 제거되지 않고 읽기만 합니다.
func (stack *Stack) Peek() interface{} {
	if stack.depth > 0 {
		return stack.sp.item
	}

	return nil
}

func main() {
	var stack *Stack = New()

	stack.Push(10)
	stack.Push(20)
	stack.Push(30)
	stack.Push(40)
	stack.Push(50)

	// 가장 나중에 들어간 데이터가 가장 먼저 나옵니다. (LIFO)
	for i := 5; i > 0; i-- {
		item := stack.Pop()

		fmt.Println(item)
	}
}

Stack은 Queue와 같이 이해하면 좋습니다.

 

'Golang > Basic' 카테고리의 다른 글

Queue - 큐  (0) 2019.05.15
Stack - 스택  (0) 2019.05.15
Binary Search Tree - 이진 탐색 트리  (0) 2019.05.15
Doubly Linked List - 이중 연결 리스트  (0) 2019.05.13
Binary Search - 이진 검색  (0) 2019.05.13
Jump Point Search - 점프 포인트 서치 (블록 탐색)  (0) 2019.05.13
0 Comments
댓글쓰기 폼