Wednesday, 14 June 2017

Stacks

Introduction to Stacks
Stacks are very important in the study of Data Structures. But in this article we would examine the basics of Stack Data Structure and how stack is represented.


Below is what is to be presented in this article.

Definition of Stack
Stack Representation
Application of Stacks
Conversion of Decimal to Binary
Expression Syntax Parsing

Definition of Stack
A stack is a linear data structure that allows for insertion and deletion of items from one end of the stack called the top of the stack. This means that the last item to be inserted into to stack is always the first item to be retrieved from the stack and vice versa. So we can can say that stack supports Last In First Out(LIFO), data storage and retrieval. Stacks are normally used in the computer system for temporary data storage.




Take note of the following terms:
Push: The action of inserting an item on top of the stack
Pop: The action of retrieving an item from the top of the stack
Initialize: Start a new stack

Linked-List Stack Representation
The most common representation of stack is by the use of linked list. Before we examine the Linked-List representation, below are operations that can be performed on a stack. These operation are actually methods that can generally be performed on an object of type Stack.

push(new_item:item_type)
Adds a new item on top of the stack.

top() : item_type
Returns that last item inserted into the stack

pop()
Retrieves that last item from top of the stack

is-empty() : Boolean
Returns true if the Stack is empty else returns false

is-full(): Boolean
Returns True if the stack is full else returns false

get-size() : Integer
Returns an integer representing the size of the stack.


Application of Stacks
Stacks can be applied in many areas of life including: Stack of trays in a restaurant, stack of books, stack of plates etc. But we are going to closely examine the following:

1. Converting Decimal to Binary
Consider the conversion of a decimal number into its binary equivalent. The algorithm goes as follows:

Read a decimal number
While the number is greater than zero, continue
    Divide the number by two
    Find the remainder   
    Write the remainder
End

Example
Implement the algorithm, to covert the decimal number 25 to binary

If the algorithm above it applied, the program would print out the binary number 10011 and this would be the wrong answer.

To get the right answer, we need to implement this algorithm using a stack data structure. Each of the binary digits is pushed on to a attack as they are generated. At the end of the whole conversion, each digit is retrieved from the stack and printed.
The correct result would be as shown in the figure below.

Other applications of stack include, Expression syntax evaluation, Rearranging Railroad cars and the Quicksort Algorithm.