#### Data Structure Tutorial

Overview#### Arrays in Data Structures: A Guide With Examples

Lesson - 1#### All You Need to Know About Two-Dimensional Arrays

Lesson - 2#### All You Need to Know About a Linked List in a Data Structure

Lesson - 3#### The Complete Guide to Implement a Singly Linked List

Lesson - 4#### Implementing Stacks in Data Structures

Lesson - 5#### The Ultimate Guide to Stacks and Queues Data Structures

Lesson - 6#### Your One-Stop Solution for Queue Implementation Using Array

Lesson - 7

Stacks in Data Structures is a linear type of data structure that follows the LIFO (Last-In-First-Out) principle and allows insertion and deletion operations from one end of the stack data structure, that is top. Implementation of the stack can be done by contiguous memory which is an array, and non-contiguous memory which is a linked list. Stack plays a vital role in many applications. You will cover the following topics in this tutorial:

- Introduction to Stacks in Data Structures
- Representation of Stacks in Data Structures
- Working of Stacks in Data Structures
- Basic Operations on Stacks
- Push()
- Pop()
- Peek()
- Empty()
- Full()
- Implementation of Stacks in Data Structures
- Array
- Linked-List
- Application of Stacks in Data Structures

The stack data structure is a linear data structure that accompanies a principle known as LIFO (Last In First Out) or FILO (First In Last Out). Real-life examples of a stack are a deck of cards, piles of books, piles of money, and many more.

This example allows you to perform operations from one end only, like when you insert and remove new books from the top of the stack. It means insertion and deletion in the stack data structure can be done only from the top of the stack. You can access only the top of the stack at any given point in time.

- Inserting a new element in the stack is termed a push operation.
- Removing or deleting elements from the stack is termed pop operation.

Next, you will see how to represent the stacks in data structures in real-time.

Now, assume that you have a stack of books.

You can only see the top, i.e., the top-most book, namely 40, which is kept top of the stack.

If you want to insert a new book first, namely 50, you must update the top and then insert a new text.

And if you want to access any other book other than the topmost book that is 40, you first remove the topmost book from the stack, and then the top will point to the next topmost book.

After working on the representation of stacks in data structures, you will see some basic operations performed on the stacks in data structures.

There following are some operations that are implemented on the stack.

Push operation involves inserting new elements in the stack. Since you have only one end to insert a unique element on top of the stack, it inserts the new element at the top of the stack.

Pop operation refers to removing the element from the stack again since you have only one end to do all top of the stack. So removing an element from the top of the stack is termed pop operation.

Peek operation refers to retrieving the topmost element in the stack without removing it from the collections of data elements.

isFull function is used to check whether or not a stack is empty.

isEmpty function is used to check whether or not a stack is empty.

First, you will learn about the functions:

The following is the algorithm of the isFull() function:

begin If top equals to maxsize return true else return false else if end |

The implementation of the isFull() function is as follows:

Bool isFull() { if(top == maxsize) return true; else return false; } |

The following is the algorithm of the isEmpty() function:

begin If topless than 1 return true else return false else if end |

The implementation of the isEmpty() function is:

Bool isEmpty() { if(top = = -1) return true; else return false; } |

Push operation includes various steps, which are as follows :

Step 1: First, check whether or not the stack is full

Step 2: If the stack is complete, then exit

Step 3: If not, increment the top by one

Step 4: Insert a new element where the top is pointing

Step 5: Success

The algorithm of the push operation is:

Begin push: stack, item If the stack is complete, return null end if top ->top+1; stack[top] <- item end |

This is how you implement a push operation:

if(! isFull ()) { top = top + 1; stack[top] = item; } else { printf(“stack is full”); } |

Step 1: First, check whether or not the stack is empty

Step 2: If the stack is empty, then exit

Step 3: If not, access the topmost data element

Step 4: Decrement the top by one

Step 5: Success

The following is the algorithm of the pop operation:

Begin pop: stack If the stack is empty return null end if item -> stack[top] ; Top -> top - 1; Return item; end |

Implementing a pop operation is as follows:

int pop( int item){ If isEmpty()) { item = stack[top]; top = top - 1; return item; } else{ printf(“stack if empty”); } } |

The algorithm of a peek operation is:

begin to peek return stack[top]; end |

The implementation of the peek operation is:

int peek() { return stack[top]; } |

You can perform the implementation of stacks in data structures using two data structures that are an array and a linked list.

- Array: In array implementation, the stack is formed using an array. All the operations are performed using arrays. You will see how all operations can be implemented on the stack in data structures using an array data structure.

- Linked-List: Every new element is inserted as a top element in the linked list implementation of stacks in data structures. That means every newly inserted element is pointed to the top. Whenever you want to remove an element from the stack, remove the node indicated by the top, by moving the top to its previous node in the list.

Here are the top 7 application of the stack in data structure:

- Expression Evaluation and Conversion
- Backtracking
- Function Call
- Parentheses Checking
- String Reversal
- Syntax Parsing
- Memory Management

Now you will understand all the applications one at a time.

There are three types of expression that you use in programming, they are:

Infix Expression: An infix expression is a single letter or an operator preceded by one single infix string followed by another single infix string.

- X
- X + Y
- (X + Y ) + (A - B)

Prefix Expression: A prefix expression is a single letter or an operator followed by two prefix strings.

- X
- + X Y
- + + X Y - A B

Postfix Expression: A postfix expression (also called Reverse Polish Notation) is a single letter or an operator preceded by two postfix strings.

- X
- X Y +
- X Y + C D - +

Similarly, the stack is used to evaluate these expressions and convert these expressions like infix to prefix or infix to postfix.

Backtracking is a recursive algorithm mechanism that is used to solve optimization problems.

To solve the optimization problem with backtracking, you have multiple solutions; it does not matter if it is correct. While finding all the possible solutions in backtracking, you store the previously calculated problems in the stack and use that solution to resolve the following issues.

The N-queen problem is an example of backtracking, a recursive algorithm where the stack is used to solve this problem.

Whenever you call one function from another function in programming, the reference of calling function stores in the stack. When the function call is terminated, the program control moves back to the function call with the help of references stored in the stack.

So stack plays an important role when you call a function from another function.

Stack in data structures is used to check if the parentheses like ( ), { } are valid or not in programing while matching opening and closing brackets are balanced or not.

So it stores all these parentheses in the stack and controls the flow of the program.

For e.g ((a + b) * (c + d)) is valid but {{a+b})) *(b+d}] is not valid.

Another exciting application of stack is string reversal. Each character of a string gets stored in the stack.

The string's first character is held at the bottom of the stack, and the last character of the string is held at the top of the stack, resulting in a reversed string after performing the pop operation.

Since many programming languages are context-free languages, the stack is used for syntax parsing by many compilers.

Memory management is an essential feature of the operating system, so the stack is heavily used to manage memory.

With that, you have reached the end of this article on Stacks in Data Structures.

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

“Queues and stack in data structures” is what is next. You will learn about some essential differences between stack and queue.

If you are interested in building a career in the field of software development, then feel free to explore Simplilearn’s Courses that will give you the work-ready software development training you need.

Next, you will learn more about data structure and all its types, linear and nonlinear. If you have any doubt regarding the Stacks in Data Structures tutorial, please let us know. We will resolve your queries as soon as possible.

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

Full Stack Web Developer - MERN

355 Learners

Lifetime Access*

*Lifetime access to high-quality, self-paced e-learning content.

- Video Tutorial
The Ultimate Guide to Stacks and Queues Data Structures

- Ebook
Data Analyst Resume Guide

- Article
Who Is a Full Stack Developer?

- Video Tutorial
Arrays in Data Structures: A Guide With Examples

- Video Tutorial
All You Need to Know About a Linked List in a Data Structure

- Ebook
Data Science Interview Guide

prevNext

- Disclaimer
- PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.