4.3. Operations

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The last element inserted is the first to be removed.

A stack is a type of data structure that organizes data in such a way that the most recently added item is the first one to be removed. This behavior is similar to a stack of plates where you can only add or remove plates from the top. If you think of stacking dishes, the last dish placed on the pile is the one that comes off first when you need a plate.

Imagine a stack of books. If you want to take a book off the top, you can do that easily, but you'll need to remove all books above it first if you want to reach a book that's further down the stack.

A stack of plates where you add and remove plates only from the top.

In real life, stacks are everywhere. A good analogy is a stack of plates in a cafeteria. You can only add or remove plates from the top of the stack. This ensures that the last plate placed on the pile is the first one taken off, demonstrating the LIFO principle of stacks.

Think about a person stacking plates in a cafeteria line. They add a new plate on top after making their meal, increasing the stack. When they need a plate, they take the top one off first — that's how a stack operates!

• push(): Add an element to the top. • pop(): Remove the top element. • peek() or top(): Retrieve the top element without removing it. • isEmpty(): Check if the stack is empty.

Stacks perform four main operations: 1) Push — this operation adds items to the top of the stack; 2) Pop — this removes the top item from the stack; 3) Peek (or top) — this retrieves the item at the top without removing it; 4) isEmpty — checks if there are no items left in the stack. These operations are designed to maintain the LIFO order.

If we continue with our plate scenario, 'push' would be the action of adding a new plate to the top of the stack, 'pop' is when you take the top plate off, 'peek' is when you simply want to check what's the top plate without taking it, and 'isEmpty' is checking if there are no plates left on the stack.

Stacks can be implemented using arrays or linked lists.

Stacks can be built using different data types such as arrays or linked lists. When using an array, you allocate a fixed size for the stack and primarily use index positions to add or remove elements. However, if you use a linked list, you can dynamically add or remove elements as needed, which provides more flexibility, especially when the number of elements is unknown at the start.

Consider a set of envelopes stacked on a table. If using an array, you might have a fixed number of envelopes in a specific size holder. If using a linked list, you could keep adding or removing envelopes without worrying about space until you run out of envelopes.

Example (Stack Operations in Pseudocode):

push(10)
push(20)
pop() // removes 20
peek() // returns 10

This pseudocode demonstrates basic stack operations. First, 'push(10)' adds 10 to the top of the stack. Then 'push(20)' adds 20 on top of 10. When 'pop()' is called, it removes the last element added, which is 20. Finally, 'peek()' allows you to view the value on the top of the stack, which will be 10 after popping 20.

Imagine writing down names on sticky notes and placing them in a stack. When you write the name John (10) and then Alice (20), you'll see Alice on top. If you remove the top note, you remove Alice, and peeking will reveal John underneath.

--