Stack#
A stack is a linear data structure, a collection of items of the same type. LIFO refers to the behavior of the push (insertion) and pop (deletion) operations.
A stack is a constrained linked list in that insertions and deletions may only occur at one end of the data structure called the top.
operations
push (insert) - add an elem to the top of the stack
pop (delete) - remove the topmost elem of the stack
is_empty - check whether the stack is empty
is_full - check whether the stack is full
top - display the topmost elem of the stack
problems
tower of hanoi
n-queens
infix to prefix
pointer to top, keeps track of the topmost elem of the stack the stack is initialized to -1 check whether the stack is empty by comparing top to -1 adding elems to, removing elems from the stack updates the pointer to top
Array-Based Implementation
push is implemented by incrementing the index of elem top and storing the new elem at that index.
pop is implemented by returning the value stored at index top and then decrementing the index of elem top.
Linked-List Implementation
push is implemented by creating a new node with the new element and setting the next pointer of the current top node to the new node.
pop is implemented by setting the next pointer of the current top node to the next node and returning the value of the current top node.
https://www.tutorialspoint.com/data_structures_algorithms/stack_program_in_c.htm
https://www.digitalocean.com/community/tutorials/stack-in-c