# Stack

## What is Stack?

{% hint style="success" %}
💡 A Stack is a data structure that follows the **Last-In-First-Out (LIFO)** principle. Imagine a pile of plates; the first plate you put on is the last one you can take off. This "stack" behavior governs how data is added and removed in a stack data structure. A stack is typically implemented with a dynamic array or with a singly linked list.
{% endhint %}

**Here are some key characteristics of stacks:**

* **Limited access:** You can only add or remove elements from the top of the stack, also known as the **head**.
* **LIFO order:** The element added last is the first one to be removed. This is like the pile of plates where the newest plate goes on top and the oldest one underneath is retrieved first.
* **Dynamic size:** Stacks can grow or shrink as needed by adding or removing elements.
* **Efficient push/pop operations:** **Adding** (pushing) and **removing** (popping) elements from the top are typically constant-time operations ( $$O(1)$$).

<figure><img src="/files/iz7uiX1YfWwyJ7TtHN0W" alt=""><figcaption><p>Stack</p></figcaption></figure>

## Big O Notation of Stack Operations

| Operation | Time Complexity | Explanation                                               |
| --------- | --------------- | --------------------------------------------------------- |
| Push      | $$O(1)$$        | Adding an element to the top is fast.                     |
| Pop       | $$O(1)$$        | Removing the top element is fast.                         |
| Peek      | $$O(1)$$        | Accessing the top element is fast.                        |
| Search    | $$O(n)$$        | Finding a specific element requires traversing the stack. |
| IsEmpty   | $$O(1)$$        | Checking if the stack is empty is fast.                   |

Overall, stacks are versatile data structures with simple operations and efficient access for the top element. However, due to their LIFO nature, accessing specific elements within the stack or searching for them is less efficient than in other data structures.

## How are stacked used?

**Common use cases of stacks include:**

* **Undo/redo functionality:** In software, stacks are often used to implement undo and redo actions, allowing users to reverse or redo their previous steps.
* **Function calls:** When a function is called, its arguments and return address are often stored on a stack, allowing for proper execution and returning to the calling function.
* **Expression evaluation:** Stacks are used to evaluate expressions by storing operands and operators in the proper order, ensuring correct mathematical operations.
* **Parsing data:** When processing data streams or languages, stacks can be used to temporarily store elements and track the parsing state.

## Implementation of Stack In JavaScript

```
// Working in progress
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://thomasbui.gitbook.io/blog/software-engineering/data-structures-and-algorithms/stack.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.