Golang Program for implementation LIFO Stack and FIFO Queue

 

사전 지식


스택: 

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D#:~:text=%EC%8A%A4%ED%83%9D(stack)%EC%9D%80%20%EC%A0%9C%ED%95%9C%EC%A0%81%EC%9C%BC%EB%A1%9C,(Pushdown%20list)%EC%9D%B4%EB%9D%BC%EA%B3%A0%EB%8F%84%20%ED%95%9C%EB%8B%A4. 

스택 - 위키백과, 우리 모두의 백과사전

 

큐: 

https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전

스택(stack)과 큐(queue)는 자료구조(data structure)입니다.

자료구조는 데이터를 구성하고, 저장하고, 관리하며, 검색하기 위한 방법을 제공합니다.

스택은 Last-In-First-Out(LIFO) 방식으로 데이터를 저장하고, 추출합니다. 가장 마지막에 삽입된 데이터가 가장 먼저 추출됩니다. 스택은 push(삽입)와 pop(추출) 두 가지 연산을 제공합니다.

큐는 First-In-First-Out(FIFO) 방식으로 데이터를 저장하고, 추출합니다. 가장 먼저 삽입된 데이터가 가장 먼저 추출됩니다. 큐는 enqueue(삽입)와 dequeue(추출) 두 가지 연산을 제공합니다.

알고리즘에서는 자료구조를 이용해서 문제를 해결할 때가 많기 때문에, 스택과 큐 또한 알고리즘에서 많이 사용됩니다. 예를 들어,
괄호 검사, 후위 표기법 계산, BFS 탐색 등에서 스택과 큐가 활용됩니다.

 

---

 

코드 설명 

 

스택은 후입선출 즉 나중에 들어온 것이 먼저 나가는 데이터 구조고  큐는 선입선출입니다. 먼저 들어온 데이터가 먼저 나가는 데이터 구조입니다. 일상 사물로 비교하면 스택은 프링글스 통에 있는 과자고 큐는 고속도로 톨게이트 같은 것입니다. 프링글스를 먹고싶어도 위에 있는 것부터 먹어야하듯이 맨 위에 있는 데이터부터 빠지게 되는 것이고   고속도로 톨게이트는 먼저 간 사람이 먼저 표를 계산합니다.  데이터 구조와 알고리즘은 다음 코드와 같습니다. 

 

구조체와 함수 설명 

 

노드 구조체 정의 : 밸류 변수 정의

프린트 함수 : 출력 기능

뉴 스택 함수 :  새로운 스택을 반환한다. 

스택 구조체 : 스택의 데이터 구조를 정의함, node와 int를 정의함, 후입선출 구조

스택 Push 함수(삽입 기능) : 스택에 노드를 삽입하는 기능 

스택 Pop 함수(인출 기능) : 스택에 노드를 인출하는 기능

뉴 큐 함수 : 주어진 크기로 새 큐를 반환한다. 

큐 구조체 : 노드, 사이즈, 헤드, 테일, 카운트 등의 변수를 정의함, 선입선출 구조

큐 Push 함수(삽입 기능) : 큐에 노드 추가

큐 Pop 함수 (인출 기능) : 큐에 노드를 제거함 

메인 함수 : Push, Pop을 이용해서 스택과 큐의 데이터 흐름을 테스트하는 함수

 

package main

import (
	"fmt"
)

type Node struct {
	Value int
}

func (n *Node) String() string {
	return fmt.Sprint(n.Value)
}

// NewStack returns a new stack.
// NewStack 은 새 스택을 반환한다.
func NewStack() *Stack {
	return &Stack{}
}

// Stack is a basic LIFO stack that resizes as needed.
// 스택은 필요에 따라 크기를 조정하는 기본 LIFO 스택입니다.
type Stack struct {
	nodes []*Node
	count int
}

// Push adds a node to the stack.
// Push는 스택에 노드를 추가하는 것이다.
func (s *Stack) Push(n *Node) {
	s.nodes = append(s.nodes[:s.count], n)
	s.count++
}

// Pop removes and returns a node from the stack in last to first order.
// Pop은 스택에서 노드를 마지막 순서에서 첫 번째 순서로 제거하고 반환합니다.
func (s *Stack) Pop() *Node {
	if s.count == 0 {
		return nil
	}
	s.count--
	return s.nodes[s.count]
}

// NewQueue returns a new queue with the given initial size.
// NewQueue는 주어진 초기 크기로 새 큐를 반환합니다.
func NewQueue(size int) *Queue {
	return &Queue{
		nodes: make([]*Node, size),
		size:  size,
	}
}

// Queue is a basic FIFO queue based on a circular list that resizes as needed.
// 큐는 필요에 따라 크기를 조정하는 순환 목록을 기반으로 하는 기본 FIFO 큐입니다.
type Queue struct {
	nodes []*Node
	size  int
	head  int
	tail  int
	count int
}

// Push adds a node to the queue.
// 푸시는 큐에 노드를 추가합니다.
func (q *Queue) Push(n *Node) {
	if q.head == q.tail && q.count > 0 {
		nodes := make([]*Node, len(q.nodes)+q.size)
		copy(nodes, q.nodes[q.head:])
		copy(nodes[len(q.nodes)-q.head:], q.nodes[:q.head])
		q.head = 0
		q.tail = len(q.nodes)
		q.nodes = nodes
	}
	q.nodes[q.tail] = n
	q.tail = (q.tail + 1) % len(q.nodes)
	q.count++
}

// Pop removes and returns a node from the queue in first to last order.
// Pop은 큐에서 노드를 제거하고 첫 번째 순서부터 마지막 순서로 반환합니다.
func (q *Queue) Pop() *Node {
	if q.count == 0 {
		return nil
	}
	node := q.nodes[q.head]
	q.head = (q.head + 1) % len(q.nodes)
	q.count--
	return node
}

func main() {
	s := NewStack()
	s.Push(&Node{3})
	s.Push(&Node{5})
	s.Push(&Node{7})
	s.Push(&Node{9})
	fmt.Println(s.Pop(), s.Pop(), s.Pop(), s.Pop())

	q := NewQueue(1)
	q.Push(&Node{2})
	q.Push(&Node{4})
	q.Push(&Node{6})
	q.Push(&Node{8})
	fmt.Println(q.Pop(), q.Pop(), q.Pop(), q.Pop())
}

 

출처: 

https://www.golangprograms.com/data-structure-and-algorithms/golang-program-for-implementation-lifo-stack-and-fifo-queue.html 

LIFO Stack and FIFO Queue in Go (Golang) - golangprograms.com