课 12, 主题 3

In Progress

← Previous Next→

stacks as

课 Progress

0% Complete

Exam code:H046

Stacks

What is a stack?

Stacks are a last in first out (LIFO) data structure
Items can only be added to or removed from the top of the stack
Stacks are key structures in the computing world as they are used to reserve an action, such as go back a page or undo
A real-life example of a stack would be a pile (or stack) of plates at a buffet; you can only take a plate from the top, and if you need to reach the bottom one you have to remove all the others first
It is often implemented using an array
Where the maximum size required is known in advance, static stacks are preferred as they are easier to implement and make more efficient use of memory
A stack has 6 main operations, which can be seen below

Operation	Description
`isEmpty()`	This checks is the stack is empty by checking the value of the top pointer
`push(value)`	This adds a new value to the end of the list, it will need to check the stack is not full before pushing to the stack.
`peek()`	This returns the top value of the stack. First check the stack is not empty by looking at the value of the top pointer.
`pop()`	This removes and returns the top value of the stack. This first checks if the stack is not empty by looking at the value of the top pointer.
`size()`	Returns the size of the stack
`isFull()`	Checks if the stack is full and returns the Boolean value, this compares the stack size to the top pointer.

Stacks use a pointer which points to the top of the stack, where the next piece of data will be added (pushed) or the current piece of data can be removed (popped)

Adding & Removing Data From a Stack

Pushing data to a stack

When pushing (adding) data to a stack, the data is pushed to the position of the pointer
Once pushed, the pointer will increment by 1, signifying the top of the stack
Since the stack is a static data structure, an attempt to push an item on to a full stack is called a stack overflow

Visual example

This would push Bunny onto the empty stack

This would push Dog to the top of the stack
This would push Ant to the top of the stack

Popping data from a stack

When popping (removing) data from a stack, the data is popped from the position of the pointer
Once popped, the pointer will decrement by 1, to point at the new top of the stack
Since the stack is a static data structure, an attempt to pop an item from an empty stack is called a stack underflow

Visual example

This would pop Ant From the top of the stack. The new top of the stack would become Dog

Note that the data that is ‘popped’ isn’t necessarily erased; the pointer ‘top’ moves to show that Ant is no longer in the stack and depending on the implementation, Ant can be deleted or replaced with a null value, or left to be overwritten

Worked Example

Stacks and queues are both data structures.

A stack is shown below before a set of operations are carried out on it.

Draw what the stack shown below would look like after the following operations:

pop(), push(“A”), push(“B”), pop(), push(“E”), push(“F”)

Pointer	Data
→	Z
	Y
	X

2 marks

Answer:

Start by using the operation pop() to remove Z from the top of the stack

Pointer	Data
→	Y
	X

Use the operation push(“A”) to add A to the top of the stack

→	A
Pointer	Data
	Y
	X

Then use the operation push(“B”) to add B to the top of the stack

→	B
Pointer	Data
	A
	Y
	X

Then use pop() to remove the top item in the stack

→	A
Pointer	Data
	Y
	<p class=”tex

Computer Science AS OCR

stacks as

Stacks

What is a stack?

Adding & Removing Data From a Stack

Pushing data to a stack

Visual example

Popping data from a stack

Visual example

Worked Example

Responses