lambdaway :: queue

5 | list | login |load

| |

_h1 stack & queue

_p The APIs of stacks and queues are built on lambdatalk array primitives.

{prewrap
{A.lib}
}

_p For instance:

{pre
{b operation        javascript               lambdatalk}
                                   return                     return
{A.new a b c d e f g}  arr.length        -> 7   '{A.length arr}      -> 7
first of arr:    arr[0]            -> a   '{A.first arr}       -> a
last of arr:     arr[arr.length-1] -> g   '{A.last arr}        -> g

[a,b,c,d,e,f,g]  arr.push(x)       -> 7   '{A.addlast! x arr}  -> {A.new a b c d e f g x}
[a,b,c,d,e,f,g]  arr.pop()         -> g   '{A.sublast! arr}    -> g
[a,b,c,d,e,f,g]  arr.unshift(x)    -> 7   '{A.addfirst! x arr} -> {A.new x a b c d e f g}
[a,b,c,d,e,f,g]  arr.shift()       -> a   '{A.subfirst! arr}   -> a
}

_h2 1) stack

_p Following [[https://rosettacode.org/wiki/Stack|https://rosettacode.org/wiki/Stack]] a stack is a container of elements with   last in, first out   access policy.   Sometimes it also called LIFO. The stack is accessed through its top. The basic stack operations are:
_ul  push   stores a new element onto the stack top;
_ul  pop   returns the last pushed stack element, while removing it from the stack;
_ul  empty   tests if the stack contains no elements.
_ul  top   (sometimes called peek to keep with the p theme) returns the topmost element without modifying the stack.

{pre

'{def stack.add 
 {lambda {:v :s}
  {let { {_ {A.addfirst! :v :s}}}
       } ok}}
-> {def stack.add 
 {lambda {:v :s}
  {let { {_ {A.addfirst! :v :s}}}
       } ok}}

'{def stack.get 
 {lambda {:s} 
  {let { {:v {A.first :s}} 
         {_ {A.subfirst! :s}} 
       } :v}}}
-> {def stack.get 
 {lambda {:s} 
  {let { {:v {A.first :s}} 
         {_ {A.subfirst! :s}} 
       } :v}}}

'{def stack.peek
 {lambda {:s}
  {A.first :s}}}
-> {def stack.peek
 {lambda {:s}
  {A.first :s}}}

'{def stack.empty?
 {lambda {:s}
  {A.empty? :s}}}
-> {def stack.empty?
 {lambda {:s}
  {A.empty? :s}}}
}

_p Note that the {b A.addfirst! & A.subfirst!} array primitives return the array, it's the reason why they are encapsulated in a let form.

_p Using

{pre
'{def S {A.new}}    -> {def S {A.new}}      []
'{stack.add 1 {S}}  -> {stack.add 1 {S}}    [1]
'{stack.add 2 {S}}  -> {stack.add 2 {S}}    [2,1]
'{stack.add 3 {S}}  -> {stack.add 3 {S}}    [3,2,1]
'{stack.empty? {S}} -> {stack.empty? {S}} 
'{stack.get {S}}    -> {stack.get {S}}      [2,1]
'{stack.add 4 {S}}  -> {stack.add 4 {S}}    [4,2,1]
'{stack.peek {S}}   -> {stack.peek {S}}      [4,2,1]
'{stack.get {S}}    -> {stack.get {S}}      [2,1]
'{stack.get {S}}    -> {stack.get {S}}      [1]
'{stack.get {S}}    -> {stack.get {S}}      []
'{stack.get {S}}    -> {stack.get {S}}      
'{stack.empty? {S}} -> {stack.empty? {S}}   
}

_h2 2) queue

_p Following [[https://rosettacode.org/wiki/Queue|https://rosettacode.org/wiki/Queue]], implement a FIFO queue. Elements are added at one side and popped from the other in the order of insertion. Operations:
_ul  push   (aka enqueue)    - add element
_ul  pop    (aka dequeue)    - pop first element
_ul  empty                   - return truth value when empty
_ul  handle the error of trying to pop from an empty queue

{pre

'{def queue.add 
 {lambda {:v :q}
  {let { {_ {A.addlast! :v :q}}}
       } ok}}
-> {def queue.add 
 {lambda {:v :q}
  {let { {_ {A.addlast! :v :q}}}
       } ok}}

'{def queue.get 
 {lambda {:q} 
  {let { {:v {A.first :q}} 
         {_ {A.subfirst! :q}} 
       } :v}}}
-> {def queue.get 
 {lambda {:q} 
  {let { {:v {A.first :q}} 
         {_ {A.subfirst! :q}} 
       } :v}}}

'{def queue.empty?
 {lambda {:q}
  {A.empty? :q}}}
-> {def queue.empty?
 {lambda {:q}
  {A.empty? :q}}}

'{def Q {A.new}}    -> {def Q {A.new}}      []
'{queue.add 1 {Q}}  -> {queue.add 1 {Q}}    [1]
'{queue.add 2 {Q}}  -> {queue.add 2 {Q}}    [1,2]
'{queue.add 3 {Q}}  -> {queue.add 3 {Q}}    [1,2,3]
'{queue.get {Q}}    -> {queue.get {Q}}      [2,3]
'{queue.add 4 {Q}}  -> {queue.add 4 {Q}}    [2,3,4]
'{queue.empty? {Q}} -> {queue.empty? {Q}}
'{queue.get {Q}}    -> {queue.get {Q}}      [3,4]
'{queue.get {Q}}    -> {queue.get {Q}}      [4]
'{queue.get {Q}}    -> {queue.get {Q}}      []
'{queue.get {Q}}    -> {queue.get {Q}}
'{queue.empty? {Q}} -> {queue.empty? {Q}}

}

_p {i alain marty 02/03/2023}