Study guide

9.3 Stacks, Queues, and Dictionaries (Maps)

Praxis Computer Science 5652

Track your progress as you read

Finished sections get a check mark.

1 Chapter 1: Praxis 5652 Exam Overview and ETS Pseudocode

1.1 Praxis 5652 Test Facts, Scoring, and Registration 1.2 Official ETS Pseudocode Notation and Tracing Strategy

2 Chapter 2: Impacts of Computing: Innovation, Access, and Effects

2.1 Computing for Creativity, Problem Solving, Communication, and Innovation 2.2 Equal Access, the Digital Divide, and Accessibility 2.3 Beneficial and Harmful Effects of Computing Innovations

3 Chapter 3: Impacts of Computing: Intellectual Property, Ethics, Privacy, and Security

3.1 Intellectual Property: Copyright, Open Source, and Creative Commons 3.2 Ethical and Unethical Computing Practices and Their Implications 3.3 Privacy, Security, Data Collection, and Local vs. Cloud Storage

4 Chapter 4: Algorithms and Computational Thinking: Abstraction, Decomposition, Number Bases, and Representation

4.1 Abstraction and Abstraction Hierarchies 4.2 Decomposition, Pattern Recognition, and Developing Algorithms 4.3 Number Bases: Binary, Octal, Decimal, and Hexadecimal 4.4 Algorithm Formats: Natural Language, Flowcharts, Pseudocode, and Tracing

5 Chapter 5: Algorithms: Efficiency, Limits of Computing, and Randomization

5.1 Algorithm Efficiency: Linear, Quadratic, Exponential, and Logarithmic Growth 5.2 Limits of Computing: Unsolvable Problems, Intractability, and Heuristics 5.3 Randomization, Random vs. Pseudorandom Numbers, and Scaling to a Range

6 Chapter 6: Algorithms: Searching, Sorting, and Recursion

6.1 Searching Algorithms: Linear Search and Binary Search 6.2 Sorting Algorithms: Tracing, Comparisons, Correctness, and Efficiency 6.3 Recursion: Base Cases, Tracing, Errors, and Iterative Equivalents

7 Chapter 7: Programming: Variables, Data Types, Strings, and Expressions

7.1 Variables, Data Types, and Type Conversion 7.2 Strings and String Operations 7.3 Operators, Precedence, Expressions, and Formulas 7.4 Boolean Expressions, Truth Tables, and Boolean Algebra

8 Chapter 8: Programming: Selection, Iteration, and Writing Code

8.1 Sequence and Selection: if, else, Chained and Nested Conditions 8.2 Iteration: for, while, do … while, and repeat … until Loops 8.3 Reading, Completing, and Modifying Code

9 Chapter 9: Programming: Procedures, Arrays, and Data Structures

9.1 Procedures, Parameters, Return Values, Nested Calls, and Scope 9.2 Arrays, Lists, and Two-Dimensional Arrays 9.3 Stacks, Queues, and Dictionaries (Maps)

10 Chapter 10: Programming: Correctness, Errors, Testing, and Code Quality

10.1 Program Correctness: Preconditions, Postconditions, Invariants, and Testing vs. Proof 10.2 Error Types and Debugging Techniques 10.3 Choosing Useful Test Cases: Boundaries, Partitions, Coverage, and Regression 10.4 Extensibility, Modifiability, and Reusability: Constants and Parameterization 10.5 Documentation, Code Reviews, Peer Feedback, and End-User Feedback

11 Chapter 11: Programming: Events, Usability, Input Validation, and APIs

11.1 Event-Driven Programming, Asynchronous Events, and Concurrency 11.2 Usability, Meaningful Error Messages, and Input Validation vs. Verification 11.3 Libraries and APIs: Reading Definitions, Making Calls, and Weighing Trade-offs

12 Chapter 12: Programming: Languages, Tools, Paradigms, and Object-Oriented Design

12.1 Low- and High-Level Languages, Compilers and Interpreters, and IDEs 12.2 Programming Paradigms: Procedural, Object-Oriented, and Others 12.3 Classes, Objects, Instance Variables, Methods, and Encapsulation 12.4 Inheritance, Polymorphism, and Overloading vs. Overriding

13 Chapter 13: Data: Bits, Encoding, Compression, and Encryption

13.1 Bits and Bytes: Why Binary, Storage Calculations, and Signed Integers 13.2 Encoding Text, Images, and Sound 13.3 Lossless and Lossy Compression: Run-Length Encoding, Huffman Coding, and Media Formats 13.4 Encoding vs. Encryption, Symmetric and Public-Key Encryption, and Their Trade-offs

14 Chapter 14: Data: Analysis Tools, Simulation, Storage, and Collection

14.1 Analyzing Data with Spreadsheets: Cleaning, Transforming, and Visualizing 14.2 Simulation and Modeling 14.3 Files, Databases, and Storage Requirements: Scale, Redundancy, and Backup 14.4 Collecting, Aggregating, and Generating Data: Public Data Sets, Surveys, Sensors, and Crowdsourcing

15 Chapter 15: Computing Systems: Hardware, Operating Systems, and Computing Environments

15.1 Hardware Components and the Fetch–Decode–Execute Cycle 15.2 Operating Systems, Software Components, and Resource Issues 15.3 Embedded Systems, the Internet of Things, and Types of Computing Systems 15.4 Local, Network, and Cloud Computing and Storage; How Binary Data Are Stored

16 Chapter 16: Networks, the Internet, the Web, and Cybersecurity

16.1 Network Types and Wired and Wireless Communication 16.2 Network Hardware and Layered Network Models (OSI and TCP/IP) 16.3 Network Performance: Bandwidth, Latency, Load, and Estimating Needs 16.4 How the Internet Works: Protocols, IP Addressing, DNS, URLs, and Reliability 16.5 The Web: HTTP, HTML and Markup Languages, Browsers, Servers, and Clients 16.6 Cybersecurity: The Five Pillars, Strong Passwords, Security Strategies, and Trade-offs

9.3 Stacks, Queues, and Dictionaries (Maps)

Key Takeaways Explain This Topic AI

A stack is last-in, first-out (LIFO): push adds to the top and pop removes the most recently added item.

A queue is first-in, first-out (FIFO): enqueue adds at the back and dequeue removes the item that has waited longest.

A dictionary (map) stores key–value pairs with unique keys; storing a value under an existing key replaces the old value.

Undo features, matching parentheses, and the call stack use stacks; waiting lines, print jobs, and breadth-first search use queues; ID lookups and word counts use dictionaries.

Hash-table dictionaries give O(1) average lookup, insertion, and removal, degrading to O(n) if many keys collide.

Last updated: September 2026

What this competency asks

ETS asks you to be familiar with dictionaries/maps, stacks, and queues :

Identify a data structure based on a description of its behavior or appropriate use.

Given goals, constraints, or context, identify the most appropriate data structure.

Trace code that uses a particular data structure.

ETS's sample question describes three situations: cars lining up at a car wash, contestants given unique ID numbers, and tennis balls loaded into and removed from the top of a can. It asks which structure models each. The answer is queue, dictionary, stack. Every question of this type is solved by asking "which item comes out next?" or "how is an item found?"

Abstract data types

An abstract data type (ADT) is defined by its behavior, meaning the operations it supports and what they guarantee, not by how it is stored. A stack could be built from an array or from a linked list. The user sees only push and pop. This is abstraction applied to data (Section 4.1).

Stacks: last in, first out

A stack works like a stack of plates or a can of tennis balls: you add and remove only at the top .

  • Operation Effect
  • push ( x ) Put x on top
  • pop ( ) Remove and return the top item
  • peek ( ) Return the top item without removing it
  • isEmpty ( ) Report whether the stack is empty

Popping an empty stack is an error ( underflow ). All of these operations take O(1) time.

Uses: undo and redo; the browser Back button; matching brackets (push each opening symbol, and pop and compare at each closing symbol); evaluating expressions; and the call stack , which tracks procedure calls and recursion (Section 6.3).

Queues: first in, first out

A queue works like a waiting line: items join at the back and leave from the front .

  • Operation Effect
  • enqueue ( x ) Add x at the back
  • dequeue ( ) Remove and return the front item
  • peek ( ) Return the front item without removing it
  • isEmpty ( ) Report whether the queue is empty

Uses: print jobs, customer-service lines, keyboard input buffers, scheduling tasks in the order they arrive, messages between programs, and breadth-first search , which explores a graph level by level.

An array-based queue avoids shifting elements by keeping front and back indexes that wrap around with the remainder operator, back ← ( back + 1 ) % capacity . This design is called a circular buffer .

Dictionaries (maps)

A dictionary (also called a map or associative array) stores key → value pairs.

  • Operation Effect
  • put ( key, value ) Store the pair; if the key already exists, replace its value
  • get ( key ) Return the value for the key, or indicate it is absent
  • containsKey ( key ) Report whether the key is present
  • remove ( key ) Delete the pair

Keys are unique , but values need not be. Two students can have the same grade, but not the same student ID.

Uses: looking up a record by ID, counting word frequencies (the key is the word and the value is its count), caching results, configuration settings, and translating codes to names.

Most dictionaries are hash tables . A hash function converts the key into an array position, so get and put take O(1) on average . When two keys land in the same position (a collision ), the table stores both, for example in a short list at that position. If a poor hash function sends many keys to the same position, operations degrade toward O(n) . Tables grow and redistribute their entries when they get too full.

Choosing the right structure

  • Description in the question Structure
  • "The most recent item is handled first" Stack
  • "Items are handled in the order they arrived" Queue
  • "Find the item by its unique label, ID, or name" Dictionary
  • "Reverse the order of the items" Stack (push all, then pop all)
  • "Items enter at one end and leave from the other" Queue
  • "Items enter and leave through the same opening" Stack
  • "Access the item at position k" Array or list
  • Tracing practice Stack S ← new Stack ( )
  • Queue Q ← new Queue ( )
  • S.push ( 10 )
  • S.push ( 20 )
  • Q.enqueue ( S.pop ( ) ) // S: [10] Q: [20]
  • S.push ( 30 ) // S: [10, 30]
  • Q.enqueue ( 40 ) // Q: [20, 40]
  • S.push ( Q.dequeue ( ) ) // dequeue returns 20; S: [10, 30, 20]; Q: [40]
  • int val ← S.pop ( ) // val = 20

Write the contents after every line, and mark which end is the top of the stack and which is the front of the queue. Most tracing errors come from popping the wrong end.

  • Word counting with a dictionary Map counts ← new Map ( )
  • for each word w in the text
  • if ( counts.containsKey ( w ) )
  • counts.put ( w, counts.get ( w ) + 1 )
  • else
  • counts.put ( w, 1 )
  • end if
  • end for

For the text "to be or not to be," the final pairs are to → 2, be → 2, or → 1, not → 1. (The for each line is informal. ETS code would loop over an index.)

Complexity summary

  • Structure Add Remove Find by key or position
  • Stack O(1) push O(1) pop (top only) Only the top is accessible
  • Queue O(1) enqueue O(1) dequeue (front only) Only the front is accessible
  • Dictionary (hash table) O(1) average O(1) average O(1) average by key
  • Array — — O(1) by index; O(n) to search by value