# Stack

## Introduction

A stack is an abstract data type that follows the Last-In-First-Out (LIFO) principle. The stack operates with two main methods: PUSH (inserts an element to the top of the stack) and POP (removes the top element from the stack). It can be visualized as a pile of plates in a cafeteria where the topmost plate is the only one accessible and is taken first.

A stack is a fundamental data structure widely used in computer science and programming. It is often used in programming languages to implement function calls, recursive algorithms, expression evaluation, and undo operations, etc.

## Implementation

```
(* Stack *)
type 'a t =
{ mutable used : int
; mutable size : int
; mutable data : 'a array
}
let allocate_space x = Array.(append x (copy x))
let make () = { used = 0; size = 0; data = [||] }
let push s x =
if s.size = 0 then s.data <- [| x |];
if s.used = s.size
then (
s.data <- allocate_space s.data;
s.size <- Array.length s.data);
s.data.(s.used) <- x;
s.used <- s.used + 1
let pop s =
match s.used with
| 0 -> None
| i ->
s.used <- i - 1;
Some s.data.(s.used)
let peek s =
match s.used with
| 0 -> None
| i -> Some s.data.(i - 1)
let is_empty s = s.used = 0
let mem s x = Array.mem x s.data
let memq s x = Array.memq x s.data
let to_array s = Array.sub s.data 0 s.used
```

The provided OCaml code well-implements a stack. The stack is represented as a mutable record with three fields, namely `used`

, `size`

and `data`

. The `used`

field tracks the number of elements currently in the stack. The `data`

field is an array that stores the stack elements. The `size`

field keeps track of the array’s capacity in number of elements.

## Step-by-step Explanation

- The
`allocate_space`

function appends the given array to its copy and returns the concatenated array. - The
`make`

function initializes a new stack with zero size and zero used space. - The
`push`

function adds a new element to the stack. The following cases are tested:- If the stack has not been initialized yet,
`data`

is set to an array containing only the input element. - If the stack is full (i.e.,
`used`

equals`size`

), the`data`

array is extended by invoking the`allocate_space`

function, and`size`

is updated accordingly. - In any of the above cases, the new element is appended to
`data`

,`used`

is updated accordingly.

- If the stack has not been initialized yet,
- The
`pop`

function removes and returns the top element of the stack. The following cases are tested:- If the stack is empty (i.e.,
`used`

equals 0),`None`

is returned. - In any other case, the top element is removed from`data`

,`used`

is updated accordingly, and the top element is returned.

- If the stack is empty (i.e.,
- The
`peek`

function returns the top element of the stack without modifying the stack in any way. The following cases are tested:- If the stack is empty,
`None`

is returned. - In any other case, the top element is returned without modifying the stack.

- If the stack is empty,
- The
`is_empty`

function returns`true`

if the stack is empty (i.e.,`used`

is 0), and`false`

otherwise. - The
`mem`

function returns`true`

if the given element is in the stack (`data`

), and`false`

otherwise, invoking the`mem`

function of the`Array`

module. - The
`memq`

function returns`true`

if the given element is in the stack (`data`

), and`false`

otherwise, invoking the`memq`

function of the`Array`

module. - The
`to_array`

function converts the stack into an array and returns it. The resulting array contains the same elements in the same order as they were in the stack.

## Complexity Analysis

The time-complexity of the `push`

operation is O(1) in the average and worst case. The `push`

function checks for empty and full stacks using constant time checks. Also, the `allocate_space`

function is called on average once every time the size of the stack is doubled.

The time-complexity of the `pop`

and `peek`

operations is O(1) in the worst and average cases since they perform constant-time checks on the stack size.

The space-complexity of the stack is O(n). The size of the stack may be increased dynamically by `allocate_space`

when the stack reaches its full capacity, which could be proportional to a maximum number of elements to be stored in the stack.

Therefore, this implementation of the stack provides good performance in time and space complexity and enable smooth and efficient processing of LIFO data structures.