What is a stack? Two operations performed on a stack with required algorithm

What is a stack? Explain any two operations performed on a stack with required algorithm.

Stacks

A simple data structure in which insertion and deletion occur at the same end, is termed (called) a stack. It is a LIFO (Last In First Out) structure.

The operations of insertion and deletion are called PUSH and POP Push - push (put) item onto stack

Pop - pop (get) item from stack

Initial Stack Push(8) Pop TOS=>

4

1

3

6

TOS=>

8

4

1

3

6

TOS=>

4

1

3

6

Our Purpose:

To develop a stack implementation that does not tie us to a particular data type or to a particular implementation.

Implementation:

Stacks can be implemented both as an array (contiguous list) and as a linked list. We want a set of operations that will work with either type of implementation: i.e. the method of implementation is hidden and can be changed without affecting the programs that use them.

The Basic Operations:

Push()

{

if there is room {

put an item on the top of the stack else

give an error message

}

}

Pop()

{

if stack not empty {

return the value of the top item remove the top item from the stack

}

else {

give an error message

}

}

CreateStack()

{

remove existing items from the stack initialise the stack to empty

}

Array Implementation of Stacks: The PUSH operation

Here, as you might have noticed, addition of an element is known as the PUSH operation. So, if an array is given to you, which is supposed to act as a STACK, you know that it has to be a

STATIC

Stack; meaning, data will overflow if you cross the upper limit of the array. So, keep this in mind.

Algorithm:

Step-1: Increment the Stack TOP by 1. Check whether it is always less than the Upper Limit of the stack. If it is less than the Upper Limit go to step-2 else report -"Stack Overflow"

Step-2: Put the new element at the position pointed by the TOP Implementation:

static int stack[UPPERLIMIT]; int top= -1; /*stack is empty*/

..

..

main()

{

..

..

push(item);

..

..

}

push(int item)

{

top = top + 1;

if(top < UPPERLIMIT) stack[top] = item; /*step-1 & 2*/ else

cout<<"Stack Overflow";

}

Note:- In array implementation,we have taken TOP = -1 to signify the empty stack, as this simplifies the implementation.

Array Implementation of Stacks: the POP operation

POP is the synonym for delete when it comes to Stack. So, if you're taking an array as the stack, remember that you'll return an error message, "Stack underflow", if an attempt is made to Pop an item from an empty Stack. OK.

Algorithm

Step-1: If the Stack is empty then give the alert "Stack underflow" and quit; or else go to step-2 Step-2: a) Hold the value for the element pointed by the TOP

b) Put a NULL value instead

c) Decrement the TOP by 1 Implementation:

static int stack[UPPPERLIMIT]; int top=-1;

..

..

main()

{

..

..

poped_val = pop();

..

..

}

int pop()

{

int del_val = 0; if(top == -1)

cout<<"Stack underflow"; /*step-1*/ else

{

del_val = stack[top]; /*step-2*/ stack[top] = NULL;

top = top -1;

}

return(del_val);

}

Note: - Step-2:(b) signifies that the respective element has been deleted. Algorithm

Step-1: If the Stack is empty go to step-2 or else go to step-3

Step-2: Create the new element and make your "stack" and "top" pointers point to it and quit. Step-3: Create the new element and make the last (top most) element of the stack to point to it Step-4: Make that new element your TOP most element by making the "top" pointer point to it. Implementation:

struct node{ int item;

struct node *next;

}

struct node *stack = NULL; /*stack is initially empty*/ struct node *top = stack;

main()

{

..

..

push(item);

..

}

push(int item)

{

if(stack == NULL) /*step-1*/

{

newnode = new node /*step-2*/ newnode -> item = item; newnode -> next = NULL; stack = newnode;

top = stack;

}

else

{

newnode = new node; /*step-3*/ newnode -> item = item; newnode -> next = NULL;

top ->next = newnode; top = newnode; /*step-4*/

}

}