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

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

void push(int data) { if(!isFull()) { top = top + 1; stack[top] = data; } else { printf("Could not insert data, Stack is full.\n"); }}

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()

int isfull() { if(top == MAXSIZE) return 1; else return 0; }

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 ()

int isempty() { if(top == -1) return 1; else return 0; }

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

Read Also

1. What is Data structure?,Linear and nonlinear data structure.
2. Array Data Structure, sorting array using algorithm bubble sort,merge sort,quick sort,linear sort. searching elements in the array using Binary search,linear search.
3. Linked list
4. What is Struct in C
5. Graph Data Structure in C
6. Tree Data Structure, Learn Binary tree,Binary Search tree and Binary search tree algorithem.
7. What is the pointer in C|what is value at(*ptr) operator