Temporal modules
Queues are part of the “temporal modules” family, with stacks and general double ended queues. They are containers that follow the FIFO (first in, first out) principle for storing and retrieving elements. While stacks follow the LIFO (last in, first out) principle, and general double ended queues can store and retrieve elements in both ways.
These temporal modules can be implemented in many ways, using for instance fixed or dynamic memory arrays, or linked linked lists.
This is a sample implementation of a queue in a fixed size memory “circular” memory array, in a VBA class module.
“Circular” meaning that we use a fixed size array to store queue elements (in this case strings), and as we push (QPush) an pop (QPop) elements in the queue, we use “pointers” (“qfront”, “qback”) to keep track of where the queue head and tail elements are in the array. “Pointers” being in this case array element indices of the (fixed size) memory array.
Download this Excel workbook here. (MD5 checksum: 46de8d5d18a25c02dbcff7dac9dc88ee)
Please note that this is a workbook containing macros (.xlsm), you’ll have to allow them to execute when opening the document.
About this implementation
The queue itself is implemented in the “CQueue” class module.
We create a queue with the (spoiler) “CreateQueue” method, which takes the maximum number of elements we can store in the queue, as a parameter. Here’s the function signature:
|
1 2 3 |
Public Function CreateQueue(ByVal piMaxCapacity As Integer) As Boolean End Function |
To be able to show the inner workings of the module in the Excel worksheet, I had to expose (as Friend) some methods that should remain private in a final implementation; they are wrapped in a conditional compilation directive, testing on the “USE_FOR_EXCEL_DEMO” project conditional compilation argument that you’ll find defined in the project properties (from the VBA editor, menu tools, entry project properties):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
'QBack, QFront and GetInternalArray() are exposed as friend members 'As we need to know them in order to display the queue as it is handled 'in the class instance memory. #If USE_FOR_EXCEL_DEMO Then Friend Property Get QFront() As Integer QFront = mTHeader.iQFront End Property Friend Property Get QBack() As Integer QBack = mTHeader.iQBack End Property 'Internal array is zero based; returns upper bound. Friend Function GetInternalArray(ByRef pasRetItems() As String) As Integer Dim iLB As Integer Dim iUB As Integer Dim i As Integer GetInternalArray = UBound(masItem()) iLB = LBound(masItem()) iUB = UBound(masItem()) ReDim pasRetItems(iLB To iUB) As String For i = iLB To iUB pasRetItems(i) = masItem(i) Next i End Function #End If |
From here
- We can change the type of the array to store something else than strings (variants, object references, integers, etc…). We could for instance use integers that would be array indices of another array where the data elements are stored.
- We can persist the queue on disk quite easily, by writing the header information in a file, and then the queue elements. We a bit of more work, the queue can then be shared and accessed by different applications using simple file/region locking mechanisms of the operating system.
- We could implement stacks and general double ended queues in the same way. We would have something like “Push” and “Pop” methods for a stack, and “RQPush”, “RQPop”, “LQPush”, “LQPop” for a general double ended queue.
The code presented here follows these coding guidelines. Enjoy 🙂
Copyright © 2019, Francesco Foti, devinfo.net.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. The Software is provided “as is”, without warranty of any kind, express or implied, including but not limited to the warranties of merchantability, fitness for a particular purpose and noninfringement. In no event shall the authors or copyright holders X be liable for any claim, damages or other liability, whether in an action of contract, tort or otherwise, arising from, out of or in connection with the software or the use or other dealings in the Software. Except as contained in this notice, the name of Francesco Foti or devinfo.net shall not be used in advertising or otherwise to promote the sale, use or other dealings in this Software without prior written authorization from Francesco Foti.
Recent Comments