25-07-2014, 10:26 AM
STACK IMPEMENTATION ON DATA STRUCTURE
“STACK IMPEMENTATION.docx (Size: 151.6 KB / Downloads: 13)
Introduction
An array is a random access data structure, where each element can be accessed directly and in constant time. A typical illustration of random access is a book - each page of the book can be open independently of others. Random access is critical to many algorithms, for example binary search.
A linked list is a sequential access data structure, where each element can be accessed only in particular order. A typical illustration of sequential access is a roll of paper or tape - all prior material must be unrolled in order to get to data you want.
In this note we consider a sub case of sequential data structures, so-called limited access data structures.
In this Tutorial I assume that all of you have a working knowledge on how to use
Classes in C++ because all of my data structures are going to be based on them.
I realised that there are a lot of Data Structures Tutorials available but it's
rare to find one that uses OOP. So this one will mainly focus on having a data
structure in corporate as a class. CODE IS COMPILED IN BORLAND C++ UNLESS OTHERWISE MENTIONED
Stack
A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure - elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the top. A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book on the top.
The stack is a very common data structure used in programs. By data structure, we mean something that is meant to hold data and provides certain operations on that data.
Related Work
A stack is a list with the restriction that inserts and deletes can be performed in only one position, namely the end of the list called the top. The fundamental operations on a stack are push, which is equivalent to an insert, and pop, which deletes the most recently inserted element. The most recently inserted element can be examined prior to performing a pop by use of the top routine. A pop or top on an empty stack is generally considered an error in the stack ADT.On the other hand, running out of space when performing a push is an implementation error but not an ADT error.
Objectives
Stacks are commonly used Data Structures while writing code. It's concept is really simple which makes it even simpler to write it in code. Consider this situation. There are a pile of 5 Books on a Table. You want to add one book to the pile. What do you do? You simply add the book on the TOP of the pile. What if you want the third book from the new 6 book pile? You then lift each book one by one from the TOP until the third book reaches the top. Then you take the third book and replace all the others back into the pile by adding them from the TOP. If you've noticed I've mentioned the word TOP in Caps. Yes, TOP is the most important word as far as stacks are concerned. Data is stored in a Stack where adding of data is permitted only from the top. Removing/Deleting Data is also done from the top. As Simple as That. Now you may ask where Stacks are used? Stacks are infact used on every Processor. Each processor has a stack where data and addresses are pushed or added to the stack. Again the TOP rule is followed here. The ESP Register adds as a Stack Pointer that refers to the top of the stack in the Processor. Anyway, since the explaination of how the Processor Stack works is beyond the subject of this Tutorial, let's write our Stack Data Structure. Remember some Stack Terminology before continuing. Adding Data to the Stack is known as Pushing and deleting data from the stack is known as Popping. Clearly we can see that the last data pushed is the first one to be popped out. That's why a Stack is also known as a LIFO Data Structure which stands for "Last In,First Out" and I guess you know why.
Proposed Work
One of the basic rules concerning programming is that no routine should ever exceed a page. This is accomplished by breaking the program down into modules. Each module is a logical unit and does a specific job. Its size is kept small by calling other modules. Modularity has several advantages. First, it is much easier to debug small routines than large routines. Second, it is easier for several people to work on a modular program simultaneously. Third, a well-written modular program places certain dependencies in only one routine, making changes easier. For instance, if output needs to be written in a certain format, it is certainly important to have one routine to do this. If printing statements are scattered throughout the program, it will take considerably longer to make modifications. The idea that global variables and side effects are bad is directly attributable to the idea that modularity is good.
An abstract data type (ADT) is a set of operations. Abstract data types are mathematical abstractions; nowhere in an ADT's definition is there any mention of how the set of operations is implemented. This can be viewed as an extension of modular design.
Objects such as lists, sets, and graphs, along with their operations, can be viewed as abstract data types, just as integers, reals, and booleans are data types. Integers, reals, and booleans have operations associated with them, and so do abstract data types. For the set ADT, we might have such operations as union, intersection, size, and complement. Alternately, we might only want the two operations union and find, which would define a different ADT on the set.