Data Structure and Algorithm Design

Chapter 8

Xingang (Ian) Fang

Sections

  • Stack ADT and C++ Implementation

  • Queue ADT and C++ Implementation

  • Deque ADT and C++ Implementation

  • ADT Demonstration

Stack Abstract Data Type

Compare stack operations across array and linked implementations in our ADT Explorer.

  • Overview

  • Behaviors

Overview

  • A stack ADT is a container of elements that are inserted and removed according to the last-in first-out (LIFO) principle.

  • A.k.a. Push-down list, LIFO list, etc.

  • Characteristics

    • Homogeneous

    • Access order is LIFO/FILO

    • Finite

    • Dynamic size

  • Applications

    • Memory management (function call)

    • Editing tools (undo/redo)

    • Backtracking algorithms

    • Expression evaluation and conversion

  • Known as one of the linear ADT because it is usually implemented using a linear data structure. It is not logically linear. The concept of top, bottom, depth are also based on the implementations but not relevant to the ADT itself.

Behaviors

  • push: Insert an element to the stack.

  • pop: Remove and return an element from the stack.

  • peek: Return the element to be popped from the stack.

  • isEmpty: Check if the stack is empty.

  • size (optional): Return the number of elements in the container.

C++ Implementation of Stack ADT

Try stack operations in our ADT Explorer before implementing the interface in C++.

  • Use C++ STL container as a stack: std::stack, std::vector, std::deque, std::list

  • Make from scratch as templates

  • Example public interface:

    template <typename T>
class Stack {
 private:
  ///...
 public:
  void push(const T& value);
  T pop();
  T top() const; // or peek()
  bool isEmpty() const;
};

Data Structures

List of data structures and STL containers that can be used to implement a stack.

  • Partially filled C array

    • push pop at the end

    • fixed capacity

  • Linked list

    • Ideal

    • singly, add and remove at the head

    • doubly, add and remove at the head or tail

  • Make a wrapper class using other STL containers

    • std::vector

    • std::deque

    • std::list

Queue Abstract Data Type

Compare queue operations across array and linked implementations in our ADT Explorer.

  • Overview

  • Behaviors

Overview

  • A queue ADT is a container of elements that are inserted and removed according to the first-in-first-out (FIFO) principle.

  • A.k.a. FIFO queue, waiting line, pipe, etc.

  • Characteristics

    • Homogeneous

    • Access order is FIFO/LILO

    • Finite

    • Dynamic size

  • Applications

    • Breadth-first search

    • Scheduling

    • Buffering

  • Known as one of the linear ADT because it is usually implemented using a linear data structure. It is not logically linear.

Behaviors

  • enqueue: Add an element to the queue.

  • dequeue: Remove and return the value of the element with the highest/lowest rank from the queue.

  • peek: Return the element to be removed from the queue.

  • isEmpty: Return true if the stack is empty, false otherwise.

  • size (optional): Return the number of elements in the container.

C++ Implementation of Queue ADT

Try queue operations in our ADT Explorer before implementing the interface in C++.

  • Use C++ STL container as a queue: std::queue, std::deque, std::list

  • Make from scratch as templates

  • Example public interface:

    template <typename T>
class Queue {
 private:
  ///...
 public:
  void enqueue(const T& value);
  T dequeue();
  T peek() const;
  bool isEmpty() const;
};

Data Structures

List of data structures and STL containers that can be used to implement a queue.

  • Partially filled C array

    • enqueue at the end

    • dequeue at the front

    • better to use a circular array

    • fixed capacity

  • Linked list

    • Ideal

    • doubly, add and remove at the head or tail

  • Make a wrapper class using other STL containers

    • std::deque

    • std::list

Deque Abstract Data Type

Try operations at both ends of a deque in our ADT Explorer.

  • Overview

  • Behaviors

Overview

  • A deque (double-ended queue) ADT is a sequence/list of elements that can be added to or removed from both ends.

  • Characteristics

    • Homogeneous

    • Add and remove elements at both ends

    • Finite

    • Dynamic size

  • Applications (Mostly out of the scope of this course)

    • Implement a stack or a queue

    • BFS in 2D grid

    • Sliding window maximum/minimum

  • Known as one of the linear ADT because it is usually implemented using a linear data structure. It is not logically linear.

Behaviors

  • enqueue front/back: Insert an element to the front/back of the deque.

  • dequeue front/back: Remove an element from the front/back of the deque.

  • peek front/back: Return the element to be removed from the deque.

  • isEmpty: Return true if the stack is empty, false otherwise.

  • size (optional): Return the number of elements in the stack.

C++ Implementation of Deque ADT

  • Use C++ STL container as a deque: std::deque

  • Make from scratch as templates

  • Example public interface:

    template <typename T>
class Deque {
 private:
  ///...
 public:
  void enqueueFront(const T& value);
  void enqueueBack(const T& value);
  T dequeueFront();
  T dequeueBack();
  T peekFront() const;
  T peekBack() const;
  bool isEmpty() const;
};

Data Structures

List of data structures and STL containers that can be used to implement a deque.

  • Partially filled C array

    • better to use a circular array

    • fixed capacity

  • Linked list

    • Ideal

    • doubly, add and remove at the head or tail

  • Other STL containers

    • std::list