8: Stack Data Structure

Stack
Introduction
Stack is a list of items in which all insertions and deletions are made at one end, called the top. Stack is a data
structure that is particularly useful in applications involving reversing.
LIFO : Last In First Out
Stack Implementation
Stack can be implemented in two different ways:
1. Contiguous stack: the stack is implemented as an array.
2. Linked stack: pointers and dynamic memory allocation is used to implement the stack.
Stack Operations
Initialise: creates/initialises the stack
push(e): Insert element e, to be the top of the stack.
pop(): Remove from the stack and return the top element on the stack; an error occurs if the stack is empty.
size(): Return the number of elements in the stack.
isEmpty(): Return a Boolean indicating if the stack is empty.
top(): Return the top element in the stack, without removing it; an error occurs if the stack is empty.
? A Simple Array-Based Stack Implementation
We can implement a stack by storing its elements in an array. Specifically, the stack in this implementation
consists of an N element array S with an integer variable t that gives the index of the top element in array S.
Implementing a stack with an array S. The top element in the stack is stored in the cell S[t].
Recalling that arrays start at index 0 in Java, we initialize t to ?1, and we use this value for t to identify an
empty stack. Likewise, we can use t to determine the number of elements (t + 1).