Stack (abstract data type) facts for kids

Imagine a stack of plates. You can only add or remove plates from the top!

Simple representation of a stack runtime with push and pop operations.

In computer science, a stack is like a special container for items. Think of it like a stack of plates in a cafeteria. You can only do two main things with it:

• Push: Add a new item to the very top of the stack.
• Pop: Take away the item that was most recently added (the one at the very top).

You can also "peek" at the top item without taking it off. The way items are added and removed is called Last In, First Out, or LIFO. This means the last item you put on the stack is the first one you can take off. If you want an item deeper in the stack, you have to remove all the items above it first.

Stacks are a type of linear data structure. This means items are arranged in a sequence. Both "push" and "pop" operations happen only at one end, which we call the "top" of the stack. If you try to add an item to a stack that is already full, it's called a stack overflow.

How Stacks Started

Stacks became important in computer science around 1946. A famous scientist named Alan M. Turing used ideas like "bury" and "unbury" for computer programs to call and return from different parts of their code.

Later, in 1955, Klaus Samelson and Friedrich L. Bauer from Germany came up with the idea of a stack. They even got a patent for it. Friedrich L. Bauer later received an award for inventing the stack idea. Other people, like Charles Leonard Hamblin, also thought of similar ideas around the same time.

Extra Stack Actions

Besides "push" and "pop," stacks often have other helpful actions:

• Peek (or "top of stack"): This lets you look at the top item without removing it. It's like looking at the top plate without taking it off.
• Is Empty?: This checks if the stack has any items in it.
• Size: This tells you how many items are currently in the stack.

If you try to "pop" or "peek" from an empty stack, it's called an "underflow" condition.

How Software Uses Stacks

Computers use stacks in many ways. Programmers can build stacks using different tools, like arrays or linked lists. The important thing is that you can only "push" or "pop" items from the top, just like a real stack.

Building Stacks with Arrays

You can use an array to make a stack. An array is like a list of numbered boxes. The first box (at number 0) is the bottom of our stack. We keep track of where the "top" of the stack is using a special number.

Here's a simple idea of how it works: structure stack: maxsize : integer // how many items it can hold top : integer // where the next item goes items : array of item // the boxes for items

procedure initialize(stk : stack, size : integer): stk.items ← new array of size items stk.maxsize ← size stk.top ← 0 // stack is empty to start

To push an item: procedure push(stk : stack, x : item): if stk.top = stk.maxsize: report overflow error // stack is full! else: stk.items[stk.top] ← x // put item in the next spot stk.top ← stk.top + 1 // move top up

To pop an item: procedure pop(stk : stack): if stk.top = 0: report underflow error // stack is empty! else: stk.top ← stk.top − 1 // move top down r ← stk.items[stk.top] // get the item return r

Building Stacks with Linked Lists

Another way to build a stack is using a singly linked list. Imagine a chain where each link holds an item and points to the next link. The "head" of the list is the top of our stack.

Here's a simple idea: structure frame: data : item next : frame or nil

structure stack: head : frame or nil size : integer

procedure initialize(stk : stack): stk.head ← nil // stack is empty stk.size ← 0

To push an item: procedure push(stk : stack, x : item): newhead ← new frame newhead.data ← x newhead.next ← stk.head // new item points to old top stk.head ← newhead // new item is now the top stk.size ← stk.size + 1

To pop an item: procedure pop(stk : stack): if stk.head = nil: report underflow error // stack is empty! r ← stk.head.data // get data from the top item stk.head ← stk.head.next // move top to the next item stk.size ← stk.size - 1 return r

Stacks in Programming Languages

Many programming languages have built-in ways to use stacks. For example, Perl, Python, and JavaScript let you use "push" and "pop" on their list or array types.

Here's an example in Java:

import java.util.Stack;

class StackDemo {
    public static void main(String[]args) {
        Stack<String> stack = new Stack<String>();
        stack.push("A");    // Put "A" on the stack
        stack.push("B");    // Put "B" on the stack
        stack.push("C");    // Put "C" on the stack
        stack.push("D");    // Put "D" on the stack
        System.out.println(stack.peek());    // Shows "D" (the top)
        stack.pop();    // Takes "D" off
        stack.pop();    // Takes "C" off
    }
}

How Hardware Uses Stacks

Computers also use stacks in their hardware, especially for managing memory.

Basic Stack Design

A typical stack in a computer's memory has a fixed starting point and a size that changes. A "stack pointer" is like a marker that always points to the most recent item on the stack.

The two main actions are:

• Push: The stack pointer moves, and new data is written where it points.
• Pop: Data is read from where the stack pointer is, and then the pointer moves back.

Stacks grow in one direction from their starting point. If a "pop" tries to go past the stack's start, it's a "stack underflow." If a "push" tries to go past the stack's maximum size, it's a "stack overflow."

Stacks in Computer Processors

Many computer processors, like the ones in older computers (x86, Z80), have special parts just for stacks. They have specific instructions to "call" a part of a program, "return" from it, "push" data, and "pop" data. This helps the computer run programs efficiently.

Some computers even use stacks for math and logic. They put numbers on a stack, do calculations on the top numbers, and then put the result back on the stack. These are called "stack machines."

What Stacks Are Used For

Evaluating Math and Understanding Code

Stacks are super useful for calculators that use a special way of writing math problems (like reverse Polish notation). They also help computer programs understand the structure of other programs. Many programming languages use stacks to figure out how to run the code.

Backtracking Through Choices

A typical call stack, storing local data and call information for multiple levels of procedure calls. This stack grows downward from its origin.

Imagine you're trying to find your way through a maze. You pick a path, but sometimes it's a dead end. How do you go back to where you made the wrong turn? Stacks can help!

When you choose a path, you "push" that choice onto a stack. If you hit a dead end, you "pop" the last choice off the stack. This lets you go back to your last good spot and try a different path. This process is called backtracking. It's used in many computer algorithms, like finding all possible paths in a network.

Managing Memory for Programs

When a computer program runs, it often needs to store temporary information. Stacks are used for this. For example, when one part of a program calls another part (like a function), a special "call stack" is used. This stack remembers where to return to after the function finishes. It also stores temporary data that the function needs.

Many programming languages, like C, use this type of stack to store data that only belongs to a specific part of the program. This data is added to the stack when that part of the program starts and removed when it finishes.

Keeping Stacks Safe

Sometimes, the way stacks are used can create problems, especially for computer security.

Some programming languages use the same stack for both temporary data and important information about where a program should go next. If a program tries to put too much data into a small space on the stack, it can overwrite this important information. This can cause the program to crash or behave in unexpected ways.

Bad actors might try to use this weakness in something called a "stack smashing" attack. They give a program too much input data, hoping it will overwrite the stack's important parts. If they succeed, they might be able to make the program do things it shouldn't, like run unauthorized commands.

This type of problem is a common source of security issues in software. It's why programmers need to be very careful when handling data and making sure it fits correctly on the stack.

See Also

In Spanish: Pila (informática) para niños