课 27, 主题 9

In Progress

← Previous Next→

stacks

课 Progress

0% Complete

Stacks

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)

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

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

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

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”)

2 marks

Answer: