5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Mhh, not really clear. What prevents me from doing class A extends java.util.Stack {}? \$\endgroup\$ – Johannes Kuhn Nov 8 '13 at 22:13
  • \$\begingroup\$ @JohannesKuhn Good point, updated. \$\endgroup\$ – Rob Nov 8 '13 at 22:24
  • 2
    \$\begingroup\$ what if, for example, in Ruby arrays have push, pop, and shift, so technically arrays are stacks and queues. They behave like linked lists, because linked lists are basically just arrays, so the default array already pretty much meets these requirements... \$\endgroup\$ – Doorknob Nov 8 '13 at 22:34
  • \$\begingroup\$ @Doorknob So "hard-coded functionality" would be better wording for this question? I guess restricting trivial answers is too generic... I'll think of a better way to word "trivial". \$\endgroup\$ – Rob Nov 8 '13 at 23:43
  • \$\begingroup\$ I don't know how I could do this without using arrays... \$\endgroup\$ – Doorknob Nov 8 '13 at 23:49
3
\$\begingroup\$

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"]
\$\endgroup\$
1
\$\begingroup\$

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")
\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ I think you can ditch the casts before malloc(). Also, you can replace sizeof(Q) with sizeof*t \$\endgroup\$ – ceilingcat Jul 1 '17 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.