Stacks And Queues

Stacks & Queue Week 6

Faezeh Seyedarabi

www.faezeh.co.uk

1

Stacks A stack is one of the methods used to insert and delete items from a linear list. For example, pile of plates in a canteen. After washing up the plates, the last plate will be placed on to the top of the stack. The next plate to be used will be taken from the top of the stack (i.e. LIFO stack) We refer to the ‘top of the stack’ or the ‘buttom of the stack’, thus the number will be set out vertically, to reinforce this point visually. We also have the phrase ‘pushed on the top of the stack’ to indicate that an item of data has been added to the stack. Moreover, we have the phrase ‘popped off the stack’ to indicate that the ‘last number in’ is always the ‘first number out’ The system of storing this list of numbers is called LIFO stack (Last In First Out). A Pointer System In practice a stack would be built up in the computer’s memory using a pointer system. This is a number used to pint to an item of interest, so it may be used to point to the memory location inside the computer that indicates the top of the stack. (called Stack Pointer) Faezeh Seyedarabi

www.faezeh.co.uk

2

For example, consider the numbers in the list: 23 54 10 90

Faezeh Seyedarabi

Add number 77 (PUSH)

77 23 54 10 90

Stack _pointer

variable used to indicate the current top of the stack.

Maximum

used to determine when the stack is full.

Minimum

used to determine if the stack is empty.

Data

item in data to be pushed or popped.

STACK

general name for the stack contained in memory.

STACK(Stack_pointer)

subscripted variable representing the data at the current stack pointer, i.e. it is an identifier for the data on the stack. www.faezeh.co.uk

3

Pseudocode to PUSH a new item of data on to the top of the STACK Note: if there is no room to add a new item then a error message must be generated, as an overflow has occurred. Example: (Let’s assume that an array STACK(N) has been already set up.) PUSH (Stack_pointer, Maximum, Data)

Calling the procedure

The actual Pseudocode for the PUSH procedure: PROCEDURE PUSH (Stack_pointer, Maximum, Data) (*Check if the stack is already full*) IF Stack_pointer=Maximum THEN PRINT No room on the stack EXIT PROCEDURE ELSE (*Push data item on the stack*) SET Stack_pointer= Stack_pointer+1 SET Stack_pointer= Data END IF END PROCEDURE Faezeh Seyedarabi

www.faezeh.co.uk

4

Pseudocode to POP a new item of data on to the top of the STACK Note: here the stack cannot overflow from this operation. However, there might be no items of data on the stack, in which case cannot remove any more data. POP (Stack_pointer, Maximum, Data)

Calling the procedure

The actual Pseudocode for the POP procedure: PROCEDURE POP (Stack_pointer, Maximum, Data) (*Check if the stack is already empty*) IF Stack_pointer=Minimum THEN PRINT the stack is already empty EXIT PROCEDURE ELSE (*Pop data off of stack and adjust pointer*) SET Data= STACK (Stack_pointer) SET Stack_pointer= Stack_pointer - 1 END IF END PROCEDURE Faezeh Seyedarabi

www.faezeh.co.uk

5

Queues A queue is very similar in principle to the operation of a stack, a queue is often called a FIFO stack (First In First Out). E.g. normal queue, waiting to be served in a shop, where the first person in the queue is expected to get served first and thus will be first person out. Note: in this operation the data does not move, it is just the pointers that have been altered. We have the start pointer (indicating to the head of the queue) and stop pointer (indicating to the end of the queue). Start _pointer

variable used to indicate the start of the queue.

Stop_pointer

variables used to indicate the end of the queue.

Size

variables that represents the size of the queue. (Data elements in the queue)

Data

item in data to be pushed or popped.

QUEUE

general name for the queue contained in memory.

QUEUE(pointer)

subscripted variable representing the data at the current pointer position, i.e. an identifier for the data on the queue.

Faezeh Seyedarabi

www.faezeh.co.uk

6

Summery What does a stack mean? A stack is an area of memory set up as a temporary storage for data. A stack has a logical top and bottom, which represent the places at which the beginning and end of the data can be found. How might a stack be implemented? Stacks are implemented by pointers which point to specific areas of memory. What is a pointer? A pointer is simply a data element that indicates the position of some other data element (e.g. the data element that points to the top of the stack). What does the term ‘push’ mean? Push is the term used to indicate that data has been placed on the stack. What does the term ‘pop’ mean? Pop is the term used to indicate that data has been removed from the stack. What is LIFO stack? A LIFO stack is a Last-In-First-Out stack. Faezeh Seyedarabi

www.faezeh.co.uk

7

What is FIFO stack? A FIFO is a First-In-First-Out stack. What is an Overflow? A queue or a stack may have a maximum size. An attempt to add a new element to a queue or stack which is already full will result in an overflow error. What is an Underflow? An attempt to remove an item from an empty queue or stack will result in an underflow.

Faezeh Seyedarabi

www.faezeh.co.uk

8