Stacks Flashcards Preview

Paper 1 - Computer Science > Stacks > Flashcards

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

What type of data structure is a stack?

A

A stack is LIFO type of data structure

Last in first out

2
Q

What are some real life applications of stacks?

A
  • used in calculations of reverse polish notation
  • used in recursive algorithms
  • Can hold information when subroutines are called
3
Q

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

A

It can be implemented as either

4
Q

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

A

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
Q

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

A
  • pop()
  • push(item)
  • peek()
  • isEmpty()
  • isFull()
6
Q

What does the pop() operation do?

A

It removes and returns the top item from the stack

7
Q

What does the push(item) operation do?

A

It adds a new item to the top of the stack

8
Q

What does the peek() operation do?

A

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

9
Q

What does the isEmpty() operation do?

A

tests to see if the stack is empty

10
Q

What does the isFull() operation do?

A

tests to see if the stack is full

11
Q

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

A

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
Q

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

A

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
Q

What is a major use of a call stack?

A

Stores information about the active subroutines while the program is running

14
Q

What does the call stack keep track of?

A

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

15
Q

Why store local variables in a call stack?

A

Because it’s more efficient than using dynamic memory allocation

16
Q

What is a call stack composed of?

A

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

17
Q

What are the three things a stack frame holds?

A

Return addresses
Local Variable
Parameters