Key Concepts

Review core concepts you need to learn to master this subject

Stack data structure

from node import Node class Stack: def __init__(self, limit=1000): self.top_item = None self.size = 0 self.limit = limit def push(self, value): if self.has_space(): item = Node(value) item.set_next_node(self.top_item) self.top_item = item self.size += 1 else: print("All out of space!") def pop(self): if self.size > 0: item_to_remove = self.top_item self.top_item = item_to_remove.get_next_node() self.size -= 1 return item_to_remove.get_value() else: print("This stack is totally empty.") def peek(self): if self.size > 0: return self.top_item.get_value() else: print("Nothing to see here!") def has_space(self): return self.limit > self.size def is_empty(self): return self.size == 0

A Stack is a data structure that supports two basic operations: pushing a new item to the top of the stack and popping a single item from the top of the stack.

In order to implement a stack using a node class, we have to store a node that is currently referencing the top of the stack and update it during the push and pop operations.

The stack data structure

from node import Node class Stack: def __init__(self, limit=1000): self.top_item = None self.size = 0 self.limit = limit def push(self, value): if self.has_space(): item = Node(value) item.set_next_node(self.top_item) self.top_item = item self.size += 1 else: print("All out of space!") def pop(self): if self.size > 0: item_to_remove = self.top_item self.top_item = item_to_remove.get_next_node() self.size -= 1 return item_to_remove.get_value() else: print("This stack is totally empty.") def peek(self): if self.size > 0: return self.top_item.get_value() else: print("Nothing to see here!") def has_space(self): return self.limit > self.size def is_empty(self): return self.size == 0

A stack is a data structure that follows a last in, first out (LIFO) protocol. The latest node added to a stack is the node which is eligible to be removed first. If three nodes (a, b and, c) are added to a stack in this exact same order, the node c must be removed first. The only way to remove or return the value of the node a is by removing the nodes c and b.

Main methods of a stack data structure

from node import Node class Stack: def __init__(self, limit=1000): self.top_item = None self.size = 0 self.limit = limit def push(self, value): if self.has_space(): item = Node(value) item.set_next_node(self.top_item) self.top_item = item self.size += 1 else: print("All out of space!") def pop(self): if self.size > 0: item_to_remove = self.top_item self.top_item = item_to_remove.get_next_node() self.size -= 1 return item_to_remove.get_value() else: print("This stack is totally empty.") def peek(self): if self.size > 0: return self.top_item.get_value() else: print("Nothing to see here!") def has_space(self): return self.limit > self.size def is_empty(self): return self.size == 0

The stack data structure has three main methods: push(), pop() and peek(). The push() method adds a node to the top of the stack. The pop() method removes a node from the top of the stack. The peek() method returns the value of the top node without removing it from the stack.

Stack overflow

from node import Node class Stack: def __init__(self, limit=1000): self.top_item = None self.size = 0 self.limit = limit def push(self, value): if self.has_space(): item = Node(value) item.set_next_node(self.top_item) self.top_item = item self.size += 1 else: print("All out of space!") def pop(self): if self.size > 0: item_to_remove = self.top_item self.top_item = item_to_remove.get_next_node() self.size -= 1 return item_to_remove.get_value() else: print("This stack is totally empty.") def peek(self): if self.size > 0: return self.top_item.get_value() else: print("Nothing to see here!") def has_space(self): return self.limit > self.size def is_empty(self): return self.size == 0

Every stack has a size that determines how many nodes it can accommodate. Attempting to push a node in a full stack will result in a stack overflow. The program may crash due to a stack overflow.

A stack is illustrated in the given image. stackA.push(xg) will result in a stack overflow since the stack is already full.

Chevron Left Icon
Stacks: Conceptual
Lesson 1 of 2
Chevron Right Icon
  1. 1

    A stack is a data structure which contains an ordered set of data. Stacks provide three methods for interaction: - Push - adds data to the “top” of the stack - Pop - returns and removes data from…

  2. 2

    Stacks can be implemented using a linked list as the underlying data structure because it’s more efficient than a list or array. Depending on the implementation, the top of the stack is equivalen…

  3. 3

    Let’s take a minute to review what we’ve covered about stacks in this lesson. Stacks: - Contain data nodes - Support three main operations - Push adds data to the top of the stack - Pop remov…

  1. 1

    You have an understanding of how stacks work in theory, so now let’s see how they can be useful out in the wild — with Python! Remember that there are three main methods that we want our stacks t…

  2. 2

    The stack’s […] and […] methods are our tools to add and remove items from it. […] additionally returns the value of the item it is removing. Keep in mind that we can only make modific…

  3. 3

    With stacks, size matters. If we’re not careful, we can accidentally over-fill them with data. Since we don’t want any stack overflow, we need to go back and make a few modifications to our methods…

  4. 4

    It’s time to add a couple helper methods. Helper methods simplify the code we’ve written by abstracting and labeling chunks of code into a new function. Here’s an example: […] This might se…

  5. 5

    Nice work — you’ve built out a […] class that can: - add a new item to the top via a […] method - remove an item from the top and returns its value with a […] method - return the val…

What you'll create

Portfolio projects that showcase your new skills

Pro Logo

How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory

Pro Logo