Stack storage
In computer science refers to a stack or stack (short stack or basement , often with the English word stack called) is a commonly used dynamic data structure . Most microprocessors support it directly using machine instructions.
Working principle
A stack can theoretically hold any number of objects, but in practice it is limited. Elements can only be placed on top of the stack and only read from there. Elements are stacked on top of each other and removed from the stack in reverse order. This is also known as the last-in-first-out principle (LIFO).
The following operations are available for this purpose:
- push (also "basement")
- puts the item on top of the stack.
- pop ("basement")
- returns the topmost object and removes it from the stack. With some processors like the MOS Technology 6502 this action is called pull .
- peek ("look up")
- returns the topmost object without removing it (sometimes also called top , ie "top").
In automata theory , stacks are used to theoretically consider certain problem classes (see push-down automaton ). Thus it distinguishes accurately between a real stack one, can be read in which no element other than the top, and stack considered in which each element, but can not be changed. In practice, however, this distinction hardly plays a role; almost every implementation is a stack. Therefore, the terms are generally used synonymously.
There are many variations on the basic principle of stacking operations. Each batch has a fixed location in memory where it starts. As data items are added to the stack, the stack pointer moves to show the current extent of the stack, which is expanding away from the origin.
Stack pointers can point to the origin of a stack or to a limited range of addresses either above or below the origin, depending on the direction in which the stack is growing. However, the stack pointer cannot cross the origin of the stack. In other words, if the origin of the stack is at memory address 1000 and the stack grows down towards memory addresses 999, 998, etc., the stack pointer must never be incremented beyond 1000 to 1001, 1002, etc. When a pop operation on the stack causes the stack pointer to move past the origin of the stack, a stack underflow occurs. If a push causes the stack pointer to increase or decrease beyond the maximum extent of the stack, a stack overflow occurs.
Some runtimes , which are heavily dependent on batches, may offer additional operations, for example
duplicate ("duplicate")
The top element is faded in and then pressed again (twice) so that there is now an additional copy of the previous top element with the original underneath on top.
swap or exchange ("exchange")
The top two items on the stack swap places.
rotate or roll ("rotate")
The n top elements are shifted while rotating on the stack. For example, if n = 3 , items 1, 2, and 3 on the stack move to positions 2, 3 and 1, respectively, on the stack. Many variations of this operation are possible, the most common of which is referred to as left turn and right turn.
Stacks are often represented as growing from the bottom up. They can also be visualized growing from left to right, so that "topmost" becomes "far right", or even growing from top to bottom. The important feature is that the bottom of the stack is in a fixed position. The illustration in this section is an example of a top-to-bottom growth visualization: The top (28) is the "bottom" stack since the "top" stack (9) is where items are pushed or pushed out.
A stack is usually represented in computers by a block of memory cells , the "bottom" being in a fixed location and the stack pointer containing the memory address of the current "top" cell in the stack. The upper and lower terminology is used regardless of whether the stack is actually growing toward lower memory addresses or toward higher memory addresses.
When you push an element onto the stack, the stack pointer is adjusted by the size of the element, i.e. either decremented or incremented , depending on the direction in which the stack grows in the memory, by pointing to the next memory cell and the new top element copied into the stack area. Depending on the exact implementation , the stack pointer can point to the next unused position in the stack or to the topmost element in the stack at the end of a push operation. When the stack points to the current top item, the stack pointer is updated before a new item is pushed onto the stack. If it points to the next available position in the stack, it will be updated after the new item is moved onto the stack.
illustration
A stack bin is like a stack of moving boxes. A new box can always be packed on top of the stack (corresponds to push ) or a box can be taken down from above (corresponds to pop ). As a rule, access is only possible to the top element of the stack. You cannot add or remove a box further down the stack. However, in some implementations there are commands to swap the topmost elements (SWAP, ROT).
history
The use of a stack memory to translate programming languages wase patented in 1957 by Friedrich L. Bauer and Klaus Samelson under the name "Kellerprinzip" and developed around the same time independently of the Australian philosopher Charles Hamblin . The long-lacking international recognition and honoring of their work did not take place until 1988. Bauer received the renowned Computer Pioneer Award ( IEEE ) for computer stacks. Samelson had died in 1980.
Applications
With stacks you can easily check terms and syntaxes for correct nesting. This is often z. B. required for processing BB codes and XML documents.
Microprocessors
In microprocessors there is often a special register , the stack pointer. This register contains a memory address that points to the current stack entry (of the current process ). Many instructions / operations of the microprocessor use this stack entry. Among other things, there are commands with which you can write to the stack (e.g. push on the x86 processor ) or read from it (e.g. pop ). The stack pointer is automatically decreased or increased.
The operation Jump To subroutine (jump to a subroutine ) puts on the stack from the return address, which later from surgery Return From subroutine is used. Subroutines or functions , as known from programming languages such as C , are passed the parameters via the stack, which also accepts the return values. Local variables are also stored on the stack. Among other things , this allows recursion , calling a function from this very function. If only one entry too many or too little is read out when returning from a function, this leads to particularly serious program errors , since the processor will then try to execute code at a completely random memory position. By exploiting the incorrectly handled size specification of the data, attackers can attempt to produce a buffer overflow that alters the stack in such a way that malicious code is executed by redirecting the return.
For most processors , the stack starts at a high address and is stacked towards address 0. This means that with push the stack pointer is decreased and something is written to the stack and with pop it is read from the stack and the stack pointer is increased. The stack grows "downwards" in the direction of lower memory addresses. This is historically justified: If, with limited memory, the stack is placed below the memory space that is used by the programs , other program data that are normally stored behind the program cannot overwrite the stack so easily and the stack cannot overwrite the machine program. Furthermore, the top element on the stack can always be addressed with offset zero (relative to the stack pointer) and an element can be added to the stack without knowing the size of the previous top element.
In multitasking systems are available for every process and within the processes for each thread its own stack. When switching between processes or threads, the respective stack pointer is saved and loaded in addition to other registers .
In order to detect errors in the use of the stack due to an "underflow" of the stack pointer, some operating systems such as DOS or CP / M (with COM programs) or OSEK-OS store the jump address of an abort or error handling routine as the lowest value in the stack. If the processor fetches this address from the stack due to an error in the interleaving of calls , it may still be possible to react to the sequence error. Some operating systems can also increase the stack memory during runtime , which can take a relatively long time if the stack is already very large. With other operating systems, the programmer himself has to specify how big the stack should be.
The so-called water level method is used to determine the degree of utilization of the mostly limited stack memory: The entire memory reserved for the stack memory is initialized with a fixed data pattern and then the program is started. The areas that still contain the initialization pattern after a certain runtime can be used to determine how much space on the stack was actually used.
Programming languages
Compilers or interpreters for programming languages usually use push operations before calling a subroutine in order to pass this parameter . Because the compiler knows the types of parameters, they can be of different sizes. In a similar way, results of the subroutine can also be returned in this way. This mechanism is extended again for local variables of the subroutine by also reserving space for them on the stack. This means that the subroutine can then be called recursively . When converting a recursive subroutine into an iterative subroutine , this mechanism must often be implemented explicitly.
Programming languages that are based on a process-based virtual machine , for example Java , P-Code - Pascal , optimize the compiled intermediate code for the use of a stack in order to accelerate the interpretation of this intermediate code at runtime .
Stack implementation
Implementation of a stack in C ++ with a singly linked list :
#include <memory>
#include <stdexcept>
#include <utility>
using namespace std;
template <typename T>
class stack {
struct item {
T value;
unique_ptr<item> next = nullptr;
item(T& _value): value(_value) {}
};
unique_ptr<item> _peek = nullptr;
size_t _size = 0;
public:
// erzeugt einen leeren Stack
stack() {}
// erzeugt einen Stack mit n Elementen von T
stack(size_t n, T _value) {
for (size_t i = 0; i < n; ++i)
push(_value);
}
// Kopierkonstruktor
stack(stack<T>& rhs) {
*this = rhs;
}
// Zuweisungsoperator
stack& operator=(stack<T>& rhs) {
// Überprüfe ob ein Stack sich selbst zugewiesen wird
if (this == &rhs)
return *this;
item* traverse = rhs._peek.get();
// Absteigen zum ersten Element, dann zum zweiten etc.
while (traverse != nullptr) {
push(traverse->value);
traverse = traverse->next.get();
}
return *this;
}
void push(T& _value) {
unique_ptr<item> temp = make_unique<item>(_value);
temp.swap(_peek);
// next des letzten Stackelements ist ein nullptr
_peek->next = move(temp);
_size++;
}
T pop() {
if (_peek == nullptr)
throw underflow_error("Nothing to pop.");
T value = _peek->value;
_peek = move(_peek->next);
_size--;
return value;
}
T& peek() {
if (_peek == nullptr)
throw underflow_error("Nothing to peek.");
return _peek->value;
}
size_t size() {
return _size;
}
};
Implementing a stack in C with an array:
#include <stdbool.h>
#include <stddef.h>
#define LEN 100
int data[LEN];
size_t count = 0;
bool is_empty() {
return count == 0;
}
bool is_full() {
return count == LEN;
}
void push(int value) {
if (is_full())
return;
data[count] = value;
count++;
}
int pop() {
if (is_empty())
return 0;
count--;
return data[count];
}
int peek() {
if (is_empty())
return 0;
return data[count - 1];
}
size_t size() {
return count;
}
Implementation of a stack in Java with a singly linked list:
class Stack<T> {
private class Item {
T value; // Das zu verwaltende Objekt
Item next; // Referenz auf den nächsten Knoten
Item(T _value, Item _next) {
value = _value;
next = _next;
}
}
private Item _peek;
// Prüft, ob der Stapel leer ist
public boolean empty() {
return _peek == null;
}
// Speichert ein neues Objekt
public void push(T _value) {
_peek = new Item(_value, _peek);
}
// Gibt das oberste Objekt wieder und entfernt es aus dem Stapel
public T pop() {
T temp = _peek.value;
if (!empty())
_peek = _peek.next;
return temp;
}
// Gibt das oberste Objekt wieder
public T peek() {
return !empty() ? _peek.value : null;
}
}
Implementation of a stack in Python with a dynamically expandable list:
class Stack:
_data = []
def is_empty(self):
return len(self._data) == 0
def push(self, element):
self._data.append(element)
def pop(self):
if self.is_empty():
return None
return self._data.pop()
def peek(self):
if self.is_empty():
return None
return self._data[-1]
def __str__(self):
return self._data.__str__()
def main():
my_stack = Stack()
print(my_stack.is_empty())
my_stack.push(5)
my_stack.push(3)
print(my_stack.is_empty())
print(my_stack)
print(my_stack.peek())
my_stack.pop()
print(my_stack.peek())
if __name__ == "__main__":
main()
In many programming languages, stacks are already implemented in the standard library. This is how Java makes this functionality available in the class java.util.LinkedList. In the C ++ Standard Template Library , the template offers the stack<T>corresponding functionality, which is usually not implemented with a linked list, unlike here.
Compiler
To translate the source code of a formal language , compilers and interpreters use a parser that uses a stack. The parser can e.g. B. work like a basement machine.
Processing of bracket structures
Stacks are also suitable for evaluating expressions in brackets, such as those used in mathematics . First a stack memory is initialized for operators and operands. The expression in brackets to be processed is now read in symbol by symbol. If an opening bracket is read in, it must be ignored. If an operand or operator is read in, it must be placed on the respective stack.
If a closing parenthesis is read in, the top operator is taken from the stack for the operators and, corresponding to this operator, a suitable number of operands that are required to carry out the operation. The result is then put back on the stack for operands. As soon as the stack for the operators is empty, the result is in the stack for the operands.
Postfix notation
Postfix notation is occasionally used to calculate terms , which with the help of operations makes parentheses and priority rules for the operations superfluous. Numbers are automatically placed on the stack. Binary operators , for example +, -, *, /, fetch the two upper values, unary operators, for example sign change, fetch a value from the stack and then store the intermediate result there again.
Infix notation
With the machine-aided resolution of arithmetic expressions in the so-called infix notation , the operator stands between the numerical values involved, first priority sub-terms are temporarily stored in a stack and the infix term is in fact converted into a postfix term before the result is processed by the Stack is calculated.
Batch Oriented Languages
Batch-oriented languages, e.g. B. Forth or Postscript , handle almost all variable operations over one or more stacks and provide other operators in addition to the above operators . For example, the Forth operator swap swaps the top two elements of the stack. Arithmetic operations are written in Postfix notation and thus also affect the stack.
Forth uses a second stack (return stack) to temporarily store the return addresses of subroutines during the execution phase. This stack is also used during the compilation phase for the addresses of the jump destinations for the control structures. The transfer and return of values to subroutines takes place via the first stack, the second takes the return address. In most implementations, there is also an additional stack for floating point operations .
Stack architecture
A stack architecture implicitly refers to a stack for data operations, i.e. without separate push and pop commands. Examples are the Intel FPU (floating point processor) and the Hewlett-Packard calculators.
Related topics
A first-in-first-out data structure is called queue (Engl. Queue ). Both structures behave differently, but have the same signature (i.e. method structure), which is why they are often taught together.
Another way of managing memory is dynamic memory management , which can handle memory requirements that arise at runtime . This memory is often referred to as the heap and is used when the lifespan of the objects to be stored is different and does not correspond to the restricted principle of the stack memory or the queue.
See also
- Field (data type)
- List (data structure)
- Queue (data structure)
- Heap (data structure)
- Floodfill
- Deque
- Stack trace
literature
- Patent DE1094019 : Method for the automatic processing of coded data and calculating machine for carrying out the method. Filed March 30, 1957 , published December 1, 1960 , inventors: Friedrich Ludwig Bauer, Klaus Samelson (granted August 12, 1971).
Web links
Individual evidence
- ^ Friedrich L. Bauer , Gerhard Goos : Informatik. An introductory overview. First part. 3. Edition. Springer, Berlin 1982, ISBN 3-540-11722-9 , p. 222. "The term 'Keller' for this was introduced by Bauer and Samelson in a German patent application dated March 30, 1957."
- ↑ Patent DE1094019 : Method for the automatic processing of coded data and calculating machine for carrying out the method. Registered on March 30, 1957 , published December 1, 1960 , inventors: Friedrich Ludwig Bauer, Klaus Samelson.