Introduction to Stack
As a DIY (Do It Yourself) activity, most of us enjoyed playing the mathematical puzzle The Tower of Hanoi, The Tower of Brahma, and The Lucas Tower. The objective of these puzzles is to understand the pattern of the disks stacked and move them to the other rod without disturbing its conventional design. Did we realize that we were handling stacks, one of the most efficient data structures of the 1950s?
Interesting facts related to Stack
In 1954, Alan Turing, the Father of Artificial Intelligence, mentioned the burying and unburying of temporary variables used for data storage in subroutines. In 1955 a practical implementation followed with the proposal of Stack - a data structure with memory space used in computing in case of emergencies. Though Klaus Samelson proposed this concept, Friedrich L. Bauer, a mathematician at Technical University Munich, patented it in 1957.
What is a Stack in Data structures?
A Stack is a metaphor for an orderly sequence of items placed one on top of another, restricting access only to the TOP.
A Stack is an Abstract Data type (ADT) that stores a finite number of a particular type of elements in an ordered fashion. A Stack data structure is also referred to as a storage structure, as it stores a definite number of elements and regulates memory management.
In other words, a Stack is a vertical linear data structure with a collection of similar items that facilitates the adding and removing at a particular position, termed TOP. As the element in Stack deletes in reverse order, the data structure features the LIFO (Last In First Out) or FILO (First In Last Out) mechanism.
As the storage capacity and the number of operations done on a Stack data structure are limited, it is also called a restricted data structure. When all the positions (lowermost -(BOTTOM) to the TOP) have data elements, it is said to be a FULLSTACK. A Stack OVERFLOWs when it does not have a space or free position to insert or store, and a stack is EMPTY or UNDERFLOW when it does not contain any element from the BOTTOM to its TOP.
Stack Operations
The basic operations performed on the stack data structures are Push and Pop operations. Push operation involves inserting an element into the stack. The new element can be placed into the stack only at the top of the stack. The operation Pop is the method used to access or delete an element from the stack. Pop operations also can be performed at the top of the stack only.
Adding or inserting an element to the Stack (PUSH) – It adds or inserts a data element to the TOP and increases its size by 1.
Deleting or removing an element from the Stack (POP) - It deletes or removes the most recent data element from the TOP and decreases its size by 1.
Details of the last element (PEEK) – It determines the value of the TOP data element without disturbing the data structure.
Algorithms to create a stack, display the most recently added element in the stack, delete an element, check if the stack is full, etc., are written in various languages to define the customized data structure.
Code to declare a Stack as a Class
class Stack{
int arr[]
int capacity
int top
}Code to create a constructor for Stack
Stack(int cap)
{
capacity = cap
top = -1
}Code to insert a data element in a Stack
void push(int item)
{
if ( top == capacity - 1 )
print( "Stack overflow!" )
else
{
arr[top+1] = item
top = top + 1
}
}Code to obtain the details of the last element in the Stack
int peek()
{
if ( isEmpty() == True )
{
print( "Stack is empty!" )
return -1
}
else
return arr[top]
}
Code to delete a data element in a Stack
void pop()
{
if ( isEmpty() == True )
print( "Stack is empty!" )
else
top = top - 1
}
Code to check if the Stack is empty
bool isEmpty()
{
if ( top == -1 )
return True
else
return False
}
Stack as an Abstract Data Type (ADT)
#define MAX 100
struct stack
{
int top;
int item{MAX};
};
struct stack s;
Stack Data Structure Using Array
A Stack is an array of finite elements. Initially, the BOTTOM and the TOP positions of the Stack are initialized to zero to create an empty stack. Deleting the BOTTOM implies deletion of the data structure Stack.
The array points to the (TOP+1) position during insertion. Each element inserted into the Stack increments the value of the TOP by one, and removal decrements the value of TOP by one.
The length of a stack array is the pointer pointing to the value of the TOP. Thus, a Stack array can be viewed as a three-element compact and dynamic data structure consisting of TOP, BOTTOM, and the data element, facilitating faster access speed than an array.
Stack Data Structure Using Linked List
A stack is a linked list with a finite number of nodes. Each node has data and address elements. While the data element stores the value of the data, the address element stores the address of the next node, where the data is stored. The first node is the HEAD of the linked list. The pointer points to the (HEAD+1) position named TOP with the insertion of the first element into the list. Thus, the TOP points to the directly accessible node in the stack.
The memory locations allocated may be non-contiguous, and the address stored acts as a pointer to the TOP. Thus, each node may contain the address of its next node.
Stack Time Complexity
As the insertion and deletion of data elements from the Stack is a single-step operation, the time complexity of these two operations is O(1). Since a stack is a unidirectional data structure, where all the functions initiate at the TOP, the time complexity of displaying an element is also one. Depending on the size of the Stack, the time complexity of searching changes. The complexity is O(n), where the Stack contains ‘n’ elements.
When a Stack is an array of an average number of elements, its time complexity is slower for the worst cases. However, it improves when a Stack is a LinkedList.
As none of the stack operations require additional space, the space complexity is O(1).
Application of Stack Data Structure
A stack is an inseparable constituent of a compiler and is used in the following applications, It used to:
Ensure Systematic Memory Management as random access to the data elements is impossible.
Evaluate an expression based on the usage of parentheses
Facilitate Recursive operations
Promote the usage of Nested loops (embedded nesting) or convert an expression from postfix to prefix or infix and vice-versa
Confirm the re-entrant code (reusability of the code)
Support Backtracking issues
Enable reversing the string (reading it backwards)
Store the history of the pages visited in the browser
Allow undoing a function in a text editor
Help in tree (non-linear data structure) traversals.
- Stack is applied wherever time and space complexity is crucial factors
Check the correctness of parentheses (in solving algebraic expressions)
Match the brackets used in a looping structure, HTML, and XML
Store the local variables and function parameters in a stack. After execution of the function, these values are automatically deleted (lost), fostering efficient memory management.
Summary
Stacks are limited regarding operational capacity but continue to create advanced data structures for problem-solving. It is not as simple as a DIY activity associated with programming, but a specialized data structure with its own rules of operations and thus provides an additional layer of security to the data. Expertise in stacks paves the path to every facet of computer design. Stack is a linear data structure that follows the last in first out method to store and retrieve data in memory. The two basic operations performed on a stack are push and pop which are performed from the stack top. Stacks are used in many applications where time and space complexity considerations are important.
Take our free skill tests to evaluate your skill!
In less than 5 minutes, with our skill test, you can identify your knowledge gaps and strengths.
Previous Tutorial
