Stacks Flashcards Preview

Paper 1 - Computer Science > Stacks > Flashcards

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

What type of data structure is a stack?

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


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


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

It can be implemented as either


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


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

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


What does the pop() operation do?

It removes and returns the top item from the stack


What does the push(item) operation do?

It adds a new item to the top of the stack


What does the peek() operation do?

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


What does the isEmpty() operation do?

tests to see if the stack is empty


What does the isFull() operation do?

tests to see if the stack is full


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


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


What is a major use of a call stack?

Stores information about the active subroutines while the program is running


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.


Why store local variables in a call stack?

Because it's more efficient than using dynamic memory allocation


What is a call stack composed of?

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


What are the three things a stack frame holds?

Return addresses
Local Variable