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.