Stack in Data Structure


 A stack is an ordinal list or data structure in which the mode of access to its elements is of type LIFO ( last in, first out) that allows you to store and retrieve data. 

It is applied on many occasions in computer science due to its simplicity and implicit arrangement in the structure itself. Graphical representation of a stack.


Stack in data structure


There are two basic operations for data management: stacking (push), which places an object on the stack, and its inverse operation, removing (or unstacking, pop), which removes the last stacked element.


Only the top of the stack, that is, the last stacked object (called TOS, Top of Stack), is accessible at any time. The remove operation allows obtaining this item, which is removed from the stack allowing access to the next one (previously stacked), which becomes the new TOS.


By analogy with everyday objects, a stack operation would be equivalent to placing a plate on a pile of plates, and a remove operation to remove it.


Batteries are usually used in the following contexts:

Evaluation of expressions in postfix notation (reverse Polish notation).

* Syntactic recognizers of context-independent languages

* Implementation of recursion.


Summary

  1. History of Stack
  2.  Call stack
  3. Stack as abstract data type
  4.  Operations of Stack
  5. Implementation of Stack


History of Stack 

The stack method for evaluating expressions was proposed in 1955 and two years later patented by Fiedrich L. Bauer, who received in 1988 the "IEEE Computer Society Pioneer Award" for his work in developing such a data structure.


Call stack

stack in data structure


The call stack is a memory segment that uses this data structure to store information about subroutine calls currently running in a program in progress.

Every time a new subroutine is called, a new entry is stacked with information about it such as its local variables. In particular, the return point to return to when this subroutine is finished is stored here (to return to the previous subroutine and continue its execution after this call).

Stack as abstract data type


Structure of a Pile

As a data type summary, the stack is a container for nodes and has two basic operations: push (or unstack) and pop (or unstack). 'Push' adds a node to the top of the stack, leaving the rest of the nodes below. 

'Pop' removes and returns the current top node in the stack. A frequently used metaphor is the idea of ​​a stack of dishes in a cafeteria with a stack spring.


In that series, only the first plate is visible and accessible to the user, all other plates remain hidden.


As the new plates are added, each new plate becomes the top of the stack, hidden underneath each plate, pushing the plate pile.

 As the top plate is removed from the stack, the second plate becomes the top of the stack.

Two important principles are illustrated by this metaphor: First the last output is a beginning, the second is that the contents of the stack are hidden. 

Only the top plate is visible, so to see what's on the third plate, the first and second plates will have to be removed.

Operations of Stack 

stack in data structure


A stack has 2 essential operations: stacking and unstacking, to which in modern implementations of stacks usually add more than usual use.

Create: The empty stack is created.

Stack - An item is added to the stack. (Push)

Unstack: the front element of the stack is removed. (Pop)

Top: returns the item that is on top of the stack. (top or peek)

Empty: returns true if the stack is empty.


Implementation of Stack

A typical storage requirement for a stack of n elements is O (n). the standard time requirement of O (1) operations also are easy to satisfy with an array or simple linked lists.


The standard C ++ template library provides a templated class "stack" that is limited to just stacking / unstacking operations.

 Java contains a library of the Stack class which is a specialization of Vector. This could be considered a defect, because the inherited design get () of Vector LIFO method ignores the Stack limitation.

These are simple examples of a stack with the operations described above (but there is no error checking).


AT PYTHON
class Stack (object):
def __init __ (self):
self.stack_p

Post a comment

0 Comments