Transcript Data Structures

Data Structures
Chapter 6
Data Structure
A data structure is a representation of data
and the operations allowed on that data.
Examples:
1. Array
2. Record
3. String
Examples of data structures
1.
2.
3.
4.
5.
6.
7.
8.
Stack
Queue
Linked List
Tree
Hash Table
Priority Queue
Heap
Binary Search Tree
Stack
A stack is a data structure into which items
may be inserted and from which items
may be deleted at one end, called the
top of the stack. That is, a data structure
in which access is restricted to the most
recently inserted item.
A stack is a LIFO structure – last in first out.
Operations on Stacks
1. push – add an element to the top of the
stack
2. pop – read and remove an element from the
top of the stack
3. top – read the top element (without removing
it)
4. isEmpty – returns true if no element in the
stack
5. isFull – returns true if the stack can hold no
more elements
6. Destroy – get rid of stack
Queue
A queue is a data structure from which items
may be deleted at one end (called the
front of the queue) and into which items
may be inserted at the other end (called
the rear of the queue). That is, a data
structure which restricts access to the
least recently inserted item.
A queue is a FIFO structure – first in first out
Operations -- Queue
1. enqueue – add an element at the rear of the
queue
2. dequeue – read and remove an element from
the front of the queue.
3. getFront – read (without removing) the element
in front of the queue.
4. isEmpty – returns true if there is no element in
the queue
5. isFull – returns true if the queue can hold no
more elements
6. destroy – get rid of the queue
Linked List
A linked list is collection of items in which
items have a position. That is, a
collection of nodes that hold data and
pointers to the next node (and possibly to
the previous node) in the list.
Operations – Linked list
1.
2.
3.
4.
5.
Add an element
Remove an element
Find an element
Check for an empty list
Destroy the list
Tree
A tree consists of a set of nodes and a set of
edges that connect pairs of nodes such that
1. One node is distinguished as the root.
2. Every node c, except the root, is connected by
an edge from exactly one other node p. p is c’s
parent and c is one of p’s children.
3. A unique path traverses from the root to each
node.
Tree Operations
1.
2.
3.
4.
Insert element
Remove element
Find element (Search)
Traverse – move through the tree and
visit each node
5. Check if the tree is empty
Binary Tree
A binary tree is a tree such that each node
has at most two children.
A binary search tree is a binary tree that has
its data values arranged as follows: each
node in the tree contains a value that is
larger than each value in its left subtree
and smaller than each value in its right
subtree.
Hash Table
A data structure that allows very fast find,
add, and delete operations (most of the
time).
Hash Function - converts a data value into
an index.
Priority Queue
A priority queue is like a queue, but
elements are deleted in order of priority
Uses:
– Emergency room
– Main Frame Job Control
• payroll would be assigned a higher priority than
some other jobs
– Event-driven simulation
– Printer Queue