Intro to Stacks and the Stack ADT

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/16

flashcard set

Earn XP

Description and Tags

A set of vocabulary terms covering the definition, operations, implementation, and applications of the Stack Abstract Data Type based on the provided lecture transcript.

17 Terms

1
New cards

Abstract Data Type (ADT)

An abstraction of a data structure that specifies the data stored, operations on the data, and error conditions associated with those operations.

2
New cards

Stacks

A type of container with restricted access that stores linear collections and follows a last-in first-out (LIFO) scheme.

3
New cards

Last-In First-Out (LIFO)

A scheme for insertions and deletions where the last item inserted into the collection is the first one to be removed.

4
New cards

push(object)

A main stack operation that inserts an element onto the top of the stack.

5
New cards

pop()

A main stack operation that removes and returns the last inserted element from the stack.

6
New cards

top()

An auxiliary stack operation that returns the last inserted element without removing it from the stack.

7
New cards

len()

An auxiliary stack operation that returns the integer number of elements stored in the stack.

8
New cards

is_empty()

An auxiliary stack operation that returns a boolean indicating whether no elements are stored in the stack.

9
New cards

Direct applications of Stacks

Page-visited history in a Web browser, Undo sequences in a text editor, and the chain of method calls in languages supporting recursion.

10
New cards

Indirect applications of Stacks

Use as an auxiliary data structure for algorithms or as a component of other data structures.

11
New cards

Array-based Stack implementation (Python)

A stack implementation using the Python list class, utilizing the append method for push operations and the pop method for removing the last element.

12
New cards

Space Complexity of Array-based Stack

The space used by the stack is O(n)O(n), where nn is the number of elements in the stack.

13
New cards

Performance of Stack Operations

Each main and auxiliary stack operation runs in time O(1)O(1).

14
New cards

ArrayStack class

A LIFO Stack implementation provided in the lecture notes that uses a Python list as underlying storage and raises an Empty exception if methods like top or pop are called on an empty stack.

15
New cards

ParenMatch(X,n) Algorithm

A stack-based algorithm that processes a string to ensure every opening symbol (, {, [ is matched by a corresponding closing symbol ), }, ] in the correct order.

16
New cards

lefty

In the Python is_matched implementation, the string variable representing the set of opening delimiters: '({['.

17
New cards

righty

In the Python is_matched implementation, the string variable representing the set of closing delimiters: ')}]'.