Stack (computing)
A stack (stack in English) is an ordered list or data structure that allows data to be stored and retrieved, being the way of access to its elements of type LIFO (from English Last In, First Out, "last in, first out"). This structure is applied in a multitude of cases in the area of computing due to its simplicity and ability to respond to numerous processes.
For data handling, it has two basic operations: stack (push), which places an object on the stack, and its inverse operation, remove (or unstack, pop), which removes the last item stacked.
At any given moment, only the top of the stack is accessible, that is, the last stacked object (called TOS, Top of Stack in English). The remove operation allows this element to be obtained, which is removed from the stack allowing access to the previous one (stacked previously), which becomes the last one, the new TOS.
Stacks are often used in the following contexts:
- Evaluation of expressions in postfix notation (inverse Polish notation).
- Syntactic recognitions of languages independent of the context.
- Implementation of recursivity.
In an operating system, each process has a memory space (stack) to store values and function calls.
A bounded stack is a stack limited to a maximum size imposed by its specification.
By analogy with everyday objects, a stack operation would be equivalent to placing a plate on top of a stack of plates, and a remove operation would be equivalent to removing it.
History
The stack method for evaluating expressions was proposed in 1955 and two years later patented by Friedrich L. Bauer, who received the 1988 "IEEE Computer Society Pioneer Award" for his work in the development of said data structure.
Stack as abstract data type
To summarize, the stack is a container of nodes and has two basic operations: push (or stack) and pop (or unstack). "Push" adds a node to the top of the stack, leaving the rest of the nodes already present in the stack below it. "Pop" returns and removes the current top node from the stack. A frequently used metaphor is the idea of a stack of dishes arranged in a cafeteria in a container with a spring that keeps the stack level. In that series, only the first plate is visible and accessible to the user, all others remain hidden. As new plates are added, each new plate becomes the top of the stack, remaining hidden below the others. As the top plate is removed from the stack, the plate immediately below it moves to the top of the stack. Two important principles are illustrated by this metaphor: only the top plate (the last to be deposited) is accessed, and the rest of the plates in the stack remain hidden. To extract a plate other than the upper one, it will be necessary to extract first those that are on it.
Operations
Usually, along with the two basic operations of stacking and unstacking (push, pop), stacks can implement another series of functions:
- Create (constructor): create the empty stack.
- Size (size(c): returns the number of items in the stack.
- Stacking (push(c): add an element to the stack.
- Unravel (pop)(c): read and remove the upper element of the stack.
- Read last (top or peek): read the upper element of the stack without removing it.
- Empty (♪(c): returns certain if the stack is without elements or false in case it contains any.
A stack can be easily implemented as either an array or a linked list. What identifies a data structure as a stack in any case is not its structure but its interface: the user is only allowed to put and pop data in the way expected of a stack and a few other auxiliary operations.
Another type of data structure is the First In First Out (FIFO) queue.
Hardware Stacks
A very common use of stacks at the hardware architecture level is memory allocation.
Basic architecture of a stack
A typical stack is an area of computer memory with a fixed origin, a place to store data, and a pointer. At first, its number of elements is zero, and the pointer address matches the source address. As data is incorporated, the elements contained in the stack are increased and the pointer updates its address to make it coincide with the last one to be incorporated.
The two operations applicable to all stacks are:
- Stack: place a new data on the stack. The pointer is read to locate the last element, incorporated after it and the pointer is redirected to point to the new built-in data.
- Unravel: extract a data from the pile. The last data is located by the pointer, the data is read and the pointer is redirected to the previous immediate element so that it re-enters the last data of the stack.
A stack is defined by its origin (a memory address), and its capacity to store data. When trying to read past its source (that is, trying to read an element when it is empty) or trying to exceed its capacity to store elements, an error is thrown: overflow error.
A stack of data (regardless of how it is stored in memory) can be viewed as a series of data stacked on top of each other (representation that corresponds to the real world) or as a succession of data stacked from left to right, one after the other.
A stack would occupy a block of memory cells, with a source address, a space reserved for the accumulation of data, and a pointer that points to the last data incorporated. The structure that a stack adopts can be very varied: storing data in increasing or decreasing directions, with flexible storage capacity, with pointers that point to the last element or to the position that the next element to be incorporated must occupy... In any case, it will remain defined by its algorithm: last in, first out.
Hardware Support
Many CPUs have registers that can be used as stack pointers. Some, like Intel x86, have special instructions that implicit the use of a register dedicated to the task of being a stack pointer. Others, like the DEC PDP-11 and Motorola's 68000 family have to deal with ways to make it possible to use a whole series of registers as a stack pointer. The Intel 80x87 series of numerical coprocessors have a set of registers that can be accessed either as a stack or as a series of numbered registers. Some microcontrollers, for example some PICs, have a fixed bottom stack that is not directly accessible. There are also a number of microprocessors that apply a stack directly to the hardware:
- Computer jeans MuP21
- Harris RTX line
- Novix NC4016
Many microprocessor-based stacks are used to implement the Forth programming language at the microcode level. batteries were also used as the basis for a series of mainframes and minicomputers. Those machines were called stack machine, the most famous being the Burroughs B5000.
Software Support
In application programs written in a high-level language, a stack can be implemented efficiently, either using vectors or linked lists. In LISP there is no need to apply the stack, since the stack and unstack functions are available for any list. Adobe PostScript is also designed around a stack that is directly visible and manipulated by the programmer. The use of batteries is very present in software development, hence the importance of batteries as an abstract type of data.
Evaluation expression and parsing
Calculated using reverse polish notation using a stack structure to temporarily store the values. Expressions can be represented in prefix, infix, postfix. Converting from one form of expression to another form requires a stack. Many compilers use a stack to parse the syntax of expressions, program blocks, etc. before translating to low-level code. High-level programming languages are compiled or translated into machine code, converting expressions to the notation that best suits the characteristics of their way of operating, always seeking simplicity.
For example, the calculation: ((1 + 2) * 4) + 3, would be translated as postfix notation with the advantage of not having to attend to the hierarchy of priorities:
In postfix notation: 1 2 + 4 * 3 +
The expression is evaluated from left to right using a stack:
- Stack when the data is an operation
- Wax two operations and evaluate the value when the data is an operator.
- Stack the outcome of the operation.
(stack data is displayed after the operation has been performed):
PILA OPERATION
1 Stacking operation 1 2 Stacking operations 1, 2 + Add operating* 3 4 Stacking operations 3, 4 ♪ Multiplicate operating ♪ 12 3 Stacking operations 12, 3 + Sumar operating* 15 The final result, 15, is in the stack, and the pointer pointed at its address. It reads pop and the stack becomes empty.
*.- The two operators are extracted with what the pointer gives them by eliminated and, in accordance with their order (necessary in operations of subtraction, division and power) the operation is performed. The result is placed on the stack.
Implementation in computer applications
Suppose a function is being processed and inside it calls another function. The function is abandoned to process the calling function, but first the address pointing to the function is stored on a stack. Now suppose that new function calls another function. Likewise, its address is stored, the request is abandoned and attended to. So in as many cases as there are requests. The advantage of the stack is that it does not require defining any control structure or knowing how many times the program will be jumping between functions and then returning to them, with the only limitation being the storage capacity of the stack. As the functions are closed, the previous functions are rescued by means of their addresses stored in the stack and their process is concluded, this until reaching the first one.
The typical case is that of a recursive function (which calls itself), this can be easily implemented using a stack. The function calls itself as many times as necessary until the function result meets the return condition; then, all the open functions complete their cascading process. It is not necessary to know how many times it will be nested and, therefore, neither when the condition will be fulfilled, with the only limitation being the capacity of the stack. If this limit is exceeded, usually because an endless loop is entered, the “stack overflow error” occurs.
Sorting data by the bubble method is solved by a recursive function.
Memory management runtime
Main article: Memory allocation-based stack and Machine stack. A number of programming languages are stack-oriented, which means that most define basic operations (add two numbers, print a character) by taking their arguments from the stack, and performing their return values back on the stack.. For example, PostScript has a stack return and a stack operand, and it also has a bunch of state graphs and a stack dictionary.
Forth uses two stacks, one for passing arguments and a return address subroutine. The use of a return stack is very common, but the unusual use of an argument to a human-readable stack is the reason Forth programming language is called a language-based stack.
Many virtual machines are also stack-oriented, including the p-code machine and the Java virtual machine.
Almost all memory runtime computing environments use a special stack STACK to have information about a procedure or function call and nesting in order to switch to the call context to restore when the call ends. They follow a runtime protocol between the caller and the called to save the arguments and return value on the stack. Stack is an important way to support nested or recursive function calls. This type of stack is implicitly used by the compiler to support CALL and RETURN states (or their equivalents), and is not directly manipulated by the programmer.
Some programming languages use the stack to store data that is local to a procedure. Space for local data is allocated to items on the stack when the procedure is entered, and is cleared when the procedure exits. The C programming language is generally applied in this way. Using the same stack for data and procedure calls has important security consequences (see below), which a programmer must be aware of, in order to avoid introducing serious security bugs into a program.
Fix search problems
Finding a solution to a problem, regardless of whether the approach is exhaustive or optimal, needs stack space. Examples of exhaustive search methods are brute force and backtraking. Examples of optimal search to explore methods are branch and bound and heuristic solutions. All of these algorithms use stacks to remember to search for nodes that have been observed, but not yet explored. The only alternative to using a stack is to use recursion and let the compiler recurse (but in this case the compiler is still using an internal stack). The use of stacks is common in many problems, ranging from storing the depth of trees to solving crossword puzzles or playing computer chess. Some of these problems can be solved by other data structures like a queue.
Security
Security when developing software using stack-type data structures is a factor to take into account due to certain vulnerabilities that incorrect use of these can cause in the security of our software or in the security of the system itself that runs it. For example, some programming languages use the same stack to store the data for a procedure and the link that allows it to return to its caller. This means that the program inserts and extracts the data from the same stack where the critical information is found with the return addresses of the procedure calls. Suppose that when inserting data into the stack we do it in the wrong position so that If we introduce data larger than that supported by the stack, thus corrupting the calls to procedures, we would cause a failure in our program. This technique, used maliciously (it is similar, but in a different scope, to buffer overflow) would allow an attacker to modify the normal operation of our program and our system, and it is at least a useful technique if we do not avoid it in very popular languages such as C++ example.
Stacks in Java
This type of data structure can be implemented dynamically or statically, that is, either with an array or with a linked list. When talking about a static stack, it is considered that the stack will have a defined size and cannot exceed said capacity for storing more information, only the indicated one. And with respect to a dynamic stack it corresponds to a stack that will not have a capacity limit, that is, we can do n number of insertions.
The following is the static stack, which is implemented based on an array:
public class Static{ private int battery[]; private int top;//indicates the position of the last element inserted private int capacity; public Static(int cap♪ capacity=cap; battery=new int[chuckles]capacity]; top=-1; ! public Boolean estaVacia(){ return(top==1); ! public Boolean This one.(){ return(top+1)♪capacity); ! public void stack(int element♪ if(This one.()♪false) battery[+++top]=element; else System.out.println("Upper overflow, you can't stack"); ! public int Unravel(){ if(estaVacia()♪false♪ return battery[chuckles]top--]; ! else{ System.out.println("Lower overflow, cannot be waxed"); ! return -1; ! public static void main (String args[]♪ Static pilita=new Static(5); pilita.stack(1); pilita.stack(12); pilita.stack(3); int r=pilita.Unravel(); System.out.println("The deleted data is "+r); Boolean b=pilita.estaVacia(); Boolean c=pilita.This one.(); System.out.println("Is the plate empty? "+b); System.out.println("Is the plate full? "+c); ! !The following is the implementation of the Stack dynamically, implemented based on a simply linked list:
Download Code.
Node class
package batteries;/** ♪ * @author Mauricio López Ramírez */public class No. { private Char data; private No. Next; public No.(Char data) { this.data = data; ! public Char getDato() { return data; ! public void setDato(Char data) { this.data = data; ! public No. getNext() { return Next; ! public void setNext(No. Next) { this.Next = Next; !!Stack class
package batteries;/** ♪ * @author Mauricio López Ramírez */public class Pila { No. coughs;//Top Of Stack public void stack(Char data) { No. new = new No.(data); if (coughs ♪ null) { coughs = new; ! else { new.setNext(coughs); coughs = new; ! ! public Char Unravel() { No. temp = coughs; coughs = coughs.getNext(); return temp.getDato(); ! public void Print() { No. temp = coughs; while (temp = null) { System.out.print(temp.getDato() + "n"); temp = temp.getNext(); ! !!Handler class
package batteries;/** ♪ * @author Mauricio López Ramírez */public class Handle { public static void main(String[] args) { Pila new = new Pila(); new.stack('A'); new.stack('B'); new.stack('C'); new.Print(); System.out.println(); new.Unravel(); new.Print(); !!