Pelajaran 4 dalam bahasa Pemrograman Go

Hai Guys... bagaimana dengan kabar kalian? Baik-baik aja kan. O ya bagaimana dengan materi yang sebelumnya, sudah paham?

Hari ini, saya ingin share tentang stack and queue

Ini merupakan gambaran dari Stack and Queue



Stack

Stack (tumpukan) merupakan struktur data LIFO (last in, first out). Stack umumnya di implementasikan dengan array atau linked list. Stack umumnya memiliki beberapa method penting, diantaranya:

● peek/top, untuk melihat data paling atas
● push, untuk menaruh item ke atas tumpukan
● pop, untuk mengambil item teratas dari tumpukan
● print n, untuk mencetak jumlah data pada tumpukan dan n data teratas

● count/is_empty, untuk memeriksa jumlah data di dalam stack

Di bawah ini merupakan contoh dari source codenya:

Go slices make excellent stacks without defining any extra types, functions, or methods. For example, to keep a stack of integers, simply declare one as,

var intStack []int

Use the built in append function to push numbers on the stack:

intStack = append(intStack, 7)

Use a slice expression with the built in len function to pop from the stack:

popped, intStack = intStack[len(intStack)-1], intStack[:len(intStack)-1]

The test for an empty stack:

len(intStack) == 0

And to peek at the top of the stack:

intStack[len(intStack)-1]

It is idiomatic Go to use primitive language features where they are sufficient, and define helper functions or types and methods only as they make sense for a particular situation. Below is an example using a type with methods and idiomatic "ok" return values to avoid panics. It is only an example of something that might make sense in some situation.

package main
 
import "fmt"
 
type stack []interface{}
 
func (k *stack) push(s interface{}) {
    *k = append(*k, s)
}
 
func (k *stack) pop() (s interface{}, ok bool) {
    if k.empty() {
        return
    }
    last := len(*k) - 1
    s = (*k)[last]
    *k = (*k)[:last]
    return s, true
}
 
func (k *stack) peek() (s interface{}, ok bool) {
    if k.empty() {
        return
    }
    last := len(*k) - 1
    s = (*k)[last]
    return s, true
}
 
func (k *stack) empty() bool {
    return len(*k) == 0
}
 
func main() {
    var s stack
    fmt.Println("new stack:", s)
    fmt.Println("empty?", s.empty())
    s.push(3)
    fmt.Println("push 3. stack:", s)
    fmt.Println("empty?", s.empty())
    s.push("four")
    fmt.Println(`push "four" stack:`, s)
    if top, ok := s.peek(); ok {
        fmt.Println("top value:", top)
    } else {
        fmt.Println("nothing on stack")
    }
    if popped, ok := s.pop(); ok {
        fmt.Println(popped, "popped.  stack:", s)
    } else {
        fmt.Println("nothing to pop")
    }
}

new stack: []
empty? true
push 3. stack: [3]
empty? false
push "four" stack: [3 four]
top value: four
four popped.  stack: [3]

Queue

Queue (antrian) merupakan struktur data FIFO (first in, first out). Queue umumnya diimplementasikan dengan circular buffer atau linked list.
Queue umumnya memiliki beberapa method penting, diantaranya:

● peek/front/first, untuk melihat data paling depan
● back/last, untuk melihat data paling belakang ● enqueue, untuk mengantri
● dequeue, untuk mengeluarkan item terdepan dari antrian
● print n, untuk mencetak jumlah data pada tumpukan dan n data terdepan
● count/is_empty, untuk memeriksa jumlah data di dalam queue

Terdapat beberapa jenis queue, yaitu:

● Priority queue merupakan antrian dengan prioritas tertentu(akan dipelajari di bagian berikutnya)
● Deque (Double­ended queue) merupakan antrian 2 arah, data bisa masuk dan keluar dari depan maupun belakang.



Ini merupakan contoh source codenya:

package queue
 
// int queue
// the zero object is a valid queue ready to be used.
// items are pushed at tail, popped at head.
// tail = -1 means queue is full
type Queue struct {
    b []string
    head, tail int
}
 
func (q *Queue) Push(x string) {
    switch {
    // buffer full. reallocate.
    case q.tail < 0:
        next := len(q.b)
        bigger := make([]string, 2*next)
        copy(bigger[copy(bigger, q.b[q.head:]):], q.b[:q.head])
        bigger[next] = x
        q.b, q.head, q.tail = bigger, 0, next+1
    // zero object. make initial allocation.
    case len(q.b) == 0:
        q.b, q.head, q.tail = make([]string, 4), 0 ,1
        q.b[0] = x
    // normal case
    default:
        q.b[q.tail] = x
        q.tail++
        if q.tail == len(q.b) {
            q.tail = 0
        }
        if q.tail == q.head {
            q.tail = -1
        }
    }
}
 
func (q *Queue) Pop() (string, bool) {
    if q.head == q.tail {
        return "", false
    }
    r := q.b[q.head]
    if q.tail == -1 {
        q.tail = q.head
    }
    q.head++
    if q.head == len(q.b) {
        q.head = 0
    }
    return r, true
}
 
func (q *Queue) Empty() bool {
    return q.head == q.tail
}
 

Sumber:
http://rosettacode.org/wiki/Stack#Go
http://www.cmpe.boun.edu.tr/~akin/cmpe223/fig2_1.gif
http://www.cs.cmu.edu/~mrmiller/15-121/Homework/hw8/queueOps.png
http://rosettacode.org/wiki/Queue/Definition#Go
Materi dosen