Documentation for: sqd.r

1. introduction

Stacks, Queues and Deques are common data structures, used in many applications and algorithms.

A stack is most commonly used. A queue is a more general stack, and a deque is more general still.

In all three cases, you have a data structure into which you can insert items at one end or the other (or both). Similarly you can extract items from one end or the other (or both).

2. stack, queue, and deque

2.1. stack

A stack you can only insert and extract from the top end. it's LIFO: last in, first out:

 my-stack: sqd/make             ;; create a stack
 sqd/push my-stack "rebol"      ;; add an item
 sqd/push my-stack "is"         ;; add another item
 sqd/push my-stack "flexible"   ;; add a third item

 loop 3 [print sqd/pop my-stack]
   flexible
   is
   rebol

 

2.2. queue

A queue you can only insert in the top, and only extract from the bottom: it's FIFO: first in, first out, a bit like a pipe:

 my-queue: sqd/make             ;; create a stack....
 sqd/to-queue my-queue          ;; .....and convert it to a queue
 sqd/push my-queue "rebol"      ;; add an item
 sqd/push my-queue "is"         ;; add another item
 sqd/push my-queue "flexible"   ;; add a third item

 loop 3 [print sqd/pop my-queue]
   rebol
   is
   flexible
 

2.3. deque

A deque is a double-ended queue. You can insert at the top or the bottom; and similarly, retrieve the item at either the top or the item at the bottom.

 my-deque: sqd/make                 ;; create a stack....
 sqd/to-deque my-deque              ;; .....and convert it to a deque
 sqd/push my-deque "rebol"          ;; add an item to the top
 sqd/push my-deque "is"             ;; add another item to the top
 sqd/push my-deque "flexible"       ;; add a third item to the top

 sqd/push/bottom my-deque "so"      ;; add an item to the bottom
 sqd/push/bottom my-deque "are"     ;; add another item to the bottom
 sqd/push/bottom my-deque "deques"  ;; add a third item to the bottom

 loop 3 [
  print sqd/pop my-deque
  print sqd/pop/bottom my-deque
 ]
   flexible
   deques
   is
   are
   rebol
   so

 

3. sqd.r

Offers a series of functions for handling stacks, queues, and deques.

to invoke:

 do %sqd.r
 

A stack can be converted to a queue or a deque at any time.

4. sqd.r functions

4.1. make

Creates a new stack. To create a queue or deque, create a stack and then convert it, as shown below.

   ms: sqd/make             ;; creates a new stack
   ms: sqd/make/items 1000  ;; creates a new stack with pre-allocated space for 1000 entries
 

4.2. to-stack

4.3. to-queue

4.4. to-deque

Converts your stack/queue/deque to another type. This doesn't fundamentally change the data structure, but it does alter the way other functions such as push and pop work.

   md: sqd/make    ;; make a stack
   sqd/to-deque md ;; and convert it to a deque
   ...
   sqd/to-queue md ;; now make it a queue
   ...
   sqd/to-stack md ;; and finally convert it to a stack
 

4.5. push

Adds an item to the top of your stack, queue, or deque. With the /bottom refinement, adds the item to the bottom of the deque:

  ms: sqd/make                   ;; new stack
  sqd/to-queue mq: sqd/make      ;; new queue
  sqd/to-deque md: sqd/make      ;; new deque

  sqd/push ms "a"                ;; add to top of stack
  sqd/push mq "b"                ;; add to top of queue
  sqd/push md "c"                ;; add to top of deque
  sqd/push/bottom md "d"         ;; add to bottom of deque
 

Note there is no /top refinement: that's the default

4.6. pop

Removes and returns the appropriate item:

• For a stack, it's the top item
• For a queue, it's the bottom item
• For a deque, it's the top by default, or the bottom if you use the /bottom refinement

• the item is removed from the structure (unless it was already empty)
• if the structure was empty, we return none. But note: it is not safe to check for none to see if the structure is empty: you may have pushed a none. Use length? instead

  sqd/pop ms                 ;; remove from top of stack
  sqd/pop mq                 ;; remove from bottom of queue
  sqd/pop md                 ;; remove from top of deque
  sqd/pop/bottom md          ;; remove from bottom of deque
 

Note there is no /top refinement: that's the default

4.7. peek

The same as pop except the item is also retained in the structure -- allows you to see the top (or bottom) item without removing it

4.8. length?

Tells you how many entries there are. 0 means empty:

  while [0 <> sqd/length mq]    ;; print all entries and empty the queue
      [print sqd/pop mq]
 

4.9. type?

Tells you if it is a stack, queue, or deque -- just in case you've forgotten:

   my-thing: sqd/make
   loop random/secure 10 [
       do random/only [
           "sqd/to-stack my-thing"
           "sqd/to-queue my-thing"
           "sqd/to-deque my-thing"
          ]
      ]
 print sqd/type? my-thing
    "deque"     ;; or whatever it is now
 

4.10. probe

Returns you all entries. Does not remove any from the structure. Useful for debugging:

  my-stack: sqd/make
  for n 5 30 7 [sqd/push my-stack n]

  foreach item sqd/probe my-stack [print item]
   26
   19
   12
    5
 

4.11. rotate

For a stack or a deque, swaps the top two entries (bottom two on a deque if you have the /bottom refinement).

For a queue, swaps the top entry with the bottom entry

  ms: sqd/make                   ;; new stack
  sqd/to-queue mq: sqd/make      ;; new queue
  sqd/to-deque md: sqd/make      ;; new deque

  foreach item ["a" "b" "c" "d" "e"][
      sqd/push ms item
      sqd/push mq item
      sqd/push md item
     ]

  probe sqd/probe ms             ;; rotate top of a stack
    ["e" "d" "c" "b" "a"]
  sqd/rotate ms
  probe sqd/probe ms
    ["d" "e" "c" "b" "a"]

  probe sqd/probe mq            ;; rotate ends of a queue
    ["e" "d" "c" "b" "a"]
  sqd/rotate mq
  probe sqd/probe mq
    ["a" "d" "c" "b" "e"]

  probe sqd/probe md            ;; rotate bottom of a deque
    ["e" "d" "c" "b" "a"]
  sqd/rotate/bottom md
  probe sqd/probe md
    ["e" "d" "c" "a" "b"]
  

5. notes

5.1. how do you pronounce deque?

No idea. I'd say deek, same pronunciation as in Deke Slayton who was one of the first Mercury program astronauts, yet just about the last Apollo program astronaut to fly. For that reason, it seems appropriate to name the structure after him.