CS415 - Stacks & Queues

NH Linear Data Structures in CS 415

Introduction

  • Course Title: Introduction to Computer Science I

Linear Data Structures

  • Definition: A linear data structure is where items are stored sequentially (or linearly).

  • Item Ordering: Items are ordered in some manner - first, second, last, etc.

  • Examples:

    • Lists: Previously discussed.

    • Tuples: To be discussed next week.

    • Arrays: Will be covered in later classes.

    • Stacks: Today's topic.

    • Queues: Today's topic.

    • Linked Lists: Today's topic.

Stacks

Definition

  • A stack is a linear data structure that follows the LIFO (Last In, First Out) rule.

Structure

  • Access Rule: Elements can only be added or removed from the top of the stack.

  • Visual Representation:

    • Bottom of Stack

      • Stack Item 1

      • Stack Item 2

      • Stack Item 3

    • Top of Stack

      • Only the top item can be removed.

      • New items are added at the top.

Stack Operations

  • push(s, x): Adds item x to the top of stack s.

  • x = pop(s): Removes the item from the top of stack s and stores it in x.

Operational Examples

  1. Adding Item:

    • Call `push(s,