Data Structures: The Stack

Flashcards about Stacks

What is a Stack?

A stack is an Abstract Data Type where items are ordered by when they were added, and items are inserted/removed at one end.

What does LIFO stand for?

Last In, First Out

What does FILO stand for?

First In, Last Out

What is the function of 'push' in a stack?

Place an item on the stack.

What is the function of 'pop' in a stack?

Look at the item on top of the stack and remove it.

What is stack underflow?

Attempting to pop an item from an empty stack.

What is stack overflow?

Attempting to push an item onto a full stack.

What does Stack() do in the Stack ADT?

Creates a new stack.

What does Push(S, int x) do in the Stack ADT?

Adds integer x to stack S.

What does int Pop(S) do in the Stack ADT?

Removes and returns an integer from the top of stack S.

What does bool Empty(S) do in the Stack ADT?

Checks if stack S is empty, returns a boolean.

What are some applications of stacks?

Program execution via call stack, syntax and semantics of programming languages, evaluating expressions, parentheses matching, searching (Depth First).

What happens during a function call in relation to the system stack?

Push a new stack frame.

What happens when returning from a function call in the system stack?

Pop a stack frame.

How can stacks be used in matching braces?

Using stacks to determine if open and closed braces are correctly matched.

How can a stack be used to help a mouse find a path to cheese in a maze?

Using stacks to help the mouse find a path to the cheese.