Skip to main content

Stack Data Structure

Stack

In this blogpost we are going to learn about Stack. What is the stack? What is the LIFO? What are stack operations? What is the pop operation ?, What is the push operation?, How to perform push/pop operation on stack? and conversions using stack.

  1. What is the stack data structure
  2. Basic Operations of Stack
  3. What is the push operation in Stack
  4. What is the pop operation in Stack
  5. What are applications of Stack
  6. Infix to postfix conversion
stack

Defination of stack

Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

There are many real-life examples of a stack. Consider an example of plates stacked over one another in the canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO(Last In First Out)/FILO(First In Last Out) order.


Basic Operations on Stack

  • push() − Pushing (storing) an element on the stack.
  • pop()<− Removing (accessing) an element from the stack.

To use a stack efficiently, we need to check the status of stack as well. For the same purpose, the following functionality is added to stacks −

  • peek() − get the top data element of the stack, without removing it.
  • isFull() − check if stack is full.
  • isEmpty() − check if stack is empty.

Push operation

The process of putting a new data element onto stack is known as a Push Operation. Push operation involves a series of steps −

  • Step 1 − Checks if the stack is full.
  • Step 2 − If the stack is full, produces an error and exit.
  • Step 3 − If the stack is not full, increments top to point next empty space.
  • Step 4 − Adds data element to the stack location, where top is pointing.
  • Step 5 − Returns success.

Procedure for push operation

  1. begin procedure push: stack, data
  2. if stack is full return null
  3. endif
  4. top ← top + 1
  5. stack[top] ← data
  6. end procedure

Code for push operation


Pop operation

Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of pop() operation, the data element is not actually removed, instead top is decremented to a lower position in the stack to point to the next value.

But in linked-list implementation, pop() actually removes data element and deallocates memory space.


Pop operation may involve the following steps

  1. Step 1 − Checks if the stack is empty.
  2. Step 2 − If the stack is empty, produces an error and exit.
  3. Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
  4. Step 4 − Decreases the value of top by 1.
  5. Step 5 − Returns success.

Algorithm for pop operation

  • begin procedure
  • pop: stack
  • if stack is empty return null
  • endif
  • data ← stack[top]
  • top ← top - 1
  • return data
  • end procedure

Algorithm for isfull()


Algorithm for isempty()

  1. begin procedure isempty
  2. if top less than 1 return true
  3. else return false
  4. endif
  5. end procedure

Code for isempty ()


Applications of stack

In a stack, only limited operations are performed because it is restricted data structure. The elements are deleted from the stack in the reverse order.

Following are the applications of stack:
  1. 1. Expression Evaluation
  3. 2. Expression Conversion
  4. i. Infix to Postfix
  5. ii. Infix to Prefix
  6. iii. Postfix to Infix
  7. iv. Prefix to Infix

Infix expression

Infix, Postfix and Prefix notations are three different but equivalent ways of writing expressions. It is easiest to demonstrate the differences by looking at examples of operators that take two operands.

Infix notation: X + Y Operators are written in-between their operands. This is the usual way we write expressions. An expression such as A * ( B + C ) / D is usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer."


Infix notation needs extra information to make the order of evaluation of the operators clear: rules built into the language about operator precedence and associativity, and brackets ( ) to allow users to override these rules.

For example, the usual rules for associativity say that we perform operations from left to right, so the multiplication by A is assumed to come before the division by D. Similarly, the usual rules for precedence say that we perform multiplication and division before we perform addition and subtraction


Postfix notation

Postfix notation (also known as

"Reverse Polish notation"): X Y + Operators are written after their operands. The infix expression given above is equivalent to A B C + * D / The order of evaluation of operators is always left-to-right, and brackets cannot be used to change this order. Because the "+" is to the left of the "*" in the example above, the addition must be performed before the multiplication.


Operators act on values immediately to the left of them. For example, the "+" above uses the "B" and "C". We can add (totally unnecessary) brackets to make this explicit: ( (A (B C +) *) D /) Thus, the "*" uses the two values immediately preceding: "A", and the result of the addition. Similarly, the "/" uses the result of the multiplication and the "D".


Prefix notations

Prefix notation (also known as "Polish notation"): + X Y Operators are written before their operands. The expressions given above are equivalent to / * A + B C D As for Postfix, operators are evaluated left-to-right and brackets are superfluous. Operators act on the two nearest values on the right. I have again added (totally unnecessary) brackets to make this clear: (/ (* A (+ B C) ) D)


Infix to postfix conversion

Infix to postfix Algorithm
  • 1) Scan the string from left to right
  • 2) Make three columns symbol , postfix expression and stack
  • 3) If symbol = = opening bracket push in stack (i.e put in stack column)
  • 4) If symbol = = closing bracket pop all the elements from stack till we get opening bracket, pop the opening bracket also and then put the pop elements in the postfix expression column leaving opening bracket.
  • 5) If symbol = = alphabet/ digit then put the symbol in postfix expression column
  • 6) If symbol = = operator check priority of top element in the stack.
  • If priority( top element)>= priority(symbol operator) then pop top element and put it in postfix expression column If priority( top element) priority(symbol operator) then push the symbol in the stack
  • 7) If all the symbol finished from the symbol pop all the elements from stack and put it in postfix expression column
Labels:

Comments

Post a Comment

Please give us feedback through comments

Trending⚡

Pointer const and Constant Pointer

A constant pointer is a pointer that cannot change the address which it stores.   Syntax: datatype *const pointer_name;  Example:  int a=10,b=20;  int *const ptr;  ptr=&a;  ptr=&b; //here the address in ptr cannot be changed so not allowed . Pointer to constant  Address in the pointer can be changed but the value of the data element which the pointer points cannot be changed.  Syntax: const datatype * pointer_name;  Example:  int a=10,b=20;  const int *ptr=&a;  *ptr=100; //here the value which ptr points to cannot changed so not allowed ptr=&b; //allowed Pointers and Const  The previous two can be combined to form a constant pointer to constant  Syntax: const datatype *const pointer_name; Example:  const int * const ptr;  int a=10,b=20;  const int * const ptr=&a;  *ptr=100; //not allowed  ptr=&b;//not allowed  Here the value which ptr points to cannot be changed an...
Post a Comment
Read more

India’s Landmark Era of Research, Innovation & Deep-Tech Growth

India’s research and development (R&D) ecosystem is undergoing a historic transformation. The country is shifting from a primarily public-funded research model to a private-sector-driven, innovation-led economy , backed by massive strategic investments. This transformation directly supports the national vision of Viksit Bharat @ 2047 , with Investment and Innovation identified as two of the four core growth engines in the 2025–26 Union Budget . The focus is clear: ➡ Build global innovation leadership ➡ Strengthen deep-tech infrastructure ➡ Attract private capital into strategic sectors ➡ Create a strong research-to-commercialisation pipeline 🧠 Strategic Institutional Foundations Anusandhan National Research Foundation (ANRF) Operational since 2024 Target: ₹50,000 crore mobilisation over 5 years Purpose: Bridge academia–industry collaboration Provide strategic national direction in science & technology Enable interdisciplinary research to solve complex societal challenges R...
Post a Comment
Read more

Policy vs Innovation Matrix - India

Policy vs Innovation Matrix Policy vs Innovation Matrix that shows the structural difference between policy intent and actual innovation output — and how India’s model is transforming to match global innovation systems . From Paper Policies to Product Power 🧱 Traditional Indian Model (Old System) Policy Layer Reality Innovation Outcome Policy Vision Strong national policies Vision without execution pipelines Funding Govt-dominated funding Limited capital availability Risk Culture Risk-averse systems No deep-tech experimentation Research Academic publications Low commercialization Industry Role Minimal R&D involvement Weak private innovation Infrastructure Limited labs & compute Research bottlenecks Talent High-quality brains Brain drain Commercialisation Weak tech transfer Research stays in journals Scale Fragmented schemes No national scale impact Speed Slow approvals Innovation delays Result: ➡ Policy existed ➡ Innovation did not scale ➡ Research stayed inside institutions ...
Post a Comment
Read more

Understanding link.click() in JavaScript

Hey! Today i am going to share with you how to use link.click() function in javascript As a JavaScript developer, you may come across the need to programmatically click a link on a web page. The link.click() method is a commonly used way to do this, and it is important to understand how it works and when to use it. What is link.click()? link.click() is a method that can be used to simulate a click on a link element in JavaScript. It is typically used when you want to trigger a link click event programmatically, rather than requiring the user to physically click the link. How to use link.click() Using link.click() is relatively straightforward. First, you need to select the link element you want to click using a DOM selector such as getElementById() or querySelector(). Then, you can call the click() method on the link element to simulate a click. Here is an example: // select the link element const myLink = document.getElementById('my-link'); // simulate a cl...
Post a Comment
Read more

Basics of Decoder

Basics of Decoder  Decoder is a combinational logic circuit that converts abinary code into the desired output signals. It is called decoder because it performs the reverse process of encoder. The process of converting binaryinput code into desirable output is known as decoding.  Figure 1 is the logic symbol of decoder with ‘n’ inputs and ‘m’ outputs. In short, it is multiple inputs and multiple outputs device with proper conversion system.  Note that decoder performs the reverse operation of the encoder. A decoder has ‘n’ number of input lines and ‘m’ number of output lines. There are 2n possible input combinations and the number of outputs (m) are less than or equal to 2n. Decoder converts an n bit code to single active output. The information present in one code is obtained back into the desired code. In general Decoder is circuit which convert specific code into more general form of code. A decoder is a logic circuit that accepts a set of inputs that represents a bina...
Post a Comment
Read more

Linked List Data Structure

Linked List Prerequisites for Linked List Definition of linkedlist Important points of Linked List Types of Linked List Basic Operations performed on Linked List Difference Between Linked List and Arrays Drawbacks of Linked List Applications of Linked List In real world Singly Linked List in C Doubly Linked List in C Singly Circular Linked List in C Doubly Circular Linked Listist in C Add node in Singly Linked List Display Data of Linked List Deletion of a node from linked list Prerequisites for Linked List pointer concept (*ptr) Address Operator (&ptr) Pointer A pointer is a variable which stores the address of another variable. By using a pointer we can directly access the memory address of the variable. Like any variable or constant, you must declare a pointer before using it to store any variable address. The general form of a pointer variable declaration is type *variable-name; Here, type is the pointer...
Post a Comment
Read more