Stack (abstract data type)

In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations: In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations: The order in which elements come off a stack gives rise to its alternative name, LIFO (last in, first out). Additionally, a peek operation may give access to the top without modifying the stack. The name 'stack' for this type of structure comes from the analogy to a set of physical items stacked on top of each other, which makes it easy to take an item off the top of the stack, while getting to an item deeper in the stack may require taking off multiple other items first. Considered 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. This makes it possible to implement a stack as a singly linked list and a pointer to the top element. A stack may be implemented to have a bounded capacity. If the stack is full and does not contain enough space to accept an entity to be pushed, the stack is then considered to be in an overflow state. The pop operation removes an item from the top of the stack. A stack is needed to implement depth-first search. Stacks entered the computer science literature in 1946, when Alan M. Turing used the terms 'bury' and 'unbury' as a means of calling and returning from subroutines. Subroutines had already been implemented in Konrad Zuse's Z4 in 1945. Klaus Samelson and Friedrich L. Bauer of Technical University Munich proposed the idea in 1955 and filed a patent in 1957, and in March 1988 Bauer received the Computer Pioneer Award for the invention of the stack principle. The same concept was developed, independently, by the Australian Charles Leonard Hamblin in the first half of 1954. Stacks are often described by analogy to a spring-loaded stack of plates in a cafeteria. Clean plates are placed on top of the stack, pushing down any already there. When a plate is removed from the stack, the one below it pops up to become the new top. In many implementations, a stack has more operations than 'push' and 'pop'. An example is 'top of stack', or 'peek', which observes the top-most element without removing it from the stack. Since this can be done with a 'pop' and a 'push' with the same data, it is not essential. An underflow condition can occur in the 'stack top' operation if the stack is empty, the same as 'pop'. Also, implementations often have a function which just returns whether the stack is empty. A stack can be easily implemented either through an array or a linked list. 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. The following will demonstrate both implementations, using pseudocode.