Collections and dictionaries are best suited for storing and organizing data, but they aren't as useful for retrieving data in an orderly fashion. Trying to keep track of data stored by index numbers or by keys can get cumbersome. As a simpler alternative, computer scientists have created three other data structures:
Stacks
Queues
Deques
Unlike collections or dictionaries, these three data structures are designed for storing and removing data in a predictable order.
The stack data structure gets its name because it resembles a stack of clean dishes, typically found in a cafeteria. When you put the first plate on the counter, that plate appears at the bottom of the stack. Each time you add a new plate to the stack, the first plate gets buried farther underneath. Add another plate to the stack, and the newest plate appears on top. To remove a plate, you have to take the top plate off.
That's the same way the stack data structure works, as shown in Figure 4-1. With a stack, you don't keep track of the data's location. Instead, you can keep adding new data to store, and the stack expands automatically.
The only way to remove data from a stack is from its top. Each time you remove data, the stack shrinks automatically. Because a stack only lets you remove the last item stored on the stack, it's often called a Last In, First Out (LIFO) data structure because the last item stored is always the first item you can remove from the stack.
Note
Few programming languages offer the stack data structure as a built-in feature. Instead, you have to create a stack using other data structures, such as an array or a linked list. When you create another data structure out of a built-in data structure, the new data structure created is an abstract data structure. To save you the time and trouble of creating a stack data structure, many programming language compilers come with libraries (or classes in object-oriented languages) of subprograms that have created the stack data structure for you.
Because a stack is just a data structure, you can declare a variable to represent a stack in Visual Basic.NET by doing the following:
Dim BlowMyStack as New Stack
This command simply identifies a BlowMyStack variable as a stack data structure. The New command tells the computer to create a new stack.
When you first create a stack, it contains zero items. Each time you add a new chunk of data to a stack, it expands automatically. Unlike other data structures, such as collections, you can only add new data to the top of the stack; you can never add data in a specific location in a stack.
Warning
Like a collection or a dictionary, a stack can typically hold different data, such as both numbers and strings.
The only way you can store or remove data from a stack is through the top of the stack. To add data to a stack, you push that data on the stack. In Visual Basic.NET, you specify the Push command along with the stack name like this:
Dim BlowMyStack as New Stack
BlowMyStack.Push ("My cat")This command stores the string "My cat" on top of the stack. Each time you add another chunk of data to a stack, you have to put that data on the top, which pushes any existing data farther down the stack.
If you added the string "My cat," the number 108.75, and the string "Fat dog," the stack would look like Figure 4-2.
Dim BlowMyStack as New Stack
BlowMyStack.Push ("My cat")
BlowMyStack.Push (108.75)
BlowMyStack.Push ("Fat dog")
After you store data in a stack, the only way you can remove data from that stack is by removing the top item. Removing data from a stack is known as popping the data off the stack. If you just want to retrieve the data from a stack without removing it, you can use a Peek command, which lets you retrieve the top item from a stack.
To use the Peek command, you have to assign the value of the Peek command to a variable like this:
Dim BlowMyStack as New Stack
Dim X as Object
BlowMyStack.Push ("My cat")
BlowMyStack.Push (108.75)
BlowMyStack.Push ("Fat dog")
X = BlowMyStack.PeekThe preceding code assigns the value "Fat dog" to the X variable, which is declared as an Object data type. (In Visual Basic.NET, an Object data type can hold any type of data including integers, strings, and decimal numbers, such as (47.748).
Warning
The Peek command retrieves the data but leaves it on top of the stack.
If you want to remove data, you use the Pop command, which retrieves and removes data, as shown in the following Visual Basic.NET example:
Dim BlowMyStack as New Stack
Dim X as Object
BlowMyStack.Push ("My cat")
BlowMyStack.Push (108.75)
BlowMyStack.Push ("Fat dog")
X = BlowMyStack.PopFigure 4-3 shows the difference between the Peek and the Pop commands.
Because stacks can expand and shrink depending on the amount of data you push on them, many programming languages give you commands to count the total number of items currently stored in a stack.
In Visual Basic.NET, the command to count the number of items currently stored in a stack is Count. Here's an example:
Dim BlowMyStack as New Stack
Dim X as Object
BlowMyStack.Push ("My cat")
BlowMyStack.Push (108.75)
BlowMyStack.Push ("Fat dog")
X = BlowMyStack.CountIn this example, the Count command stores the number 3 in the X variable.
Visual Basic.NET also provides a Contains command, which tells you whether a chunk of data is stored in a stack (but doesn't tell you the location of that data in the stack). To use the Contains command, you have to specify the data you want to find like this:
Dim BlowMyStack as New Stack
Dim X, Y as Object
BlowMyStack.Push ("My cat")
BlowMyStack.Push (108.75)
BlowMyStack.Push ("Fat dog")
X = BlowMyStack.Contains("Good dog")
Y = BlowMyStack.Contains("Fat dog")In this example, the first Contains command looks for the "Good dog" string. Because this string isn't stored in the stack, the Contains command returns a False value, which it stored in the X variable.
The second Contains command looks for the "Fat dog" string. Because this string is stored in the stack, this Contains command returns a True value, which is stored in the Y variable.
Warning
The Contains command tells you whether a chunk of data is in a stack, but it doesn't tell you where in the stack that data might be.
Similar to a stack is another data structure — a queue.
Tip
A queue gets its name because the data structure resembles a line of waiting people, such as a line at a bank teller. The first person in the line (queue) is also the first person who gets to leave the line. As a result, a queue is often a First In, First Out (FIFO) data structure, as shown in Figure 4-4.
Like a stack, a queue can expand and shrink automatically, depending on the amount of data you store in it. Unlike a stack that only lets you store and retrieve data from the top, a queue lets you store data on one end but remove that data from the opposite end.
Note
Most programming languages don't offer the queue data structure as a built-in feature. Instead, you have to create a queue with other data structures, such as an array or a linked list, to create an abstract data structure. Fortunately, many programming language compilers come with libraries (or classes in object-oriented languages) of subprograms that have created the queue data structure for you.
Because a queue is just a data structure, you can declare a variable to represent a queue in Visual Basic.NET by doing the following:
Dim LongLine as New Queue
This command simply identifies a LongLine variable as a queue data structure. The New command tells the computer to create a new stack.
New data always gets stored at the end of the queue:
When you first create a queue, it contains zero items.
Each time you add a new chunk of data to a queue, the queue expands automatically.
The front of the queue always contains the first or oldest data.
Warning
Like a collection or a dictionary, a queue can hold different data, such as both numbers and strings.
To add data to a queue, Visual Basic.NET uses the Enqueue command along with the queue name like this:
Dim LongLine as New Queue
LongLine.Enqueue ("Tasha Korat")This command stores the string "Tasha Korat" as the first item in the queue. Each time you add another chunk of data to this queue, the new data gets tacked on to the end, which pushes the oldest data to the front of the queue.
If you added the string "Tasha Korat," the number 7.25, and the string "Gray," the stack would look like Figure 4-5.
Dim LongLine as New Queue
LongLine.Enqueue ("Tasha Korat")
LongLine.Enqueue (7.25)
LongLine.Enqueue ("Gray")
You always remove data from a queue by taking that data off the front of the queue. The front of the queue always contains the data that's been stored in the queue the longest.
In Visual Basic.NET, you can remove and retrieve data off a queue by using the Dequeue command, as shown in the following Visual Basic.NET example:
Dim LongLine as New Queue
Dim X as Object
LongLine.Enqueue ("My cat")
LongLine.Enqueue (108.75)
LongLine.Enqueue ("Fat dog")
X = LongLine.DequeueAs an alternative to removing data from a queue, you can retrieve data by using the Peek command. To use the Peek command, you have to assign the value of the Peek command to a variable like this:
Dim LongLine as New Queue
Dim X as Object
LongLine.Enqueue ("Tasha Korat")
LongLine.Enqueue (7.25)
LongLine.Enqueue ("Gray")
X = LongLine.PeekThe preceding code assigns the value "Tasha Korat" to the X variable, which is declared as an Object data type. (In Visual Basic.NET, an Object data type can hold any type of data including integers, strings, and decimal numbers, such as 57.98).
Warning
The Peek command only retrieves the data but leaves it at the front of the queue. Figure 4-6 shows the difference between the Peek and the Dequeue commands.
Because a queue can keep growing each time you add more data to it, most programming languages provide a way to count the total number of items currently stored in the queue.
Figure III.4-6. The Peek command retrieves data, but the Dequeue command retrieves and removes data.
In Visual Basic.NET, the command to count the number of items currently stored in a stack is Count. Here's an example:
Dim LongLine as New Queue
Dim X as Object
LongLine.Enqueue ("Tasha Korat")
LongLine.Enqueue (7.25)
LongLine.Enqueue ("Gray")
X = LongLine.CountIn this example, the Count command stores the number 3 in the X variable.
Visual Basic.NET also provides a Contains command, which tells you whether a chunk of data is stored in a queue (but doesn't tell you the location of that data in the queue). To use the Contains command, you have to specify the data you want to find like this:
Dim LongLine as New Queue
Dim X, Y as Object
LongLine.Enqueue ("Tasha Korat")
LongLine.Enqueue (7.25)
LongLine.Enqueue ("Gray")
X = LongLine.Contains("Gray")
Y = LongLine.Contains("Orange juice")In this example, the first Contains command looks for the "Gray" string. Because this string is stored in the queue, the Contains command returns a True value, which it stored in the X variable.
The second Contains command looks for the "Orange juice" string. Because this string isn't stored in the stack, this Contains command returns a False value, which is stored in the Y variable.
Warning
The Contains command just tells you whether a chunk of data is in a queue, but it doesn't tell you where in the queue that data might be.
A queue only lets you add data on one end of the data structure and remove data from the opposite end. A deque (pronounced deck) acts like a queue that lets you add or remove data from either end, as shown in Figure 4-7.
Note
Most programming languages don't offer the deque data structure as a builtin feature. Instead, you have to create a queue with other data structures, such as a linked list, and then write code to manage the storage and removal of data from both ends of the deque.
A deque is basically a linked list of nodes that contain data and two pointers:
One pointer points to the previous node.
The second pointer points to the next node, as shown in Figure 4-8.
Figure III.4-8. Each node in a deque contains two pointers that point to the next and previous node.
Initially, a deque consists of a single node with both pointers pointing to nothing, which is often defined in most programming languages as a NIL value. When you add (or remove) data, you must specify which end of the deque to put that data, either the front or the back.
Deques can either be implemented as a double-linked list or a circular double-linked list, as shown in Figure 4-9. In both implementations, you need to keep track of which node represents the front and which represents the end.
The common command names used for adding or removing data from a deque include
Push_front: Adds data to the front of the deque
Push_back: Adds data to the end of the deque
Pop_front: Removes data from the front of the deque
Pop_back: Removes data from the end of the deque
Because you can add data to both ends of a deque, a deque can grow in both directions, as shown in Figure 4-10.
Unlike a stack that always removes the newest data or a queue that always removes the oldest data, a deque can never predictably remove either the oldest or newest data. When you add data to both ends of the deque, the oldest data tends to get sandwiched and buried in between the newest data on both ends.
Like stacks and queues, deques only allow you to remove data from a specific part of the data structure. In general, the more complicated the data structures, the more code you have to write to manage that data structure.
A list or an array is much simpler to use, but much less flexible than a queue or a stack. Unfortunately, stacks, queues, and deques add greater complexity to your program in exchange for their added flexibility.
Tip
If you need to store and remove data in an orderly fashion, stacks, queues, and deques are better suited than arrays, collections, or dictionaries, which are better suited for long-term storage of data. A queue might be useful for an online reservation system that handles the oldest request first.
Although the idea of removing the last item first might seem counterintuitive, stacks are a commonly used data structure. Most programs offer an Undo command, which lets you undo the last command you gave the computer. If you give five different commands, the program may store each command in a stack.
When you want to undo a command, you want to start with the last command you gave it, which appears on the top of the stack, as shown in Figure 4-11. Each succeeding Undo command removes an additional command until you get to the last command, which is the oldest one that was buried at the bottom of the stack.
Tip
A deque might be useful for an antivirus program that needs to examine messages being sent out and coming in to a particular computer. When messages come in, the antivirus program stores each message in the deque. Messages scanned as virus-free are sent through the other end of the deque, whereas messages caught carrying a virus are rejected from the same end of the dequeue, as shown in Figure 4-12.
Different data structures can be useful for different purposes. Choose the right data structure, and a program can suddenly be easier to write. Choose the wrong data structure, and your program can suddenly become much tougher to write.