Stack

Download python eBook

Introduction

A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure - elements can be added and removed from the stack only at the top. Here is a structural definition of a Stack: a stack is either empty or it consists of a top and the rest which is a Stack.

Syntax

  • stack = [] # Create the stack
  • stack.append(object) # Add object to the top of the stack
  • stack.pop() -> object # Return the top most object from the stack and also remove it
  • list[-1] -> object # Peek the top most object without removing it

Remarks

From Wikipedia:

In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed.

Due to the way their elements are accessed, stacks are also known as Last-In, First-Out (LIFO) stacks.

In Python one can use lists as stacks with append() as push and pop() as pop operations. Both operations run in constant time O(1).

The Python's deque data structure can also be used as a stack. Compared to lists, deques allow push and pop operations with constant time complexity from both ends.

Related Examples

Stats

107 Contributors: 16
Tuesday, April 11, 2017
Licensed under: CC-BY-SA

Not affiliated with Stack Overflow
Rip Tutorial: info@zzzprojects.com

Download eBook