*Introduction to Data Structures*

*At the heart of virtually every computer program are its algorithms and its data structures. It is hard to separate these two items, for data structures are meaningless without algorithms to create and manipulate them, and algorithms are usually trivial unless there are data structures on which to operate.*

*This category concentrates on four of the most basic structures: stacks, queues, binary search trees, and priority queries. Questions will cover these data structures and implicit algorithms, not on implementation language details. A stack is usually used to save information that will need to be processed later. Items are processed in a “Last-in, first-out” (LIFO) order. A queue is usually used to process items in the order in which requests are generated; a new item is not processed until all items currently in the queue are processed. This is also known as “first-in, first-out” (FIFO) order. A binary search tree is used when one is storing a set of items and needs to be able to efficiently process the operations of insertion, deletion and query (i.e. find out if a particular item is part of the set and if not, which item in the set is close to the item in question). A priority queue is used like a binary search tree, except one cannot delete an arbitrary item, nor can one make an arbitrary query. One can only delete the smallest element of the set, and can only find out what is the smallest element of the set.*

*A stack supports two operations: PUSH and POP. A command of the form “PUSH(A)” puts the key A at the top of the stack; the command “POP (X)” removes the top item from the stack and stores its value into variable X. If the stack was empty (because nothing had ever been pushed on it, or if all elements have been popped off of it), then X is given the special value of NIL. An analogy to this is a stack of books on a desk: a new book is placed on the top of the stack (pushed) and a book is removed from the top also (popped). Some textbooks call this data structure a “push-down stack” or a “LIFO stack”.*

*Queues operate just like stacks, except items are removed from the bottom instead of the top. A good physical analogy of this is the way a train conductor or newspaper boy uses a coin machine to give change: new coins are added to the tops of the piles, and change is given from the bottom of each. Some textbooks refer to this data structure as a “FIFO stack”.*

*Consider the following sequence of 14 operations:*

*PUSH(A), PUSH(M), PUSH(E), POP(X), PUSH(R),*

*POP(X), PUSH(I), POP(X), POP(X), POP(X),*

*POP(X), PUSH(C), PUSH(A), PUSH(N)*

*If these operations are applied to a stack, then the values of the pops are E, R, I, M, A and NIL. After all of the operations, there are three items still on the stack: the N is at the top (it will be the next to be popped if nothing else is pushed before the pop command), and C is at the bottom. If instead of using a stack we used a queue, then the values popped would be A, M, E, R, I and NIL. There would be three items still in the queue: N at the top and C on the bottom. Since items are removed from the bottom of a queue, C would be the next item to be popped regardless of any additional pushes.*

## Post A Comment:

## 0 comments:

Thanks

Mukesh Rajput