Stack Definition:

In computer science, a stack is a last in, first out(LIFO) abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations, the push and the pop.

(or)

A collection of items in which only the most recently added item may be removed. The latest added item is at the top. Basic operations are push and pop. Often top and is Empty are available, too. Also known as "last-in, first-out" or LIFO.

Push:

The push operation adds to the top of the list, hiding any items already on the stack, or initializing the stack if it is empty.

Pop:

The pop operation removes an item from the top of the list, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty list.

Stack Applications:

1. Expression evaluation.

2. Backtracking (game playing, finding paths, exhaustive searching).

3. Memory management, run-time environment for nested language features.

Alogarithm steps:

1. Expression evaluation.

2. Backtracking (game playing, finding paths, exhaustive searching).

3. Memory management, run-time environment for nested language features.

Alogarithm steps:

Step 1: create a list.

i) Create a new empty node top.

ii) Read the stack element and store it in top's data area.

iii) Assign top's link part as NULL (i.e. top->link=NULL).

iv) Assign temp as top (i.e. temp=top).

Step 2: Read next stack operation.

i) If it is Create then go to step1.

ii) If it is Push then it process following steps

a) Check Main memory for node creation.

b) Create a new node top.

c) Read the stack element and store it in top's data area.

d) Assign top's link part as temp (i.e. top->link=temp).

e) Assign temp as top (i.e. temp=top).

iii) If it is pop then it process following steps

a) If top is NULL then display stack is empty.

b) Otherwise assign top as temp (i.e. top=temp, bring the top to top position)

c) Assign temp as temp's link. (i.e. temp=temp->link, bring the temp to top's previous position).

d) Delete top from memory.

iv) If it is traverse then process the following steps

a) Bring the top to stack’s top position(i.e. top=temp)

b) Repeat until top becomes NULL

i) Display the top's data.

ii) Assign top as top's link (top=top->link).

C Program To Implement Stack Using Single Linked List

CPP Program To Implement Stack Using Single Linked List