Stack Part 1 - Data Structure | Learn More CSE

 Stacks - 1

Introduction

• Stacks are simple data structures that allow us to store and retrieve data sequentially. 
• A stacks is a linear data structure like arrays and linked lists.
• It is an abstract data type (ADT).
• In a stack, the order in which the data arrives is essential. It follows the a LIFO order of data insertion/abstraction. LIFO stands for Last In First Out.
• Consider the example of pile of book: 

 Here ,unless the book at the topmost position is removed from the pile, we can't have acces to the second book from the top the similarly, for the books below the second one. When we apply the same technique over the data in our program then, this pile-type structure is said to be a stack.

Like deletion ,we can only insert the book at the top of the pile rather than at any other position .this means that the object/data that made its entry at the last would be one too come first, hence known as LIFO.

Operations on the Stack :

• In a stack, insertion and deletion are done at one end, called top.
• Insertion: This is known as push operation.
• Deletion : This is known as pop operation.

Main Stack operations:

• push (int data): Insert data onto the stack.
• int Pop( ): Removes and returns the last inserted element from the stack.

Auxiliary Stack operations

• int Top( ): Returns the last inserted element without removing it.
• int Size( ): Returns the number of elements stored in the stack.
• int IsEmptyStack( ): indicates whether any elments are stored in the stack or not.
• int IsFullStack( ) :indicates whether the stack is full or not.

Performance

Let n be the number of elements in the stack. The complexities of stack operations with this represention can be given as:

Space complexity (for n push operation)	O(1)
Time complexity of Push ( )	O(1)
Time complexity of Pop ( )	O(1)
Time complexity of Size( )	O(1)
Time complexity of IsEmptyStack( )	O(1)
Time complexity of IsFullStack( )	O(1)
Time complexity of DeleteStack( )	O(1)

Exceptions

• Attempting the execution of an operation may sometimes cause an error condition, called an exception.
• Exceptions are said to be “thrown” by an operation that cannot be executed. 
• Atempting the execution of pop() on an empty stack throws an exception called ​Stack Underflow​.
• Trying to push an element in a full-stack throws an exception called ​Stack Overflow.

Implementing stack - Simple Array Implementation

This implementation of stack ADT uses an array. In the array ,we add elementsfrom left to right and use a variable to keep track of the top element.

Limitation of simple array implementation

In other programming languages like C++, Java, etc, the maximum size of the an array must first be defined i.e. it is fixed and it cannot be changed. However, in Python, arrays are resizable by nature. This means that even though Python internally handles the resizing of arrays, it is still very expensive.