In the world of Computer Science there exist many types of storing data. A popular type of storing data is in the form of an array. In programming an array is defined as a series of objects all of which are of the same size and type. Arrays can be simply described as a list of objects. Imagine a deck of cards and each card was a data object with attributes like the number or value of the card, the suit, and pictures on the face and back of the card. The complete deck can be looked at as an array of cards. In turn the whole deck of cards can be referred to as an object in itself. Arrays are one of the first data structures a programmer learns and manipulation and access of data is what programming is all about. Two specialized versions of an array which have unique abilities are the Stack and Queue.
A Stack is a group of objects formed by stacking one object on top of another and implements the last-in-first-out (LIFO) principle. The operations of a Stack are push and pop. The push operation is used to add items to the stack which puts the item on the top. The pop operation is used to remove an item which removed the item at the top. A commonly seen example of a Stack is the "undo" function in text editors. When the text has changed, the change is pushed on a stack. When the user wants to "undo" the latest change in text the change is easily accessed by popping it off the stack.
A Queue (like the Stack) is a group of objects but uses the first-in-first-out (FIFO) principle. The operations of a Queue are enqueue and decueue. The enqueue operation is used to add an object to the Queue array by placing the object in the back of any other objects already in the Queue. The dequeue operation is used to remove or retrieve an object. The first object is returned and removed with the dequeue operation. A common use of a Queue is a waiting list when registering for classes. When a class is full a waiting list is created making a list of people wanting to be in the class in case someone already registered in the class decides to remove themselves from it. This would make an available spot open for enrollment and the waiting list provides a fair opportunity for the first person to try to add the class when it became full. For more information about Stacks and Queues see David Galles "Data Structure Visualizations" at The University of San Francisco here.
Hi David, it is a good post. I especially like the way you explain each of the data structures. It is very easy to understand and memorize. Although the implementations of stack and queue are similar, pick the wrong one will definitely lower the performance of the program. For example, if we accidentally pick stack as the way we implement the waiting list, we need to walk through the entire stack in order to pop out the person from the bottom of the stack. However, for queue, the person is the first element. As a result, we should not only know how a data structure works but also when to use it.
ReplyDelete