## Stack

## What is a data structure?

So what is a data structure? A data structure is a way of organizing, formatting and storing data so that you may access it as efficiently as possible and modify it if need be.

On earth we're dealing with "stacks", "queues" etc, maybe on other planets they have a different **concept** of what a data structure should be and it's goal. For us it's a way of dealing with data.

What then is a stack data structure?

### Definition

A stack data structure is an **Abstract Data Type**.

**Data type:** The purpose of software is to model/mimic real world objects in your programs. For this we use data types in our programs. For example we can represent a car in our program with the Object data type, a customer's name with the string data type. And this is point number 1.

2nd point to note is that data types have associated with them a set of operations that may be performed on them. For example int data type represents "integers". And we can perform a set of operations on integer data types such as addition, subtraction other mathematical operations. We cannot "subtract" a string, this data type has associated with it another set of related operations.

**Abstract Data type (ADT):** is a type for objects whose behavior is defined by a set of operations. This means that a user only knows what operations can be performed on some data without any knowledge of "how"/implementation. For example you know that maple syrup sweetens the pancakes but not the formula for glucose of exactly how.

Stacks are Abstract Data types as you can use methods such as isFull()to find if the stack is full, without knowledge of the implementation of theisFull() method.

## More stack

Stacks are linear and follow "LIFO" principle which stands for *Last In First Out.* This means that operations such as adding/deleting elements happens on only 1 end of the stack. The last element to be inserted into a stack will be the first one taken out of the stack. Additionally stacks can also only hold the same data types.

Stacks can either be of a fixed size or have dynamic re-sizing.

## How to stack?

Stacks can be implemented in 2 ways:

- Via arrays
- Via linked lists

## Stack operations

1.**push()**:This is used to insert an element at the top of a stack.

2.**pop()**: Removes an elemenet from the top of the stack

3.**size()**: Query the number of elements in a stack

4.**empty()**: Query whether the stack is empty. Returns true if it is empty.

5.**top()**: Return a reference to the top most element of the stack

## Example of stack operations in C++

- Instantiate a new stack of integers

```
#include <iostream>
#include <stack>
using namespace std;
int main(){
stack <int> myLovelyStack
}
```

- Query whether the
*myLovelyStack*stack is empty

```
cout<< myLovelyStack.empty();
//returns true or 1
```

- Push some elements in the
*myLovelyStack*stack

```
int main(){
stack <int> myLovelyStack
myLovelyStack.push(1);
myLovelyStack.push(2);
myLovelyStack.push(3);
myLovelyStack.push(4);
myLovelyStack.push(5);
}
```

- Find the size of
*myLovelyStack*stack

```
cout << myLovelyStack.size();
//returns 5
```

- Pop the top most element from
*myLovelyStack*stack

```
myLovelyStack.pop();
//and now the size of the stack will be..
cout << myLovelyStack.size();
//returns 4
```

- Return the top most element of the
*myLovelyStack*stack

```
cout << myLovelyStack.top();
//returns 4 as remember we popped 5
```

## Some more stack

In order to get all the contents from a stack you have to:

- Access the top most or first element.
- Pop() the 1st element in order to access the element beneath it. Because remember the "LIFO" principle only lets you deal with whatever is the last element inserted into the stack, which then becomes the top most element.
- And you keep doing this till the stack is
**not**empty.

```
void print_stack(stack<int> stackName) {
while (!stackName.empty()) {
cout<<stackName.top();
stackName.pop();
}
}
```

## Discussion