Data Structure By Romeo Mesina The basic principle of data structures is the computer’s ability to organize, retrieve and store data in its specific memory address. Some common types of data structures that are used in the real world include array, queue, stack, and linked list. Data structures are designed to manage information to suit particular programming so that it can work appropriately according to its designed purpose. Many algorithms have been developed for the purpose of working with data structure to sort data more efficiently.
As a relevant topic for this report, I will discuss three common types of data structure to illustrate its use in a real world application. The first type of data structure I would like to discuss which is very common in most high level programming languages is the use of stack. A stack is called a last-in first-out (LIFO) data structure which takes a form of a container that is particularly designed to operate in that circumstance . The elements of the stacks are inserted and remove only from the end of the container.
This means that the last thing we added on the top is also the first thing that will get pulled off from the pile. As an example of how stacks works in real life, think of a deck of playing cards that is faced down on a table. Only the card that is on top of the deck is easily access. If we want to look at the top card, there are a couple of things that we can do, we could peek at it, but leave it on the top of the stack, or we can “pop” it off. When we pop it off the top of the deck, we are taking it off the stack, and if we want to add another card on the top of the stack, we “push” it to the stack.
Therefore, if the last card we put on our stack of cards is a diamond, then the first card that we pulled from the top is that same diamond. There are two main operations for the stack data structure, push() and pop(). The push operation puts an item is on top of the stack, increasing the stack size by one. Because there is a maximum size on a stack, exceeding its limit could cause a stack overflow. The pop operation takes the item on top from the stack, decreasing stack size by one. If there was no top item, or the stack was empty, this will cause a stack underflow.
The figure on the bottom illustrates a graphical description of a stack. The next item I will discuss is another data structure that is similar to the stack as I previously discussed on this paper. This data structure is called a Queue; a queue is another basic data structure that is used throughout programming. Queue data structure follows the First in First out strategy or FIFO. Like the stack, Queues have restrictions on where you can add and remove any elements. Nodes are used and kept in an order in the structure which is inserted from the rear of the queue and is deleted from the front.
The first element inserted in the first element first to delete. The addition of an element to a queue is known as an enqueue, and removing an element from the queue is known as a dequeue. There are a couple of basic ways to implement a queue. The first is to just make an array and shift all the elements to accommodate enqueues and dequeues. Another method is, instead of shifting the elements, shifts the enqueue and dequeue points. The basic operations of the Queue Data Structure are push, pop, size, front, and empty.
The push operation inserts the element in the queue at the end. The pop operation removes the element out of the queue from the front. The size operation returns the size of the queue. The front operation returns the first element of the queue, and the empty operation is used to find if the queue is empty. Queue Operations: Push – Inserts the element in the queue at the end. Pop – removes the element out of the queue from the front Size – Returns the size of the queue Front – Returns the first element of the queue. Empty – to find if the queue is empty.
As an example of this data type to illustrate its use in a real world application, think of a book store in a registry line: the person at the front is served first, and people are added to the line at the back. Therefore, the first person in line is served first, and the last person is served last. The picture at the bottom displays this example. The line in a book store is one type of queue. Queues are often used in programming networks, operating systems, and other situations in which many different processes must share resources such as CPU time.
In conclusion I will discuss one of the most important dynamic data structure used today in the real world. Linked list is the simplest and most common data structures used in many programs and applications. Basically, there are two types of linked list, singly-linked list and doubly-linked list. In a singly-linked list every element contains some data and a link to the next element, which allows keeping the structure. On the doubly-linked list, every node also contains a link to the previous node. Linked list’s can also be created in two ways, either forwards or backwards.
The way to build a linked list a forward requires three pointers: the head, which is stationary and always points to the first node; the last, which is the last node in the list; and the pointer to control what is being inserted. When building a linked list backwards, there are only two pointers needed. One pointer creates the new node while the other pointer to point to the actual list. The traversal through the list is by starting at the first node and stepping through node by node. Linked list is the fundamental data structure to implement stack, queue or sorted list. Tunes playlist is an example of linked list application in the real world. Suppose that we would like to open a list of songs that exist in the F drive therefore, we open My computer. The directory tree structure displays the main drive containing subdirectory in which also contains the data (or info in a node of a struc definition) and a link to its subdirectories. It will then show the drive letter and files after we select F drive and select the songs. The image on the right displays an example of how this is illustrated. Works Cited Dale, N. (2007). C++ Data Structure. Jones ; Barlett Publisher Inc.
Department of Computer Science, U. o. (2007, March 26). Queues. Retrieved July 4, 2010, from http://www. cs. uregina. ca/Links/class-info/210/Queue/ Lecky-Thompson, G. (2006, May 19). Data Structures and Algorithms. Retrieved June 30, 2010, from suite101. com: http://computerprogramming. suite101. com/article. cfm/data_structures_and_algorithms Stacks Data Structure. (2010). Retrieved 02 July, 2010, from WordIQ. com: http://www. wordiq. com/definition/Stack_data_structure Uma. (2002, Feb 27). What is Data Structure. Retrieved June 30, 2010, from SearchSQLServer. com: http://searchsqlserver. techtarget. com/definition/data-structure