Stack

UNIT – II LINEAR DATA STRUCTURES

Stacks Primitive Operations:

A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure - elements can be added and removed from the stack only at the top. Push adds an item to the top of the stack, pop removes the item from the top. A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book on the top.

A stack may be implemented to have a bounded capacity. If the stack is full and does not contain enough space to accept an entity to be pushed, the stack is then considered to be in an overflow state. The pop operation removes an item from the top of the stack. A pop either reveals previously concealed items or results in an empty stack, but, if the stack is empty, it goes into underflow state, which means no items are present in stack to be removed.

Stack (ADT) Data Structure:

Stack is an Abstract data structure (ADT) works on the principle Last In First Out (LIFO). The last element add to the stack is the first element to be delete.  Insertion and deletion can be takes place at one end called TOP. It looks like one side closed tube.

·         The add operation of the stack is called push operation

·         The delete operation is called as pop operation.

·         Push operation on a full stack causes stack overflow.

·         Pop operation on an empty stack causes stack underflow.

·         SP is a pointer, which is used to access the top element of the stack.

·         If you push elements that are added at the top of the stack;

·         In the same way when we pop the elements, the element at the top of the stack is deleted.

 

Operations of stack:

There are two operations applied on stack they are

1.    push

2.  pop.

While performing push & pop operations the following test must be conducted on the stack.

1)  Stack is empty or not

2)  Stack is full or not

Push:

Push operation is used to add new elements in to the stack. At the time of addition first check the stack is full or not. If the stack is full it generates an error message "stack overflow".

Pop:

Pop operation is used to delete elements from the stack. At the time of deletion first check the stack is empty or not. If the stack is empty it generates an error message "stack underflow".

Representation of a Stack using Arrays:

Let us consider a stack with 6 elements capacity. This is called as the size of the stack. The number of elements to be added should not exceed the maximum size of the stack. If we attempt to add new element beyond the maximum size, we will encounter a stack overflow condition. Similarly, you cannot remove elements beyond the base of the stack. If such is the case, we will reach a stack underflow condition.

When a element is added to a stack, the operation is performed by push().

 

When an element is taken off from the stack, the operation is performed by pop().

Source code for stack operations, using array:

STACK: Stack is a linear data structure which works under the principle of last in first out.   Basic operations: push, pop, display.

1.       PUSH: if (top==MAX), display Stack overflow else reading the data and making stack [top]

=data and incrementing the top value by doing top++.

2.       POP: if (top==0), display Stack underflow else printing the element at the top of the stack and decrementing the top value by doing the top.

3.       DISPLAY: IF (TOP==0), display Stack is empty else printing the elements in the stack from stack [0] to stack [top].

#include <stdio.h>

int MAXSIZE = 8;

int stack[8]; int top = -1;

int isempty() {

if(top == -1)

return 1; else

return 0;

}

int isfull() {

if(top == MAXSIZE) return 1;

else

return 0;

}

int peek() {

return stack[top];

}

int pop() { int data;

if(!isempty()) {

data = stack[top]; top = top - 1; return data;

}else {

printf("Could not retrieve data, Stack is empty.\n");

}

}

int push(int data) {

if(!isfull()) { top = top + 1;

stack[top] = data;

}else {

printf("Could not insert data, Stack is full.\n");

}

}

int main() {

// push items on to the stack push(3);

push(5);

push(9);

push(1);

push(12);

push(15);

printf("Element at top of the stack: %d\n" ,peek()); printf("Elements: \n");

// print stack data while(!isempty()) {

int data = pop(); printf("%d\n",data);

}

printf("Stack full: %s\n" , isfull()?"true":"false"); printf("Stack empty: %s\n" , isempty()?"true":"false");

return 0;

}

 

Stack Applications:

1.      Stack is used by compilers to check for balancing of parentheses, brackets and braces.

2.      Stack is used to evaluate a postfix expression.

3.      Stack is used to convert an infix expression into postfix/prefix form.

4.      In recursion, all intermediate arguments and return values are stored on the processor‟s stack.

5.      During a function call the return address and arguments are pushed onto a stack and on return they are popped off.

6.      Depth first search uses a stack data structure to find an element from a graph.

In-fix- to Postfix Transformation: Procedure:

Procedure to convert from infix expression to postfix expression is as follows:

1.                  Scan the infix expression from left to right.

2.                  a)        If the scanned symbol is left parenthesis, push it onto the stack.

b)                  If the scanned symbol is an operand, then place directly in the postfix expression (output).

c)                   If the symbol scanned is a right parenthesis, then go on popping all the items from the stack and place them in the postfix expression till we get the matching left parenthesis.

d)                  If the scanned symbol is an operator, then go on removing all the operators from the stack and place them in the postfix expression, if and only if the precedence of the operator which is on the top of the stack is greater than (or equal) to the precedence of the scanned operator and push the scanned operator onto the stack otherwise, push the scanned operator onto the stack.

Convert the following infix expression A + B * C – D / E * H into its equivalent postfix expression.

Symbol	Postfix string	Stack	Remarks
A	A
+	A	+
B	A B	+
*	A B	+ *
C	A B C	-
-	A B C * +	-
D	A B C * + D	-
/	A B C * + D	- /
E	A B C * + D E	- /
*	A B C * + D E /	- *

H	A B C * + D E / H	- *
End of string	A B C * + D E / H * -	The input is now empty. Pop the output symbols from the stack until it is empty.

Evaluating Arithmetic Expressions: Procedure:

The postfix expression is evaluated easily by the use of a stack. When a number is seen, it is pushed onto the stack; when an operator is seen, the operator is applied to the two numbers that are popped from the stack and the result is pushed onto the stack.

Evaluate the postfix expression: 6 5 2 3 + 8 * + 3 + *

Symbol	Operand 1	Operand 2	Value	Stack	Remarks
6				6
5				6, 5
2				6, 5, 2
3				6, 5, 2, 3	The  first  four  symbols  are placed on the stack.
+	2	3	5	6, 5, 5	Next a „+‟ is read, so 3 and 2 are popped from the stack and their sum 5, is pushed
8	2	3	5	6, 5, 5, 8	Next 8 is pushed
*	5	8	40	6, 5, 40	Now a „*‟ is seen, so 8 and 5 are popped as 8 * 5 = 40 is pushed
+	5	40	45	6, 45	Next, a „+‟ is seen, so 40 and 5 are popped and 40 + 5 = 45 is pushed
3	5	40	45	6, 45, 3	Now, 3 is pushed
+	45	3	48	6, 48	Next, „+‟ pops 3 and 45 and pushes 45 + 3 = 48 is pushed
*	6	48	288	288	Finally, a „*‟ is seen and 48 and 6 are popped, the result 6 * 48 = 288 is pushed

Source Code:

If we compile and run the above program, it will produce the following result −