Stack

Introduction

Introduction to Stacks

What is a stack?

A stack is a First In Last Out (FILO) data structure that is commonly used for a variety of purposes in computer systems.

Example usage:

  • Recursion
  • Expression Evaluation
  • Parsers
  • Backtracking Algorithms

A common analogy of a stack is when you are washing dishes. As more dishes are brought in to wash they are added to the top of the stack of dishes. When you have finished washing a plate you take the next plate from the top of the pile

 

What do you need to know for AS Level?

You need to be able to:

  • Describe the key features of a stack, queue and linked list and justify their use for a given situation
  • Candidates will not be required to write pseudocode for these structures, but they should be able to add, edit and delete data from these structures.

Stack Methods

Stack Methods

Stacks have three main methods:

  • Push
  • Pop
  • Peak

Push

This is where an item is added to the top of the stack. If the stack is full and the item cannot be added then an error is raised.

Pop

This is where an item is removed from the top of the stack and returned to the program for further processing. If the stack is already empty then an error is raised.

Peek

This is where the value contained at the top of the stack is returned to the program without removing the item from the stack. If the stack is empty then an error is raised.

 

Python Stack

Python Implementation

Python (Functional Programming)

Python (Object Orientated Programming)

Link List (can use to implement a stack)

Resources

Resources

Stacks – Teacher Presentation

Past Paper Questions

AS Level Questions

I couldn’t find any past paper questions at AS Level…

A Level Questions

W18 Paper 43 – Question 3

 

example – browsing history app. (click link / press back button)