Implementing Stack & Queue in go (golang)



First lets define the interface for Stack,

type Stack interface {
    Push(value interface{})
    Pop() (interface{}, bool)
    Peek() (interface{}, bool)
    HasNext() bool
    Len() int
}

We can use the doubly linked from "container/list" to implement our Stack,
just import "container/list"

Define a type which implements our Stack interface,

type stack struct{
    list *list.List
}


We can have constructor which returns the stack instance,
func NewStack() Queue{
    return &stack{list: list.New()}
}

We can leverage the PushFront() and Front() list methods to push values to the head
and get hold of the first element

func (this *stack) Push(value interface{}){
    this.list.PushFront(value)
}

The Front() method return a pointer to Element type in list package,
the actual value in list is stored in Element's Value field.


func (this *stack) Pop() (interface{}, bool){
    e := this.list.Front()
    if e == nil{
        return nil,false
    }
    this.list.Remove(e)
    return e.Value,true
}

similarly we can implement Peek(), we just skip the Remove() from Pop.

Len() and HasNext() can leverage the Len() method of list,

func (this *stack) Len() int{
    return this.list.Len()
}

func (this *stack) HasNext() bool{
    return this.list.Len() != 0
}





On the same lines we can implement Queue by leveraging
list.PushBack() method in Push() of Queue method.

Implementing Set backed by map in golang

Here is the simple implementation of set

We can define the interface as 

type Set interface { Add(data interface{}) Delete(data interface{}) bool Contains(data interface{}) bool Size() int ToArray() []interface{} Print() }

lets define a type which implements our Set interface,

type set struct {

  mymap map[interface{}]struct{}

  empty struct{}

}

the map is the actual data holder here.

here is the implementation for the Set interface method.

func NewSet() Set { return &set{mymap: make(map[interface{}]struct{})} } func (this *set) Add(data interface{}) { this.mymap[data] = this.empty }

// there may be a better approach func (this *set) Delete(data interface{}) bool { _, ok := this.mymap[data] if ok { delete(this.mymap, data) } return ok } func (this *set) Contains(data interface{}) bool { _, ok := this.mymap[data] return ok } func (this *set) Size() int { return len(this.mymap) } func (this *set) ToArray() []interface{} { size := len(this.mymap) arr := make([]interface{}, size) i := 0 for k, _ := range this.mymap { arr[i] = k i++ } return arr }

Checking for nil in go (golang)

Well, am trying to check for nil in golang,

Looks like this utility may help

func IsNil(i interface{}) bool {
    if i == nil {
        return true
    }
    val := reflect.ValueOf(i)
    kind := val.Kind()
    switch kind {
    case reflect.Ptr, reflect.Chan, reflect.Func, reflect.Map, reflect.Slice, reflect.Interface:
        return val.IsNil()
    }
    return false
}
need to import "reflect" package.

Using JSch to download files.

JSch is a popular java library to connect to SSHD server.

Here is the code listing which connects to the SSHD server to download and upload files.

package com.mm.ftpclient;

import java.io.Closeable;
import java.io.FileInputStream;
import java.util.List;

import com.jcraft.jsch.Channel;
import com.jcraft.jsch.ChannelSftp;
import com.jcraft.jsch.ChannelSftp.LsEntry;
import com.jcraft.jsch.JSch;
import com.jcraft.jsch.Session;

public class SftpUtil {

// can be used to filter the files, not implemented here.
public interface LsEntryFilter{
boolean accept(LsEntry e);
}

public static Session getSession(String hostIp, String username, String password)
        throws Exception {
log("SFTPUtil : entering getSession....");
JSch jsch = new JSch();
Session session = jsch.getSession(username, hostIp);
session.setPassword(password);
session.setConfig("StrictHostKeyChecking", "no");
log("SFTPUtil : exiting getSession....");
return session;
}

public static ChannelSftp getChannelSftp(Session session) throws Exception {
Channel channel = session.openChannel("sftp");
channel.setInputStream(System.in);
channel.setOutputStream(System.out);
channel.connect();

ChannelSftp sftpChannel = (ChannelSftp) channel;
return sftpChannel;
}


// updloads the src file to remote server.
public static void uploadFile(Session session, String srcFile, String destFile)
        throws Exception {
log("SFTPUtil : Entering uploadFile.....");

ChannelSftp sftpChannel = getChannelSftp(session);
FileInputStream is = new FileInputStream(srcFile);

try {
sftpChannel.put(is, destFile);
} finally {
close(is);
if (sftpChannel != null)
sftpChannel.disconnect();
}
log("SFTPUtil : Exiting uploadFile.....");
}

public static void downloadFile(Session session, String srcDir, String destDir,
        String fileName) throws Exception {
ChannelSftp sftpChannel = getChannelSftp(session);
List<ChannelSftp.LsEntry> list = getFiles(sftpChannel, srcDir, destDir);
try {
log("SFTPUtil : ls command output is :" + list);
for (ChannelSftp.LsEntry file : list) {
if (!file.getAttrs().isDir() && file.getFilename().equals(fileName)) {
log("SFTPUtil : downloading file to local working dir, filename is : [" +                                                      file.getFilename() + "]");
sftpChannel.get(file.getFilename(), file.getFilename());
}
}
} finally {
if (sftpChannel != null)
sftpChannel.disconnect();
}
}


public static List<ChannelSftp.LsEntry> getFiles(ChannelSftp sftpChannel, String srcDir,
        String destDir) throws Exception {

sftpChannel.lcd(destDir);
log("SFTPUtil : local working dir: " + sftpChannel.lpwd());

sftpChannel.cd(srcDir);
log("SFTPUtil : remote working dir: " + sftpChannel.pwd());

// Get a listing of the remote directory
@SuppressWarnings("unchecked")
List<ChannelSftp.LsEntry> list = sftpChannel.ls(".");
log("SFTPUtil : running command 'ls .' on remote server : ");

return list;
}



private static void log(String msg) {
System.out.println(msg);
}

private static void close(Closeable is) {
try {
if (is != null)
is.close();
} catch (Exception e) {
}
}

}

Here is the driver code to test

public static void test() throws Exception{
Session session = SftpUtil.getSession("127.0.0.1", "demo", "demo");
session.connect();
try{
List<LsEntry> files = SftpUtil.getFiles(getChannelSftp(session), "/test", "c:/test");
for(LsEntry  file : files){
System.out.println(file.getFilename());
}
}finally{
session.disconnect();
}
}

Simple Linked List in go

Here is the code listing for simple linked list in go.

package datastruct

import (

"bytes"

"fmt"

"sync"

)

type node struct {

data interface{}

link *node

}

type llist struct {

size       int32

head, tail *node

lock       sync.Mutex

}

type LList llist

func NewLList() *LList {

node := new(LList)

return node

}

func (this *LList) Add(data interface{}) {

this.add(data, true)

}

func (this *LList) Delete(value interface{}) bool {

return this.delete(value)

}

func (this *LList) Contains(data interface{}) bool {

for list := this.head; list != nil; list = list.link {

if list.data == data {

return true

}

}

return false

}

func (this *LList) Size() int32 {

return this.size

}

//--- functions to support Stack & Queue

func (this *LList) AddFirst(data interface{}) {

this.add(data, false)

}

func (this *LList) RemoveFirst() bool {

if this.head == nil {

return false

}

return this.Delete(this.head.data)

}

func (this *LList) First() (bool, interface{}) {

if this.head == nil {

return false, nil

}

return true, this.head.data

}

func (this *LList) Last() (bool, interface{}) {

if this.tail == nil {

return false, nil

}

return true, this.tail.data

}

//------ util methods -------------------->

func (this *LList) Lock() sync.Mutex {

return this.lock

}

//------ toString in golang

func (this *LList) String() string {

var buffer bytes.Buffer

buffer.WriteString("LList [")

list := this.head

for list != nil {

buffer.WriteString(fmt.Sprint(list.data))

list = list.link

if list != nil {

buffer.WriteString(" ")

}

}

buffer.WriteString("]")

return buffer.String()

}

//------ debug info

func (this *LList) Print() {

var headdata, taildata interface{}

if this.head != nil {

headdata = this.head.data

}

if this.tail != nil {

taildata = this.tail.data

}

fmt.Println("Size:", this.Size(), "Head=", headdata, "Tail=", taildata, " --> ", this)

}

//------------ private methods---------------------->

func (this *LList) delete(value interface{}) bool {

result := false

if this.head != nil && this.head.data == value {

this.head = this.head.link

if this.head == nil {

this.tail = nil

}

result = true

} else if this.head != nil {

prev := this.head

for curr := this.head.link; curr != nil; curr = curr.link {

if curr.data == value {

prev.link = curr.link

if this.tail == curr {

this.tail = prev

}

result = true

break

}

}

}

if result {

this.size -= 1

}

return result

}

func (this *LList) add(data interface{}, action bool) {

lnode := new(node)

lnode.data = data

if this.head == nil {

this.head = lnode

this.tail = this.head

} else if action {

this.tail.link = lnode

this.tail = lnode

} else {

lnode.link = this.head

this.head = lnode

}

this.size += 1

}

Here is the driver class to test the link list.

package main

import (

"datastruct"

"fmt"

)

func main(){

       list := datastruct.NewLList()

list.Add(50)

list.Add(60)

list.Add(70)

list.Add(80)

list.AddFirst(40)

list.AddFirst(30)

list.AddFirst(20)

list.AddFirst(10)

list.Add(90)

list.Add(100)

fmt.Println(list)

fmt.Println("contains 10", list.Contains(10))

fmt.Println("contains 40", list.Contains(40))

fmt.Println("contains 110", list.Contains(110))

}

Link to code   https://github.com/Fazal-Khan/learngo