Documention for: sqd.r Created by: sunanda on: 5-Oct-2005 Format: text/editable Downloaded on: 16-Apr-2024 [numbering-on [contents [h2 introduction [p **Stacks**, **Queues** and **Deques** are common data structures, used in many applications and algorithms. [p A stack is most commonly used. A queue is a more general stack, and a deque is more general still. [p 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). [h2 stack, queue, and deque [h3 stack [p A stack you can only insert and extract from the top end. it's **LIFO**: last in, first out: [asis 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 asis] [h3 queue [p 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: [asis 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 asis] [h3 deque [p 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. [asis 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 asis] [h2 sqd.r [p Offers a series of functions for handling stacks, queues, and deques. [p to invoke: [asis do %sqd.r asis] [p A stack can be converted to a queue or a deque at any time. [h2 sqd.r functions [h3 make [p Creates a new stack. To create a queue or deque, create a stack and then convert it, as shown below. [asis ms: sqd/make ;; creates a new stack ms: sqd/make/items 1000 ;; creates a new stack with pre-allocated space for 1000 entries asis] [h3 to-stack [h3 to-queue [h3 to-deque [p 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. [asis 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 asis] [h3 push [p 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: [asis 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 asis] [p Note there is no **/top** refinement: that's the default [h3 pop [p Removes and returns the appropriate item: [li For a stack, it's the top item [li For a queue, it's the bottom item [li For a deque, it's the top by default, or the bottom if you use the **/bottom** refinement list] In all cases: [li the item is removed from the structure (unless it was already empty) [li 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 list] [asis 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 asis] [p Note there is no **/top** refinement: that's the default [h3 peek [p 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 [h3 length? [p Tells you how many entries there are. 0 means empty: [asis while [0 <> sqd/length mq] ;; print all entries and empty the queue [print sqd/pop mq] asis] [h3 type? [p Tells you if it is a stack, queue, or deque -- just in case you've forgotten: [asis 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 asis] [h3 probe [p Returns you all entries. Does not remove any from the structure. Useful for debugging: [asis 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 asis] [h3 rotate [p For a stack or a deque, swaps the top two entries (bottom two on a deque if you have the **/bottom** refinement). [p For a queue, swaps the top entry with the bottom entry [asis 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"**] asis] [h2 notes [h3 how do you pronounce deque? [p 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.