IT 123A-Stack

A.) Definition/Concept
Stack- is an abstract data type and data structure based on the principle of Last In First Out. (google.com)
History;
The stack method of expression evaluation was first proposed in 1955 and then patented in 1957 by early German computer scientist Friedrich L. Bauer, (google.com)
Abstract data type;
As an abstract data type, the stack is a container of nodes and has two basic operations: push and pop.(google.com)
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 top(also known as peek) can return the current top element of the stack without removing it from the stack.(google.com)
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 a dynamic array or (singly) linked list implementation.
Ex.
class Stack(object):
def __init__(self):
self.stack_pointer = None
def push(self, element):
self.stack_pointer = Node(element, self.stack_pointer)
def pop(self):
e = self.stack_pointer.element
self.stack_pointer = self.stack_pointer.next
return e def peek(self):
return self.stack_pointer.element
def __len__(self):
i = 0
sp = self.stack_pointer
while sp:
i += 1
sp = sp.next
return i class Node(object):
def __init__(self, element=None, next=None):
self.element = element
self.next = next if __name__ == '__main__':
# small use example s = Stack()
[s.push(i) for i in xrange(10)]
print [s.pop() for i in xrange(len(s))] (google.com)
Hardware support;
stack in main memory;
Many CPUs have registers that can be used as stack pointers. Some, like the Intel x86, have special instructions that implicitly use a register dedicated to the job of being a stack pointer. Others, like the DEC PDP-11 and the Motorola 68000 family have addressing modes that make it possible to use any of a set of registers as a stack pointer. (google.com)
stack in registers;
The Intel 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. Sun's SPARC has a number of register windows organized as a stack which significantly reduces the need to use memory for passing function's arguments and return values. (google.com)

B.)illustration







C.) Reference
http://en.wikipedia.org/wiki/Stack_(data_structure
‎