Stack (data structure)
Encyclopedia : S : ST : STA : Stack (data structure)
In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). Stacks are very widely and extensively used in modern computer systems, and are usually implemented through a combination of hardware and software features.
A stack-based computer system is one that stores temporary information primarily in stacks, rather than hardware CPU registers (a register-based computer system).
Abstract data type
As an abstract data type, the stack is a container (data structure) of nodes and has two basic operations: push and pop. Push adds a given node to the top of the stack leaving previous nodes below. Pop removes and returns the current top node of the stack. A frequently used metaphor is the idea of a stack of plates in a spring loaded cafeteria stack. In such a stack, only the top plate is visible and accessible to the user, all other plates remain hidden. As new plates are added (pushed), each new plate becomes the top of the stack, and hides each plate below. As plates are removed (popped) from the stack, they can be used, and second plate becomes the top of the stack. Two important principles are illustrated by this metaphor, the Last In First Out principle is one. The second is that the contents of the stack are hidden. Only the top plate is visible, so to see what is on the third plate, the first and second plates will have to be removed.
Other Operations
In modern computer languages, the stack is usually implemented with more operations than just "push" and "pop". The length of a stack can often be returned as a parameter. Another helper operation peek can return the current top node of the stack without removing it from the stack.Implementation
A typical storage requirement for a stack of n elements is O(n). The typical time requirement of O(1) operations is also easy to satisfy with an array or linked list implementation.Related Data Structures
The abstract data type and data structure of the First In First Out (FIFO) principle is the queue, and the combination of stack and queue operations is provided by the deque. For example, changing a stack into a queue in a search algorithm can change the algorithm from a depth-first search (DFS) into a breadth-first search (BFS).Basic architecture of a stack
A typical stack is an area of computer memory with a fixed origin and a variable size. Initially the size of the stack is zero. A stack pointer, usually in the form of a hardware register, points to the most recently referenced location on the stack; when the stack has a size of zero, the stack pointer points to the origin of the stack.
The two operations applicable to all stacks are:
- a push operation, in which a data item is placed at the location pointed to by the stack pointer, and the address in the stack pointer is adjusted by the size of the data item;
- a pop or pull operation: a data item at the current location pointed to by the stack pointer is removed, and the stack pointer is adjusted by the size of the data item.
For example, a stack might start at a memory location of one thousand, and expand towards lower addresses, in which case new data items are stored at locations ranging below 1000, and the stack pointer is decremented each time a new item is added. When an item is removed from the stack, the stack pointer is incremented.
Stack pointers may 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 grows); however, the stack pointer cannot cross the origin of the stack. In other words, if the origin of the stack is at address 1000 and the stack grows downwards (towards addresses 999, 998, and so on), the stack pointer must never be incremented beyond 1000 (to 1001, 1002, etc.). If 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 operation causes the stack pointer to increment or decrement beyond the maximum extent of the stack, a stack overflow occurs.
Some environments that rely heavily on stacks may provide additional operations, for example:
- Dup(licate): the top item is popped and pushed again so that an additional copy of the former top item is now on top, with the original below it.
- Peek: the topmost item is popped, but the stack pointer is not changed, and the stack size does not change (meaning that the item remains on the stack). This is also called top operation in many articles.
- Swap or exchange: the two topmost items on the stack exchange places.
- Rotate: the n topmost items are moved on the stack in a rotating fashion. For example, if n=3, items 1, 2, and 3 on the stack are moved to positions 2, 3, and 1 on the stack, respectively. Many variants of this operation are possible, with the most common being called left rotate and right rotate.
apple banana banana ==right rotate==> cucumber cucumber apple
cucumber banana apple ==right rotate==> apple cucumber bananaA stack is usually represented in computers by a block of memory cells, with the "bottom" at a fixed location, and the stack pointer holding the address of the current "top" cell in the stack. The top and bottom terminology are used irrespective of whether the stack actually grows towards lower memory addresses or towards higher memory addresses.
Pushing an item on to the stack adjusts the stack pointer by the size of the item (either decrementing or incrementing, depending on the direction in which the stack grows in memory), pointing it to the next cell, and copies the new top item to the stack area. Depending again on the exact implementation, at the end of a push operation, the stack pointer may point to the next unused location in the stack, or it may point to the topmost item in the stack. If the stack points to the current topmost item, it will be updated before a new item is pushed onto the stack; if it points to the next available location in the stack, it will be updated after the new item is pushed onto the stack.
Popping the stack is simply the inverse of pushing. The topmost item in the stack is removed and the stack pointer is updated, in the opposite order of that used in the push operation.
Hardware support
Many CPUs have registers that can be used as stack pointers. Some, like the x86, have special instructions that implicitly use a register dedicated to the job of being a stack pointer. Others, like the PDP-11 and the 68000 family have addressing modes that make it possible to use any of a set of registers as a stack pointer. The 80x87 series of numeric coprocessors has 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-depth stack that is not directly accessible.
There are also a number of microprocessors which implement a stack directly in hardware:
- Computer Cowboys MuP21
- Harris RTX line
- Novix NC4016
Software support
In application programs written in a high level language, a stack can be implemented efficiently using either arrays or linked lists. In LISP there is no need to implement the stack, as the functions push and pop are available for any list. Adobe PostScript is also designed around a stack that is directly visible to and manipulated by the programmer.
Applications
Stacks are ubiquitous in the computing world.
Expression evaluation and syntax parsing
Calculators employing reverse Polish notation use a stack structure to hold values. Expressions can be represented in prefix, postfix or infix notations. Conversion from one form of the expression to another form needs a stack. Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code. Most of the programming languages are context-free languages allowing them to be parsed with stack based machines. Note that natural languages are context sensitive languages and stacks alone are not enough to interpret their meaning.For example, The calculation: ((1 + 2) * 4) + 3 can be written down like this in postfix notation with the advantage of no precedence rules and parentheses needed:
1 2 + 4 * 3 +The expression is evaluated from the left to right using a stack:
- push when encountering an operand and
- pop two operands and evaluate the value when encountering an operation.
- push the result
| Input | Operation | Stack |
|---|---|---|
| 1 | Push operand | 1 |
| 2 | Push operand | 1, 2 |
| Add | 3 | |
| 4 | Push operand | 3, 4 |
| * | Multiply | 12 |
| 3 | Push operand | 12, 3 |
| Add | 15 |
The final result, 15, lies on the top of the stack at the end of the calculation.
Runtime memory management
- Main articles: Stack-based memory allocation and Stack machine
Forth uses two stacks, one for argument passing and one for subroutine return addresses. The use of a return stack is extremely commonplace, but the somewhat unusual use of an argument stack for a human-readable programming language is the reason Forth is referred to as a stack-based language.
Many virtual machines are also stack-oriented, including the p-Code machine and the Java virtual machine.
Almost all computer runtime memory environments use a special stack (the "call stack") to hold information about procedure/function calling and nesting in order to switch to the context of the called function and restore to the caller function when the calling finishes. They follow a runtime protocol between caller and callee to save arguments and return value on the stack. Stacks are an important way of supporting nested or recursive function calls. This type of stack is used implicitly by the compiler to support CALL and RETURN statements (or their equivalents) and is not manipulated directly by the programmer.
Some programming languages use the stack to store data that is local to a procedure. Space for local data items is allocated from the stack when the procedure is entered, and is deallocated when the procedure exits. The C programming language is typically implemented in this way. Using the same stack for both data and procedure calls has important security implications (see below) of which a programmer must be aware in order to avoid introducing serious security bugs into a program.
Solving search problems
Solving a search problem, regardless of whether the approach is exhaustive or optimal, needs stack space. Examples of exhaustive search methods are bruteforce and backtracking. Examples of optimal search exploring methods are branch and bound and heuristic solutions. All of these algorithms use stacks to remember the search nodes that have been noticed but not explored yet. The only alternative to using a stack is to use recursion and let the compiler do the remembering for you (but in this case the compiler is still using a stack internally). The use of stacks is prevalent in many problems, ranging from simple in-order traversals of trees or depth-first traversals of graphs to a crossword puzzle solver or computer chess game. Some of these problems can be solved by alternative data structures like a queue, when a different order of traversal is required.
Security
Some computing environments use stacks in ways that may make them vulnerable to security breaches and attacks. Programmers working in such environments must take special care to avoid the pitfalls of these implementations.
For example, some programming languages use a common stack to store both data local to a called procedure and the linking information that allows the procedure to return to its caller. This means that the program moves data into and out of the same stack that contains critical return addresses for the procedure calls. If data is moved to the wrong location on the stack, or an oversized data item is moved to a stack location that is not large enough to contain it, return information for procedure calls may be corrupted, causing the program to fail.
Malicious parties may attempt to take advantage of this type of implementation by providing oversized data input to a program that does not check the length of input. Such a program may copy the data in its entirety to a location on the stack, and in so doing it may change the return addresses for procedures that have called it. An attacker can experiment to find a specific type of data that can be provided to such a program such that the return address of the current procedure is reset to point to an area within the stack itself (and within the data provided by the attacker), which in turn contains instructions that carry out unauthorized operations.
This type of attack is a variation on the buffer overflow attack and is an extremely frequent source of security breaches in software, mainly because some of the most popular programming languages (such as C) use a shared stack for both data and procedure calls, and do not verify the length of data items. Frequently programmers do not write code to verify the size of data items, either, and when an oversized or undersized data item is copied to the stack, a security breach may occur.
History
The stack method of expression evaluation was first proposed by early German computer scientist F.L. Bauer, who received the IEEE Computer Society Pioneer Award in 1988 for his work on Computer Stacks.
See also
- Compare with queue, deque
- Call stack
- The computer networking term protocol stack
- stack machine
- Burroughs B5000
References
- Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 10.1: Stacks and queues, pp.200–204.
External links
- [StackAnalyzer]
- [Stack Machines - the new wave]
- [Bounding stack depth]
- [Libsafe - Protecting Critical Elements of Stacks]
- [Stack Checker Tool]
- [Stack Size Analysis for Interrupt-driven Programs] (322 KB)
- [Stack Implementation ( Graphical & Text Mode)] C Language implementation of Stack
- Pointers to [stack visualizations]
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.