Stacks Flashcards Preview

Paper 1 - Computer Science > Stacks > Flashcards

Flashcards in Stacks Deck (17)
Loading flashcards...
1

What type of data structure is a stack?

A stack is LIFO type of data structure
(Last in first out)

2

What are some real life applications of stacks?

- used in calculations of reverse polish notation
- used in recursive algorithms
- Can hold information when subroutines are called

3

Is a stack a dynamic or static type of data structure?

It can be implemented as either

4

Explain how a stack could be implemented as a static data structure?

Could do this using a (static) array and two variables. One that holds the index of the pointer and one that holds the size of the list

5

What are the 5 operations that could be carried out on a stack data structure?

- pop()
- push(item)
- peek()
- isEmpty()
- isFull()

6

What does the pop() operation do?

It removes and returns the top item from the stack

7

What does the push(item) operation do?

It adds a new item to the top of the stack

8

What does the peek() operation do?

It returns the top item from the stack but does not remove it

9

What does the isEmpty() operation do?

tests to see if the stack is empty

10

What does the isFull() operation do?

tests to see if the stack is full

11

What could cause an overflow when implementing a stack using an array?

If an item is appended to a full list of n items, the pointer will go up to n+1, causing an error as the item can't be added to the list

12

What could cause an underflow when implementing a stack using an array?

If an item is removed from an empty list, this will cause an error as there will be no items left to remove and the pointer will become -1

13

What is a major use of a call stack?

Stores information about the active subroutines while the program is running

14

What does the call stack keep track of?

It keeps track of the return addresses (of several nested subroutines) As each subroutine completes each address is popped off the stack.

15

Why store local variables in a call stack?

Because it's more efficient than using dynamic memory allocation

16

What is a call stack composed of?

Stack frames. Each stack frame corresponds to call to a subroutine.

17

What are the three things a stack frame holds?

Return addresses
Local Variable
Parameters