Data Structures And Algorithms

STACK

A special type of data structure in which items are removed in the reverse order from that in which they are added, so the most recently added item is the first one to be removed. This is also called last-in, first-out (LIFO).

Adding an item to a stack is called PUSH. Removing an item from a stack is called POP. And the item at the peak of the stack is called TOP.

Image: JLVeel26

QUEUE

Is a data structure in which elements are removed in the same order they were entered. This is often referred as FIFO (first in, first out).

New additions to a line made to the rear of the queue, while removal happens in the front. In the queue only two operations are allowed enqueue and dequeue. Enqueue means to insert an item into the rear of the queue, Dequeue means removing the item in the front of the queue.

Image: JLVeel26

LINKED LIST

Each element (node) of a list is comprising of two items - the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.

A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand. Any application which has to deal with an unknown number of objects will need to use a linked list.

One disadvantage of a linked list against an array is that it does not allow direct access to the individual elements. If you want to access a particular item then you have to start at the head and follow the references until you get to that item.

Image: JLVeel26

BINARY TREE

Is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. The topmost node in the tree is called the root.

Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent. On the other hand, each node can be connected to arbitrary number of nodes, called children. Nodes with no children are called leaves, or external nodes. Nodes which are not leaves are called internal nodes. Nodes with the same parent are called siblings.

More tree terminology:

• The depth of a node is the number of edges from the root to the node.
• The height of a node is the number of edges from the node to the deepest leaf.

Image: JLVeel26

REFERENCE

CITATION

Victor S.Adamchik, CMU, 2009, Stack & Queues, Linked List, Binary Tree