Maintenance script: Initial automated import

2016-02-24T18:41:15Z

Initial automated import

New page

A queue is an abstract data structure that stores objects in a First In First Out basis. The two main operations that can be performed on a queue are ''enqueue'' and ''dequeue''. ''Enqueue'' adds an element to the bottom of a queue. ''Dequeue'' removes the top element from the queue, and returns it. A queue can be visualized as a line of people waiting to get on a bus. The first person there gets on first, and the last person there gets on last.

Queues are widely used in the TI-83+ operating system, and are found in most computer systems.

= Implementation in TI-Basic =

TI-Basic does not have a queue data structure by default, but depending on what needs to be stored, a stack can be implemented as either a list or a string.

== Lists ==

In a list, the top can be considered the first element of the list or the last element of the list. Both approaches are valid, and either may be more appropriate depending on the situation.

=== First element as top ===

To make a queue using a list, one can create a list for which one assumes that the first element is the top of the queue. In order to enqueue one would do:

:N→L₁(dim(L₁))

This adds N to the end of the list. Dequeue is done by getting the value of the first element and then using [[TI-BASIC:Deltalist|ΔList(]] in conjuntion with [[TI-BASIC:Cumsum|cumSum(]] to remove the first element of the list. This can be done with the following code:

:L₁(1)→N
:ΔList(cumSum(L₁))→L₁

If the queue is empty, then the list will be empty and dim(L₁) will return 0.

=== Last element as top ===

To make a queue using a list, one can create a list for which one assumes that the last element is the top of the stack In order to enqueue onto the stack one would do:

:augment({N},L₁)→L₁

This stores N into the first element of the list. Dequeue is done by getting the value of the last element and then decreasing the list size by one. This can be done with the following code:

:L₁(dim(L₁))→N
:dim(L₁)-1→dim(L₁

If the queue is empty, then the list will be empty and dim(L₁) will return 0.

== Strings ==

To make a queue using a string one has to store values into a string with a specified delimiter. The delimiter is a one or two token string that will ''not'' appear in any of the data items being put into the queue. This delimiter will change depending on what you are storing in the queue. To begin, store one instance of the delimiter (for this example, "::") into a string which will be the stack. To push on to the string, simply add the new data and a delimiter to the end of the string (for this example Str0).

:Str0+Str1+"::"→Str0

To dequeue from the string, use the inString( function for find the first instance of the delimiter and remove it from the queue.

:inString(Str0,"::")→N
:sub(Str0,1,N-1)→Str1
:sub(Str0,N+2,length(Str0)-N-1)→Str0

If the queue is empty, the string will contain one delimiter and length(Str0) will return the length of the delimiter (in this case 2).[[Category:TI-BASIC]]
[[Category:TIBD]]

TI-BASIC:Queue - Revision history

Maintenance script: Initial automated import