Shortest implementation of a linked list, stack and queue

Question

Challenge

Write the shortest program that implements the minimum requirements for a linked list, stack and queue.

Minimum requirements

• Functions that allow the user to add and remove elements from the linked list, stack and queue.
• Any data type can be added to the linked list, stack and queue (string, int, etc.).
• One special function (e.g. sort letters alphabetically).
• The program must work (compile without errors and operations and results should make sense in the context of linked lists, stacks and queues)!
• Lastly, this program must be hard-coded. Arrays, however, are allowed (please refer to the restrictions section).

Winning criteria

• Standard Codegolf rules.
• Number of characters based on the summation of characters for linked list, stack and queue.

Restrictions

• No trivial answers (i.e. 0 or 1 for a stack based language).
• You are allowed to write the program in any language except for stack-based languages (let me know if this is unfair).
• You cannot simply use the functions of another class. If a language (like Ruby) already has push and pop functions in arrays or any other class, you must write your own push and pop functions.

---

Little blurb: If this code golf challenge is too simple, I will add more requirements. I'm also open to any suggestions.

Answer 1

Haskell, 81 69 characters

data L a=N|a:~L a
N~:z=z:~N
(a:~b)~:z=a:~(b~:z)
r N=N
r(a:~z)=r z~:a

This code makes use of no preexisting functions at all. The push operation is :~, the enqueue operation is ~:. Both pop and dequeue are via pattern match against :~. The extra operation r is reverse.

Stacks:

ex1 =
    let stack0 = N                      -- empty stack
        stack1 = 'a' :~ stack0          -- push 'a'
        stack2 = 'b' :~ stack1          -- push 'b'
        first :~ stack3 = stack2        -- pop
        second :~ stack4 = stack3       -- pop
    in mapM_ print [first, second]

—

λ: ex1
'b'
'a'

Queues:

ex2 =
    let queue0 = N                      -- empty queue
        queue1 = queue0 ~: 'x'          -- enq 'x'
        queue2 = queue1 ~: 'y'          -- enq 'y'
        queue3 = queue2 ~: 'z'          -- enq 'z'
        next0 :~ queue4 = queue3        -- deq
        next1 :~ queue5 = queue4        -- deq
        next2 :~ queue6 = queue5        -- deq
    in mapM_ print [next0, next1, next2]

—

λ: ex2
'x'
'y'
'z'

List reverse operation:

ex3 =
    let list = "alpha" :~ ("beta" :~ ("gamma" :~ N)) -- a list
        tsil = r list                   -- reverse the list
        native N = []                   -- convert to native list
        native (a:~z) = a : native z    -- for easy printing
    in mapM_ (print . native) [list, tsil]

—

λ: ex3
["alpha","beta","gamma"]
["gamma","beta","alpha"]

Answer 2

Ruby, 123

class S
def initialize
@a=[]
end
def u n
@a[@a.size]=n
end
def o
@a.slice! -1
end
def s
@a.slice!0
end
def j x
@a*x
end
end

Example:

s = S.new     # initialize
s.u 5         # push 5
s.u 10        # push 10
s.u [1,2,3]   # push [1,2,3]
s.u "test"    # push "test"
s.u "test2"   # push "test2"
puts s.s      # shift - queue behaivior (remove and return first element, 5)
puts s.o      # pop - stack behaivior (remove and return last element, "test2")
puts s.j ", " # join - special behavior (join elements with argument, "10, 1, 2, 3, test")

Answer 3

C, 659 bytes

Try Online

typedef M;typedef struct M{int d;M*n;M*p;}Q;typedef struct{Q*f;Q*e;}L;Q*t;x;
Q*F(L**l){return*l?(*l)->f:0;}
Q*E(L**l){return*l?(*l)->e:0;}
N(Q**t){*t=*t?(*t)->n:0;}
P(Q**t){*t=*t?(*t)->p:0;}
A(L**l,int d){Q*t=(Q*)malloc(sizeof(Q));t->d=d;if(*l)(*l)->f->p=t,t->n=(*l)->f,(*l)->f=t;else(*l)=(L*)malloc(sizeof(L)),(*l)->f=t,(*l)->e=t;}
B(L**l){if(*l)t=(*l)->f,(*l)->f=t->n,(*l)->f->p=0,x=t->d,free(t);if(!(*l)->f)free(*l);return x;}
C(L**l,int d){t=(Q*)malloc(sizeof(Q));t->d=d;if(*l)(*l)->e->n=t,t->p=(*l)->e,(*l)->e=t;else (*l)=(L*)malloc(sizeof(L)),(*l)->f=t,(*l)->e=t;}
D(L**l){if(*l)t=(*l)->e,(*l)->e=t->p,(*l)->e->n=0,x=t->d,free(t);if(!(*l)->e)free(*l);return x;}

Detailed github

typedef _LNode; typedef struct _LNode{ void* d; _LNode* n; _LNode* p; } LNode;
typedef _List; typedef struct _List{ LNode* f; LNode* e; int size; } List;

LNode* list_begin(List** l){ return *l?(*l)->f:0; }
LNode* list_end(List** l){ return *l?(*l)->e:0; }

void list_iterator_next(LNode** t){ *t = *t?(*t)->n:0; }
void list_iterator_prev(LNode** t){ *t = *t?(*t)->p:0; }

int list_size(List** l){ return *l?(*l)->size:0; }

void list_push_front(List** l, void* d)
{
    LNode*t = (LNode)malloc(sizeof(LNode));
    t->d = d;

    if(*l)
        (*l)->f->p = t,
        t->n = (*l)->f,
        (*l)->f = t;
    else
        (*l)=(List*)malloc(sizeof(List)),
        (*l)->f = t,
        (*l)->e = t;

    (*l)->size++;
}

void list_push_back(List** l, void* d)
{
    LNode*t = (LNode)malloc(sizeof(LNode));
    t->d = d;

    if(*l)
        (*l)->e->n = t,
        t->p = (*l)->e,
        (*l)->e = t;
    else
        (*l)=(List*)malloc(sizeof(List)),
        (*l)->f = t,
        (*l)->e = t;

    (*l)->size++;
}

void* list_pop_front(List** l)
{
    LNode* t = 0;
    void* d = 0;

    if(*l)
        t = (*l)->f,
        (*l)->f = t->n,
        (*l)->f->p = 0,
        d = t->d,
        free(t),
        (*l)->size--;

    if(!(*l)->f) free(*l);

    return d;
}

void* list_pop_back(List** l)
{
    LNode* t = 0;
    void* d = 0;

    if(*l)
        t = (*l)->e,
        (*l)->e = t->p,
        (*l)->e->n = 0,
        d = t->d,
        free(t),
        (*l)->size--;

    if(!(*l)->e) free(*l);

    return d;
}

Answer 4

JavaScript, 188

function L(){N=null;E=[N,N];t=this;h=E;t.u=i=>h=[i,h];
t.o=_=>h==E?N:h[+!(h=h[1])];t.e=(i,l)=>h=(l||h)==E?[i, 
E]:[(l||h)[0],t.e(i,(l||h)[1])];t.s=_=>{o="";while(i=t.o())
{o+=i+","}return o}}

(Line breaks added for readability, not needed for answer or counted as bytes)

Usage

Methods

• u(item): Push
• o() -> item: Pop (or dequeue)
• e(item): Enqueue
• s() -> string: Convert to a string

Example

let failed = _ => { throw Error(); };
let list = new L();

// Stack
list.u(1);
list.u(3);

list.o() === 3 || failed();
list.u(2);
list.o() === 2 || failed();
list.o() === 1 || failed();
list.o() === null || failed();

// Queue

list.e(1);
list.e(2);

list.o() === 1 || failed();
list.e(3);
list.o() === 2 || failed();
list.o() === 3 || failed();
list.o() === null || failed();

// Reverse
list.u(1);
list.u(2);
list.u(3);

list.s() === "3,2,1," || failed();

Explanation

function L(){
    N=null; // end marker
    // a node has the format [item, rest]
    E=[N,N]; // end marker, is a node
    t=this;
    h=E; // head of list, is a node

    t.d = _ => JSON.stringify(h);

    t.u=i=>h=[i,h]; // push

    t.o=_=> // pop/deque
        h==E?
        N:
        h[+!(h=h[1])]; // set head to rest, return item (index into zeroth index by casting an assignment to a value to a bool to a float)

    // t.e acts recursively, we use `||` to set a default for when the user calls
    t.e=(i,l)=> // enqueue (user caller leaves `l` undefined)
        h=
            (l||h)==E?
                [i, E]: // if at end, insert new item right before
                [(l||h)[0],t.e(i,(l||h)[1])]; // else keep current value and process rest recursively

    t.s=_=>{
        o="";
        while(i=t.o()) {
            o+=i+","
        }
        return o
    }
}

Notes

List can't store anything JavaScript casts to false (null, false, 0, [], etc.). Repeated pop operations on an empty list have no effect. Ignore the return values of push and enqueue. Because I use global variables to reduce character count, only one list can be created.