Using a dynamic array, it is possible to implement a stack that can grow or shrink as much as needed. Similarly, pop decrements the top index after checking for underflow, and returns the item that was previously the top one: The push operation adds an element and increments the top index, after checking for overflow: Stk.items ← new array of size items, initially empty Procedure initialize(stk : stack, size : integer): Thus, the stack itself can be effectively implemented as a three-element structure: The program must keep track of the size (length) of the stack, using a variable top that records the number of items pushed so far, therefore pointing to the place in the array where the next element is to be inserted (assuming a zero-based index convention). The first element, usually at the zero offset, is the bottom, resulting in array being the first element pushed onto the stack and the last element popped off. The following will demonstrate both implementations, using pseudocode.Īn array can be used to implement a (bounded) stack, as follows.
What identifies the data structure as a stack, in either case, is not the implementation but the interface: the user is only allowed to pop or push items onto the array or linked list, with few other helper operations. Software stacks Implementation Ī stack can be easily implemented either through an array or a linked list, as stacks are just special cases of lists. Additionally, many implementations provide a check if the stack is empty and one that returns its size. If the stack is empty, an underflow condition will occur upon execution of either the "stack top" or "pop" operations. This could be done with a "pop" followed by a "push" to return the same data to the stack, so it is not considered an essential operation. An example of a non-essential operation is "top of stack", or "peek", which observes the top element without removing it from the stack.
In many implementations, a stack has more operations than the essential "push" and "pop" operations. When a plate is removed from the stack, the one below it pops up to become the new top plate. Clean plates are placed on top of the stack, pushing down any already there. Stacks are often described using the analogy of a spring-loaded stack of plates in a cafeteria. Similar concepts were developed, independently, by Charles Leonard Hamblin in the first half of 1954 and by Wilhelm Kämmerer in 1958. In March 1988, by which time Samelson was deceased, Bauer received the IEEE Computer Pioneer Award for the invention of the stack principle. Bauer of Technical University Munich proposed the idea of a stack in 1955 and filed a patent in 1957. Subroutines had already been implemented in Konrad Zuse's Z4 in 1945. Turing used the terms "bury" and "unbury" as a means of calling and returning from subroutines. Stacks entered the computer science literature in 1946, when Alan M. If the stack is full and does not contain enough space to accept another element, the stack is in a state of stack overflow.Ī stack is needed to implement depth-first search. A stack may be implemented to have a bounded capacity. This data structure makes it possible to implement a stack as a singly linked list and as a pointer to the top element. Ĭonsidered as a linear data structure, or more abstractly a sequential collection, the push and pop operations occur only at one end of the structure, referred to as the top of the stack. As with a stack of physical objects, this structure makes it easy to take an item off the top of the stack, but accessing a datum deeper in the stack may require taking off multiple other items first.
The order in which an element added to or removed from a stack is described as last in, first out, referred to by the acronym LIFO. Calling this structure a stack is by analogy to a set of physical items stacked one atop another, such as a stack of plates. Pop, which removes the most recently added element that was not yet removed.Īdditionally, a peek operation can, without modifying the stack, return the value of the last element added.Push, which adds an element to the collection, and.In computer science, a stack is an abstract data type that serves as a collection of elements, with two main operations: Simple representation of a stack runtime with push and pop operations.
0 kommentar(er)
